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

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

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

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

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

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

Теорему можно использовать для легкого уменьшения больших степеней по модулю $n$ . Например, рассмотрите возможность поиска десятичной цифры единицы. $7^{222}$ , то есть $7^{222}{\pmod {10}}$ . Целые числа 7 и 10 являются взаимно простыми, а $\varphi (10)=4$ . Итак, теорема Эйлера дает $7^{4}\equiv 1{\pmod {10}}$ , и мы получаем $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}}$ .

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

если

x\equiv y{\pmod {\varphi (n)}}

, затем

a^{x}\equiv a^{y}{\pmod {n}}

.

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

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

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

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

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

\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

дает теорему Эйлера:

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

См. также

Примечания

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

Ссылки

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

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

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

[1] См.:
Леонард Эйлер (представлено: 2 августа 1736 г.; опубликовано: 1741 г.) «Доказательство некоторых теорем относительно простых чисел» , Commentarii academye scientiarum Petropolitanae , 8 : 141–146.

Более подробную информацию об этой статье, включая английский перевод, можно найти в: Архив Эйлера .

[2] Леонард Эйлер (представлено: 2 августа 1736 г.; опубликовано: 1741 г.) «Доказательство некоторых теорем относительно простых чисел» , Commentarii academye scientiarum Petropolitanae , 8 : 141–146.

[3] Более подробную информацию об этой статье, включая английский перевод, можно найти в: Архив Эйлера .

[2] См.:
Л. Эйлер (опубликовано в 1763 г.) «Theoremata arithmetica nova Methodo Demonstrata» (Доказательство нового метода в теории арифметики), Novi Commentarii academiae scientiarum Petropolitanae , 8 : 74–104. Теорема Эйлера представлена как «Теорема 11» на странице 102. Эта статья была впервые представлена в Берлинской академии 8 июня 1758 года и в Санкт-Петербургской академии 15 октября 1759 года. В этой статье общая функция Эйлера $\varphi (n)$ , не называется, но упоминается как «numerus partium ad N primarum» (количество частей, простых с N ; то есть количество натуральных чисел, которые меньше N и относительно просты с N ).

Более подробную информацию об этой статье см.: Архив Эйлера .

Обзор работ Эйлера за годы, приведшие к созданию теоремы Эйлера, см.: Эд Сандифер (2005) «Доказательство Эйлера малой теоремы Ферма». Архивировано 28 августа 2006 г. в Wayback Machine.

[5] Л. Эйлер (опубликовано в 1763 г.) «Theoremata arithmetica nova Methodo Demonstrata» (Доказательство нового метода в теории арифметики), Novi Commentarii academiae scientiarum Petropolitanae , 8 : 74–104. Теорема Эйлера представлена как «Теорема 11» на странице 102. Эта статья была впервые представлена в Берлинской академии 8 июня 1758 года и в Санкт-Петербургской академии 15 октября 1759 года. В этой статье общая функция Эйлера $\varphi (n)$ , не называется, но упоминается как «numerus partium ad N primarum» (количество частей, простых с N ; то есть количество натуральных чисел, которые меньше N и относительно просты с N ).

[6] Более подробную информацию об этой статье см.: Архив Эйлера .

[7] Обзор работ Эйлера за годы, приведшие к созданию теоремы Эйлера, см.: Эд Сандифер (2005) «Доказательство Эйлера малой теоремы Ферма». Архивировано 28 августа 2006 г. в Wayback Machine.

[3] Ирландия и Розен, корр. 1 к предложению 3.3.2

[4] Харди и Райт, thm. 72

[5] Ландау, THM. 75

[6] См . лемму Безу .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]