Делители нуля в кольце вычетов Zm

Отличные от нуля элементы кольца, произведение которых равно нулю, называются делителями нуля.

Т: Если НОД (m,); ?Zm, то класс является делителем 0 в кольце вычетов Zm.

Доказательство: (m,)=d, d.

Выберем а?, тогда (m, a)=d, d.

Тогда, a=dx, m=dy, (x, y)=1.

Очевидно, что m>d>0, поэтому.

ay=dxy=mx.

(ay).

— делитель 0.

Следствие: любой класс вычетов в кольце Zm является либо нулевым, либо делителем нуля, либо обратимым в Zm. Действительно, если.

Функция Эйлера

• *Ф-ей Эйлера называется числовая ф-ия, которая определяет число классов вычетов по mod m взаимно простых с этим модулем.
• *Ф-ей Эйлера называется числовая ф-ия, которая определяет число натуральных чисел, не превосходящих m и взаимно простых с m.

Из определения следует, что ф-ия Эйлера определяет число элементов в приведенной системе вычетов по mod m.

Определим способы вычисления ф-ии Эйлера ?(m).

Если m=1, то кольцо классов вычетов состоит из одного класса; Если НОД (1,1)=1, то принято считать, что ?(1)=1.

Если m=p, p — простое число, тогда ?(m)=?(р)=р-1.

Если.

Теоремы Эйлера и Ферма

Т (Эйлера): Если целое число, а взаимно просто с m, то .

Док-во: т.к. (а, m)=1, то коммутативная группа обратимых элементов кольца Zm.

Любой элемент группы Рm, т. е. класс, порождает подгруппу, порядок которой является делителем числа элементов в группе Рm, а это число элементов есть ?(m).

Порядком подгруппы называют такое натурально число s, что .

Пусть ?(m)=s*t.

.

Т (малая теорема Ферма): Если р — простое число, а — произвольное целое число и (а, р)=1, то ар-11(mod p).

Док-во: Из теоремы Эйлера>, -целое.

Тогда при m=p,, .

Очень часто применяют следствие из малой теоремы Ферма, хотя ее бывает называют просто теоремой Ферма: ара (mod p).