Мы рассмотрим конечное кольцо \(\mathbf{Z}_m\), так как вычисления в нем помогут нам решать некоторые задачи для всех целых чисел.
В кольце классов вычетов \(\mathbf{Z}_m\) обратимыми являются те и только те элементы \(a\), которые взаимно просты (не имеют общих делителей кроме 1) с модулем \(m\).
Теорема. Кольцо \(\mathbf{Z}_m\) является полем тогда и только тогда, когда \(m\) - простое число1.
Напомним теорему о делении целых чисел с остатком:
Теорема. Для любых целых чисел \(a, b\), где \(b \neq 0\), существует единственная пара целых чисел \(q, r\), таких, что \(a = bq + r\) и \(0 \leq r < |b|\).
Наибольшим общим делителем (НОД) целых чисел \(a \neq 0\) и \(b\) называется наибольший из общих делителей этих чисел.
Лемма. Если \(a = bq + r\), то \((a, b) = (b, r)\).
Алгоритм Евклида нахождения НОД состоит следующем шаге:
В тот момент, когда при очередном делении получим \(r=0\), мы используем \((b,0) = b\).
Просмотр полученной при делениях цепочки равенст позволяет доказать
Лемма. НОД целых чисел линейно выражается через них: \[(a,b) = \alpha \cdot a + \beta \cdot b\]
Верно и обратное:
Лемма. Если общий делитель целых чисел линейно выражается через них, то это их НОД.
Теперь можно легко доказать утверждение об обратимости по простому модулю. В \(\mathbf{Z}_m\) при простом модуле \(m\) для любого \(a \neq 0\) из \((a,m)=1\) можно получить выражение \(\alpha a + \beta m = 1\) для подходящих целых чисел \(\alpha\), \(\beta\). Из него получим \(\alpha a = \beta m + 1\). Это означает, что остаток от деления \(\alpha a\) на \(m\) равен 1 или что \(\alpha\) является обратным к \(a\) в \(\mathbf{Z}_m\).
Функцией Эйлера называется функция \(\phi\), ставящая в соответствие каждому натуральному числу \(n\) количество таких натуральных чисел \(k\), что \(k \leq n\) и \((k,n) = 1\).
В кольце классов вычетов \(\mathbf{Z}_m\) обратимыми являются те и только те элементы \(a\), которые взаимно просты с модулем \(m\). Множество всех таких обратимых элементов образует группу по умножению - мультипликативную группу кольца \(\mathbf{Z}_m\). Количество элементов в ней (порядок этой группы) равно \(\phi(m)\).
Теорема. (Эйлер) Для любого целого числа \(a\) взаимно простого с \(m\) справедливо \(a^{\phi(m)} \mod m = 1\).
Пусть все взаимно простые с \(m\) числа не превышающие \(m\) (приведенная система вычетов) собраны во множестве \(R = \{ r_i \mid i=1,\ldots,\phi(m) \}\). Тогда множество \(aR = \{ a r_i \mod m \mid i=1,\ldots,\phi(m) \}\) обладает тем же свойством, т.е. \(R = aR\). В самом деле, все элементы \(aR\) различны (на \(a\) можно сокращать по модулю \(m\)) и из \((a r_i, m)=1\) следует \((a r_i \mod m, m)=1\). Получаем \(\prod r_i \mod m = \prod a r_i \mod m = a^{\phi(m)} \prod r_i\). После сокращений на \(r_i\), окончательно \(a^{\phi(m)} \mod m = 1\).
Следующие теоремы позволяют2 вычислять функцию Эйлера если известно разложение числа на простые ножители.
Теорема. Функция Эйлера мультипликативна: \(\phi(ab) = \phi(a) \phi(b)\) для любых взаимно простых \(a\) и \(b\).
Теорема. Для простого числа \(p\) и натурального числа \(k\): \(\phi(p^k) = p^k - p^{k-1}\).