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

Эта статья посвящена теореме Эйлера в теории чисел. Чтобы узнать о других значениях, см. Список тем, названных в честь Леонхарда Эйлера.

В теории чисел, теорема Эйлера (также известный как теорема Ферма-Эйлера или Эйлера totient теорема) утверждает, что если п и являются взаимно простыми положительными целыми числами, то, возведенное в силе totient из п конгруэнтно к одному, по модулю п, или:

${\ Displaystyle а ^ {\ varphi (п)} \ эквив 1 {\ pmod {п}}}$

где - функция Эйлера. В 1736 году Леонард Эйлер опубликовал свое доказательство маленькой теоремы Ферма, которое Ферма представил без доказательства. Впоследствии Эйлер представил другие доказательства теоремы, кульминацией которых стала «теорема Эйлера» в его статье 1763 года, в которой он попытался найти наименьший показатель степени, для которого малая теорема Ферма всегда верна. ${\ Displaystyle \ varphi (п)}$

Обратные теоремы Эйлера также верно: если выше сравнение верно, то и должен быть взаимно прост. ${\ 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} \ эквив 7 ^ {4 \ раз 55 + 2} \ эквив (7 ^ {4}) ^ {55} \ раз 7 ^ {2} \ эквив 1 ^ {55} \ раз 7 ^ {2} \ Equiv 49 \ Equiv 9 {\ pmod {10}}}$

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

если, то.${\ Displaystyle х \ эквив у {\ pmod {\ varphi (п)}}}$${\ Displaystyle а ^ {х} \ эквив а ^ {у} {\ pmod {п}}}$

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

• 1 Доказательства
• 2 См. Также
• 3 Примечания
• 4 ссылки
• 5 Внешние ссылки

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

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

2. Существует также прямое доказательство: пусть R = { x 1, x 2,..., x φ ( n) } - приведенная система вычетов ( mod n) и пусть a - любое целое число, взаимно простое с n. Доказательство основано на фундаментальном факте, что умножение на a переставляет x i: другими словами, если ax j ≡ ax k (mod n), то j = k. (Этот закон сокращения доказан в статье « Мультипликативная группа целых чисел по модулю n». ) То есть множества R и aR = { ax 1, ax 2,..., ax φ ( n) }, рассматриваемые как множества сравнения классы ( mod n) идентичны (как наборы - они могут быть перечислены в разном порядке), поэтому произведение всех чисел в R конгруэнтно ( mod n) произведению всех чисел в aR:

${\ Displaystyle \ prod _ {я = 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}}.}$

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

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

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

• Вайсштейн, Эрик У. "Теорема Тотиента Эйлера". MathWorld.
• Теорема Эйлера-Ферма в PlanetMath