КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ

|

Множество всех целых чисел (положительных, отрицательных и нуля) образуют кольцо относительно обычных операций сложе­ния и умножения. Это кольцо принято обозначать через Z. В данном параграфе мы будем изучать структуру кольца целых чисел.

Говорят, что целое число s делится на целое число r или что r делит s (или что r является делителем s),если rа=s, где а-не­которое целое число. Если r и делит s,и делится на s, то r=±s. Действительно, r=sа и s=rb для некоторых целых чисел а и b;следовательно, г=rаb и аb должно равняться 1.Так как а и b-целые, то и a, и b должны быть либо 1, либо - 1.

Положительное целое число р > 1, которое делится только на ±р или ±1, называется простым. Положительное целое число, большее 1, не являющееся простым, называется составным. Наибольший общий делитель двух целых чисел гr и s обозначается через НОД (r, s) и определяется как наибольшее положительное число, которое делит оба из них. Наименьшее общее кратное двух целых чисел r и s обозначается через НОК (r, s) и определяется как наименьшее положительное число, которое делится на оба из них. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.

В общем случае в кольце целых чисел деление возможно не всегда, зато имеют место две почти столь же важные операции, а именно сокращение и деление с остатком. В силу возможности сокращения кольцо целых чисел является областью целостности. Возможность деления c остатком (известного как алгоритм деле­ния) обычно доказывается с помощью конструктивной процедуры. Мы сформулируем его в виде самоочевидной теоремы.

Теорема 2.1.1 (алгоритм деления).Для каждой пары целых
чисел с и d при отличном от нуля d найдется единственная пара
целых чисел Q, (частное) и s (остаток), таких, что

с=dQ+s,
где 0≤ s < | d.

Обычно нас будет больше интересовать не частное, а остаток. Мы будем часто записывать остаток в виде равенства

s =≡ R_d [с],

которое читается так: s является остатком от деления с на d. Другим обозначением является

s ≡= с (mod d).

Соотношение такого вида называется сравнение и читается так: “s сравнимо с c по модулю d”. Оно означает, что при делении на d числа s и с имеют один и тот же остаток, но s не обязательно меньше d.

Вычисление остатка от сложного выражения, содержащего сложение и умножение, облегчается тем, что можно менять после­довательность выполнения операции вычисления остатка со сложением и умножением. А именно справедливо следующее утвер­ждение.