Теоре́ма Э́йлера в теории чисел гласит:
Если и взаимно просты, то , где — функция Эйлера.
Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма:
Если не делится на простое число , то .
В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю .
Доказательства
С помощью теории чисел
Пусть — все различные натуральные числа, меньшие и взаимно простые с ним.
Рассмотрим все возможные произведения для всех от до .
Поскольку взаимно просто с , и взаимно просто с , то и также взаимно просто с , то есть для некоторого .
Отметим, что все остатки при делении на различны. Действительно, пусть это не так, тогда существуют такие , что
или
Так как взаимно просто с , то последнее равенство равносильно тому, что или . Это противоречит тому, что числа попарно различны по модулю .
Перемножим все сравнения вида . Получим:
или . Так как число взаимно просто с , то последнее сравнение равносильно тому, что
или
С помощью теории групп
Рассмотрим мультипликативную группу обратимых элементов кольца вычетов . Её порядок равен согласно определению функции Эйлера. Поскольку число взаимно просто с , соответствующий ему элемент в является обратимым и принадлежит . Элемент порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит , отсюда .
См. также Список объектов, названных в честь Леонарда Эйлера
Литература
Ссылки Topics: Euler’s Theorem, Chinese Remainder Theorem, Amir Kamil, CS70, Fall 2003. UC Berkeley RSA and the Chinese remainder theorem / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley
Категория:Теория чисел Эйлера (теория чисел) Категория:Объекты, названные в честь Леонарда Эйлера