- Теорема Эйлера (теория чисел)
-
Теоре́ма Э́йлера в теории чисел гласит:
Если и взаимно просты, то , где — функция Эйлера.
Частным случаем теоремы Эйлера является малая теорема Ферма (при простом m). В свою очередь, теорема Эйлера является следствием теоремы Лагранжа.Содержание
Доказательства
С помощью теории чисел
Пусть — все различные натуральные числа, меньшие и взаимно простые с ним.
Рассмотрим всевозможные произведения для всех от до .
Поскольку взаимно просто с и взаимно просто с , то и также взаимно просто с , то есть для некоторого .
Отметим, что все остатки при делении на различны. Действительно, пусть это не так, то существуют такие , что
или
Так как взаимно просто с , то последнее равенство равносильно тому, что
- или .
Это противоречит тому, что числа попарно различны по модулю .
Перемножим все сравнения вида . Получим:
или
- .
Так как число взаимно просто с , то последнее сравнение равносильно тому, что
или
С помощью теории групп
Рассмотрим мультипликативную группу обратимых элементов кольца вычетов . Её порядок равен согласно определению функции Эйлера. Поскольку число взаимно просто с , соответствующий ему элемент в является обратимым и принадлежит . Элемент порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит , отсюда . ■
См. также
Для улучшения этой статьи желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
- Проставив сноски, внести более точные указания на источники.
Категории:- Теория чисел
- Теоремы
Wikimedia Foundation. 2010.