Теорема Эйлера и малая теорема Ферма

Теорема Эйлера. Если числа а и m взаимно просты, то a^φ(m)º1(modm).

Доказательство.

Пусть  приведенная система вычетов по модулю m. Так как , то  так же приведенная система вычетов по модулю m.

Отсюда следует, что для каждого числа системы  найдется единственное сравнимое с ним число из системы . То есть существует следующая система сравнений:

………………………

,

где - перестановка чисел .

Перемножим почленно эти сравнения:

И после преобразования левой части получим: .

Разделим обе части сравнения на число  взаимно простое с m, получим требуемый результат .

Если m = р — простое число, то, как было выше указано, φ(р)= р - 1, и теорема Эйлера в этом случае принимает вид: .

В этом случае теорема Эйлера носит название малой теоремы Ферма.

Кольца и поля классов вычетов

Классом вычетов по модулю т с представителем называется множество .

Для обозначения всех классов вычетов по модулю m будем использовать обозначение: .

На множестве классов вычетов определим две внутренние бинарные опереции.

Сумму классов вычетов определим как класс вычетов, содержащий число , то есть

.

Произведение классов вычетов  определим как класс вычетов, содержащий число , то есть

. Построенное нами множество  классов вычетов с введенными на нем бинарными операциями является коммутативным кольцом.

Элемент  кольца называется делителем нуля, если существует элемент  этого же кольца такой, что .

Таким образом, кольцо  является кольцом с делителями нуля.

В кольце  классов вычетов по модулю m нет делителей нуля тогда и только тогда, когда m простое число.

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

Теорема о полях вычетов: Кольцо  является полем тогда и только тогда, когда p – простое число.

Сравнения с неизвестным

Пусть a_nxⁿ + a_n-1x^n-1 + ... + a₁x¹+a₀º0(modm)   есть сравнение, в котором a₀, а₁,..., a_nÎZ, а буквой х обозначена неизвестная величина, принимающая значения из Z.

Любое целое число, при подстановке которого вместо х сравнение превращается в верное сравнение целых чисел называется решением этого сравнения. Сравнения с неизвестным х называются равносильными, если они имеют одно и то же множество решений.

При замене в сравнении любого из коэффициентов a_i сравнимым с ним по модулю m числом получится сравнение, равносильное исходному. Следовательно, не теряя общности, можно считать, что 0 ≤ a_i< m, i = 0,..., n.

Любое сравнение первой степени может быть записано в виде , где  или .

Сравнение  разрешимо тогда и только тогда, когда . При выполнении последнего условия исходное сравнение имеет d решений по модулю m. Если условие не выполняется, то решений нет.

В любом случае решение сравнения  сводится к случаю, когда . Отсюда следует следующее важное утверждение:

Если , то сравнение  имеет единственное решение , которое может быть найдено с использованием теоремы Ферма.

Но это единственное решение может быть найдено и с помощью расширенного алгоритма Евклида, по которому из условия  следует способ нахождения таких целых чисел u и v, что . А это и означает, что , то есть  и далее , то есть найдено решение  сравнения .