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

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

Если <math>a</math> и <math>m</math> взаимно просты, то <math>a^{\varphi(m)} \equiv 1 \pmod m</math>, где <math>\varphi(m)</math> — функция Эйлера.

Частным случаем теоремы Эйлера является малая теорема Ферма (при простом m). В свою очередь, теорема Эйлера является следствием теоремы Лагранжа.

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

С помощью теории чисел

Пусть <math>x_1, \dots, x_{\varphi(m)}</math> — все различные натуральные числа, меньшие <math>m</math> и взаимно простые с ним.

Рассмотрим все возможные произведения <math>x_i a</math> для всех <math>i</math> от <math>1</math> до <math>\varphi(m)</math>.

Поскольку <math>a</math> взаимно просто с <math>m</math> и <math>x_i</math> взаимно просто с <math>m</math>, то и <math>x_i a</math> также взаимно просто с <math>m</math>, то есть <math>x_i a \equiv x_j\pmod m</math> для некоторого <math>j</math>.

Отметим, что все остатки <math>x_i a</math> при делении на <math>m</math> различны. Действительно, пусть это не так, то существуют такие <math>i_1 \neq i_2</math>, что

<math>x_{i_1} a \equiv x_{i_2} a\pmod m</math>

или

<math>(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.</math>

Так как <math>a</math> взаимно просто с <math>m</math>, то последнее равенство равносильно тому, что

<math>x_{i_1} - x_{i_2} \equiv 0\pmod m</math> или <math>x_{i_1} \equiv x_{i_2}\pmod m</math>.

Это противоречит тому, что числа <math>x_1, \dots, x_{\varphi(m)}</math> попарно различны по модулю <math>m</math>.

Перемножим все сравнения вида <math>x_i a \equiv x_j\pmod m</math>. Получим:

<math>x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m</math>

или

<math>x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m</math>.

Так как число <math>x_1 \cdots x_{\varphi(m)}</math> взаимно просто с <math>m</math>, то последнее сравнение равносильно тому, что

<math>a^{\varphi(m)}-1 \equiv 0\pmod m</math>

или

<math>a^{\varphi(m)} \equiv 1\pmod m.</math> ■

С помощью теории групп

Рассмотрим мультипликативную группу <math>\mathbb Z_n^*</math> обратимых элементов кольца вычетов <math>\mathbb Z_n</math>. Её порядок равен <math>\varphi(n)</math> согласно определению функции Эйлера. Поскольку число <math>a</math> взаимно просто с <math>n</math>, соответствующий ему элемент <math>\overline a</math> в <math>\mathbb Z_n</math> является обратимым и принадлежит <math>\mathbb Z_n^*</math>. Элемент <math>\overline{a}\in \mathbb Z_n^*</math> порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит <math>\varphi(n)</math>, отсюда <math>\overline a^{\varphi(n)}=\overline 1</math>. ■

См. также

• Малая теорема Ферма
• Список объектов, названных в честь Леонардо Эйлера
• Теорема Эйлера для многогранников
• Теорема Эйлера (планиметрия)
• Функция Эйлера

Ссылки

• [www.cs.berkeley.edu/~kamil/teaching/fa03/101003.pdf Topics: Euler’s Theorem, Chinese Remainder Theorem], Amir Kamil, CS70, Fall 2003. UC Berkeley  (англ.)
• [www.cs.berkeley.edu/~daw/teaching/cs70-f03/Notes/lecture12b.pdf RSA and the Chinese remainder theorem] / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley  (англ.)

Отрывок, характеризующий Теорема Эйлера (теория чисел)

Княжна пустила.
– И вы!
Анна Михайловна не послушалась его.
– Пустите, я вам говорю. Я беру всё на себя. Я пойду и спрошу его. Я… довольно вам этого.
– Mais, mon prince, [Но, князь,] – говорила Анна Михайловна, – после такого великого таинства дайте ему минуту покоя. Вот, Пьер, скажите ваше мнение, – обратилась она к молодому человеку, который, вплоть подойдя к ним, удивленно смотрел на озлобленное, потерявшее всё приличие лицо княжны и на перепрыгивающие щеки князя Василья.
– Помните, что вы будете отвечать за все последствия, – строго сказал князь Василий, – вы не знаете, что вы делаете.
– Мерзкая женщина! – вскрикнула княжна, неожиданно бросаясь на Анну Михайловну и вырывая портфель.
Князь Василий опустил голову и развел руками.
В эту минуту дверь, та страшная дверь, на которую так долго смотрел Пьер и которая так тихо отворялась, быстро, с шумом откинулась, стукнув об стену, и средняя княжна выбежала оттуда и всплеснула руками.
– Что вы делаете! – отчаянно проговорила она. – II s'en va et vous me laissez seule. [Он умирает, а вы меня оставляете одну.]
Старшая княжна выронила портфель. Анна Михайловна быстро нагнулась и, подхватив спорную вещь, побежала в спальню. Старшая княжна и князь Василий, опомнившись, пошли за ней. Через несколько минут первая вышла оттуда старшая княжна с бледным и сухим лицом и прикушенною нижнею губой. При виде Пьера лицо ее выразило неудержимую злобу.
– Да, радуйтесь теперь, – сказала она, – вы этого ждали.
И, зарыдав, она закрыла лицо платком и выбежала из комнаты.
За княжной вышел князь Василий. Он, шатаясь, дошел до дивана, на котором сидел Пьер, и упал на него, закрыв глаза рукой. Пьер заметил, что он был бледен и что нижняя челюсть его прыгала и тряслась, как в лихорадочной дрожи.
– Ах, мой друг! – сказал он, взяв Пьера за локоть; и в голосе его была искренность и слабость, которых Пьер никогда прежде не замечал в нем. – Сколько мы грешим, сколько мы обманываем, и всё для чего? Мне шестой десяток, мой друг… Ведь мне… Всё кончится смертью, всё. Смерть ужасна. – Он заплакал.
Анна Михайловна вышла последняя. Она подошла к Пьеру тихими, медленными шагами.
– Пьер!… – сказала она.
Пьер вопросительно смотрел на нее. Она поцеловала в лоб молодого человека, увлажая его слезами. Она помолчала.
– II n'est plus… [Его не стало…]
Пьер смотрел на нее через очки.
– Allons, je vous reconduirai. Tachez de pleurer. Rien ne soulage, comme les larmes. [Пойдемте, я вас провожу. Старайтесь плакать: ничто так не облегчает, как слезы.]
Она провела его в темную гостиную и Пьер рад был, что никто там не видел его лица. Анна Михайловна ушла от него, и когда она вернулась, он, подложив под голову руку, спал крепким сном.