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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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


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

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


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

Доказательства[править | править вики-текст]

С помощью теории чисел[править | править вики-текст]

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

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

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

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

или

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

или .

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

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

или

.

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

или


С помощью теории групп[править | править вики-текст]

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


См. также[править | править вики-текст]

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]