Функция Эйлера. Теоремы Эйлера, Ферма и др.

Теорема. Пусть каноническое разложение натурального числа . Тогда

.

Утверждение теоремы вытекает из приводимых ниже лемм 1, 2.

Лемма 1. Пусть − простое число, . Тогда

.

Доказательство. Среди чисел , ,…, имеется в точности чисел, кратных . Остальные числа взаимно просты с и, следовательно, с . ∎

Лемма 2. Если нод ( , , то .

Доказательство. Для утверждение леммы очевидно. Пусть . Рассмотрим множество , , …, . Его можно представить как объединение

попарно не пересекающихся подмножеств

, , ,…, , , , …, .

Удалим из подмножества , для которых нод , . В результате в останется подмножеств . Каждое из оставшихся подмножеств содержит только числа из , взаимно простые с . Далее, любое из подмножеств представляет собой полную систему вычетов по модулю . В каждом из них содержится в точности чисел, взаимно простых с . Эти числа оставим, а остальные удалим из . В результате в останутся те и только те числа из , которые взаимно просты как с числом , так и с числом , и, следовательно, с . Всего же во множестве , после всех удалений, останется чисел. С другой стороны, в исходном множестве содержится чисел, взаимно простых с . Значит, . ∎

Теорема Эйлера.

нод , .

Доказательство. Пусть , ,…, , где ,− числа, образуют приведённую систему вычетов по модулю . Тогда согласно теореме числа , ,…, также образуют приведённую систему вычетов по модулю . Поэтому всякое число сравнимо по модулю с некоторым числом , и обратно. Следовательно, имеет место система сравнений

,

,

…

,

где , , …, − некоторая перестановка индексов , , …, . Перемножая левые и правые части этих сравнений, получаем

Так как нод , , то левую и правую части последнего сравнения можно сократить на . В результате получим . ∎

Следствие (Малая теорема Ферма). Если − простое число и , то

.

Доказательство. Достаточно учесть, что , и применить теорему Эйлера.∎

Следствие. Если простое число, то

для любых , .

Доказательство. Если , то . Если , то последнее сравнение заведомо выполняется. Но тогда

. ∎

Теорема Эйлера допускает следующее обобщение:

Теорема Кармайкла. Для любых взаимно простых чисел ,

,

где − функция Кармайкла, определяемая следующим образом:

, ; , если ;

, если − нечетное простое число;

,…, , если − каноническое разложение числа .

Замечание. Для чисел вида 2, 4, или , где − простое число, , имеет место равенство Во всех остальных случаях − собственный делитель числа и для них соотношение (2) улучшает теорему Эйлера.

Доказательство. См. Приложение. ∎

Следующее утверждение является обращением теоремы Ферма:

Теорема Люка (1876). Натуральное число является простым тогда и только тогда, когда существует число такое, что , но для любого простого делителя числа .

(Доказательство этой теоремы откладывается.)

Из Малой теоремы Ферма следует, что если нод , и , то − заведомо составное число. Вместе с тем существуют составные числа . для которых

.

Такие (составные) числа называют псевдопростыми.

Теорема Чиполлы . Существует бесконечно много -псевдопростых чисел.

Доказательство. Положим , где − нечетное простое число, взаимно простое с , и отметим, что − целое составное число, так как , а

− целые числа. Имеем

где

Допустим, что нод , . Тогда . Поскольку ), то 1) и . Если же нод , , то и | . В любом случае , и

∎

Пример. Для и получим и .

Замечание. Число может быть -псевдопростым для некоторого , но не быть таковым при другом . Однако существуют составные числа, которые являются -псевдопро- стыми при любом , взаимно простым с . Такие числа называют числами Кармайкла, или абсолютно псевдопростыми. Известно , что множество чисел Кармайкла бесконечно . Первое такое число равно .

Приведём одно утверждение, используемое в криптографии (в алгоритме ):

Теорема. Пусть , − различные простые числа, , − любое число, взаимно простое с . Тогда отображение

является взаимно однозначным на множестве , причем обратным к нему является отображение

,

где − число, удовлетворяющее сравнению .

Доказательство. Достаточно показать, что

,

рассматривая случаи: 1) и ; 2) , т.е. для некоторого , взаимно простого с ; 3) (этот случай аналогичен предыдущему, поэтому не рассматривается). Отметим, что для некоторого .

В первом случае имеем:

,

а во втором случае:

(здесь некоторое целое). ∎

Китайская теорема об остатках.

Число называется мультипликативным обратным к по модулю , если

. Очевидно, что существует тогда и только тогда, когда нод , . В этом случае в качестве можно взять любое число, сравнимое с по модулю , что непосредственно вытекает из теоремы Эйлера. В интервале , содержится в точности одно такое (действительно, ; соответствующее обозначим через . Другой способ вычисления (без привлечения функции ) основан на использовании расширенного алгоритма Евклида, в котором наряду с вычислением нод , также вычисляются числа и такие, что .

Китайская теорема об остатках. Пусть ,…, − любые попарно взаимно простые числа; , ,…, − любые числа; … . Тогда в интервале

[ , содержится число , удовлетворяющее сравнениям

(1) ,…, ,

причём единственное.

Доказательство. Построим искомое . Положим = … … , = (число существует, поскольку нод , , ,…, . Далее полагаем

.

Нетрудно проверить, что число удовлетворяет системе сравнений , поскольку

и при , . Если и удовлетворяет , то и удовлетворяет . Отсюда следует, что любое число , где , удовлетворяет . Одно из таких чисел попадает в интервал , . Допустим на минутку, что в этом интервале содержатся два числа: и , удовлетворяющие . Пусть, для определённости, . Поскольку число удовлетворяет системе сравнений

, …, ,

То делится без остатка на ,…, , и, следовательно, на . Так как , то и . Значит, в указанном интервале содержится в точности одно число , удовлетворяющее системе сравнений . ∎