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

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

В теории чисел теорема Эйлера (также известная как теорема Ферма-Эйлера или теорема Эйлера о тотенте ) утверждает, что, если n и a являются взаимно простыми положительными целыми числами, то они конгруэнтны по модулю n , где обозначает функцию тотента Эйлера ; то есть ${\displaystyle a^{\varphi (n)}}$ ${\displaystyle 1}$ ${\displaystyle \varphi }$

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}.}$

В 1736 году Леонард Эйлер опубликовал доказательство малой теоремы Ферма ^[1] (высказанное Ферма без доказательства), которое представляет собой ограничение теоремы Эйлера на случай, когда n — простое число. Впоследствии Эйлер представил другие доказательства теоремы, кульминацией которых стала его статья 1763 года, в которой он доказал обобщение на случай, когда n не является простым. ^[2]

Верно и обратное утверждение теоремы Эйлера: если приведенное выше сравнение истинно, то и должно быть взаимно простым. ${\displaystyle a}$ ${\displaystyle n}$

Теорема далее обобщается некоторыми теоремами Кармайкла .

Теорему можно использовать для легкого уменьшения больших степеней по модулю . Например, рассмотрим поиск десятичной цифры , т.е. Целые числа 7 и 10 взаимно просты и . Итак, теорема Эйлера дает , и мы получаем . ${\displaystyle n}$ ${\displaystyle 7^{222}}$ ${\displaystyle 7^{222}{\pmod {10}}}$ ${\displaystyle \varphi (10)=4}$ ${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$ ${\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}}$

В общем, при уменьшении степени по модулю (где и взаимно просты) нужно работать по модулю в показателе степени : ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle a}$

если , то . ${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$ ${\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}$

Теорема Эйлера лежит в основе криптосистемы RSA , которая широко используется в интернет- коммуникациях. В этой криптосистеме используется теорема Эйлера, где n является произведением двух больших простых чисел , а безопасность системы основана на сложности факторизации такого целого числа.

Доказательства

1. Теорему Эйлера можно доказать, используя понятия теории групп : ^[3] Классы вычетов по модулю n , которые взаимно просты с n , образуют группу при умножении ( подробности см. В статье Мультипликативная группа целых чисел по модулю n ). Порядок этой группы равен φ ( n ) . Теорема Лагранжа утверждает, что порядок любой подгруппы конечной группы делит порядок всей группы, в данном случае φ ( n ) . Если a — любое число, взаимно простое с n , то a принадлежит к одному из этих классов вычетов, а его степени a , a ² , ..., a ^k по модулю n образуют подгруппу группы классов вычетов с a ^k ≡ 1 ( мод н ) . Теорема Лагранжа гласит, что k должно делить φ ( n ) , т.е. существует целое число M такое, что kM = φ ( n ) . Это означает, что

${\displaystyle a^{\varphi (n)}=a^{kM}=(a^{k})^{M}\equiv 1^{M}=1{\pmod {n}}.}$

2. Существует также прямое доказательство: ^{[4] [5]} Пусть R = { x ₁ , x ₂ , ... , x _{φ ( n )} } — приведенная система вычетов ( mod n ), и пусть a — любое целое число взаимно простой к n . Доказательство основано на фундаментальном факте, что умножение на a меняет местами x _i : другими словами, если ax _j ≡ ax _k (mod n ) , то j = k . (Этот закон сокращения доказан в статье Мультипликативная группа целых чисел по модулю n . ^[6] ) То есть множества R и aR = { ax ₁ , ax ₂ , ... , ax _{φ ( n )} } , рассматриваемые как множества классов соответствия ( mod n ) идентичны (как множества — они могут быть перечислены в разном порядке), поэтому произведение всех чисел в R конгруэнтно ( mod n ) произведению всех чисел в aR :

${\displaystyle \prod _{i=1}^{\varphi (n)}x_{i}\equiv \prod _{i=1}^{\varphi (n)}ax_{i}=a^{\varphi (n)}\prod _{i=1}^{\varphi (n)}x_{i}{\pmod {n}},}$и использование закона сокращения для отмены каждого x _i дает теорему Эйлера:

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}.}$

Смотрите также

• Функция Кармайкла
• критерий Эйлера
• Маленькая теорема Ферма
• Теорема Вильсона

Примечания

1. См.:
   • Леонард Эйлер (представлено: 2 августа 1736 г.; опубликовано: 1741 г.) «Theorematum quorundam ad numeros primos spectantium demostratio» (Доказательство некоторых теорем относительно простых чисел), Commentarii academiae scientiarum Petropolitanae , 8  : 141–146.
   • Более подробную информацию об этой статье, включая английский перевод, можно найти в: Архив Эйлера.
2. См.:
   • Л. Эйлер (опубликовано в 1763 г.) «Theoremata arithmetica nova Methodo Demonstrata» (Доказательство нового метода в теории арифметики), Novi Commentarii academiae scientiarum Petropolitanae , 8  : 74–104. Теорема Эйлера представлена ​​как «Теорема 11» на стр. 102. Эта статья была впервые представлена ​​​​в Берлинской академии 8 июня 1758 года и в Санкт-Петербургской академии 15 октября 1759 года. В этой статье общая функция Эйлера , не равна называется, но упоминается как «numerus partium ad N primarum» (количество частей, простых для N ; то есть количество натуральных чисел, которые меньше N и относительно просты с N ). ${\displaystyle \varphi (n)}$
   • Более подробную информацию об этой статье см.: Архив Эйлера.
   • Обзор работ Эйлера за годы, приведшие к созданию теоремы Эйлера, см.: Эд Сандифер (2005) «Доказательство Эйлера малой теоремы Ферма». Архивировано 28 августа 2006 г. в Wayback Machine .
3. Ирландия и Розен, корр. 1 к предложению 3.3.2
4. Харди и Райт, thm. 72
5. Ландау, тм. 75
6. См. лемму Безу.

Рекомендации

« Disquisitiones Arithmeticae» переведена с цицероновской латыни Гаусса на английский и немецкий языки. Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих; Кларк, Артур А. (переведенный на английский) (1986), Disquisitiones Arithemeticae (второе, исправленное издание) , Нью-Йорк: Springer , ISBN 0-387-96254-9
• Гаусс, Карл Фридрих; Мазер, Х. (переведено на немецкий язык) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) (второе издание) , Нью-Йорк: Челси, ISBN 0-8284-0191-8
• Харди, GH; Райт, Э.М. (1980), Введение в теорию чисел (пятое издание) , Оксфорд: Oxford University Press , ISBN 978-0-19-853171-5
• Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе издание) , Нью-Йорк: Springer , ISBN 0-387-97329-Х
• Ландау, Эдмунд (1966), Элементарная теория чисел , Нью-Йорк: Челси

Внешние ссылки

• Вайсштейн, Эрик В. «Теорема Эйлера о Тотенте». Математический мир .
• Теорема Эйлера-Ферма в PlanetMath