Теорема Эйлера (теория чисел)

Теоре́ма Э́йлера в теории чисел гласит:

Если и взаимно просты, то , где функция Эйлера.

Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма:

Если не делится на простое число , то .

В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю .

Доказательства править

С помощью теории чисел править

Пусть   — все различные натуральные числа, меньшие   и взаимно простые с ним.

Рассмотрим все возможные произведения   для всех   от   до  .

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

Отметим, что все остатки   при делении на   различны. Действительно, пусть это не так, тогда существуют такие  , что

 

или

 

Так как   взаимно просто с  , то последнее равенство равносильно тому, что

  или  .

Это противоречит тому, что числа   попарно различны по модулю  .

Перемножим все сравнения вида  . Получим:

 

или

 .

Так как число   взаимно просто с  , то последнее сравнение равносильно тому, что

 

или

 

С помощью теории групп править

Рассмотрим мультипликативную группу   обратимых элементов кольца вычетов  . Её порядок равен   согласно определению функции Эйлера. Поскольку число   взаимно просто с  , соответствующий ему элемент   в   является обратимым и принадлежит  . Элемент   порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит  , отсюда  .

См. также править

Литература править

  • Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.

Ссылки править