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

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

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

Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма:

Если $a$$a$ не делится на простое число $p$$p$, то $a^{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}p)$$a^{{p-1}}\equiv 1{\pmod p}$.

В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю $m$$m$.

ДоказательстваПравить

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

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

Рассмотрим все возможные произведения $x_{i}a$$x_i a$  для всех $i$$i$  от $1$$1$  до $\mathrm{\phi <!--\; \phi \; -->}(m)$$\varphi(m)$ .

Поскольку $a$$a$  взаимно просто с $m$$m$ , и $x_i$$x_{i}$  взаимно просто с $m$$m$ , то и $x_{i}a$$x_i a$  также взаимно просто с $m$$m$ , то есть $x_{i}a\equiv <!--\; \equiv \; -->x_j(\mathrm{mod}m)$$x_i a \equiv x_j\pmod m$  для некоторого $j$$j$ .

Отметим, что все остатки $x_{i}a$$x_i a$  при делении на $m$$m$  различны. Действительно, пусть это не так, тогда существуют такие $i_1\ne <!--\; \ne \; -->i_2$$i_1 \neq i_2$ , что

$x_{i_1}a\equiv <!--\; \equiv \; -->x_{i_2}a(\mathrm{mod}m)$$x_{i_1} a \equiv x_{i_2} a\pmod m$ 

или

$(x_{i_1}-<!--\; -\; -->x_{i_2})a\equiv <!--\; \equiv \; -->0(\mathrm{mod}m).$$(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.$ 

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

$x_{i_1}-<!--\; -\; -->x_{i_2}\equiv <!--\; \equiv \; -->0(\mathrm{mod}m)$$x_{i_1} - x_{i_2} \equiv 0\pmod m$  или $x_{i_1}\equiv <!--\; \equiv \; -->x_{i_2}(\mathrm{mod}m)$$x_{i_1} \equiv x_{i_2}\pmod m$ .

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

Перемножим все сравнения вида $x_{i}a\equiv <!--\; \equiv \; -->x_j(\mathrm{mod}m)$$x_i a \equiv x_j\pmod m$ . Получим:

$x_1\cdots <!--\; \cdots \; -->x_{\mathrm{\phi <!--\; \phi \; -->}(m)}{a}^{\mathrm{\phi <!--\; \phi \; -->}(m)}\equiv <!--\; \equiv \; -->x_1\cdots <!--\; \cdots \; -->x_{\mathrm{\phi <!--\; \phi \; -->}(m)}(\mathrm{mod}m)$$x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m$ 

или

$x_1\cdots <!--\; \cdots \; -->x_{\mathrm{\phi <!--\; \phi \; -->}(m)}(a^{\mathrm{\phi <!--\; \phi \; -->}(m)}-<!--\; -\; -->1)\equiv <!--\; \equiv \; -->0(\mathrm{mod}m)$$x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m$ .

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

$a^{\mathrm{\phi <!--\; \phi \; -->}(m)}-<!--\; -\; -->1\equiv <!--\; \equiv \; -->0(\mathrm{mod}m)$$a^{\varphi(m)}-1 \equiv 0\pmod m$ 

или

$a^{\mathrm{\phi <!--\; \phi \; -->}(m)}\equiv <!--\; \equiv \; -->1(\mathrm{mod}m).$$a^{\varphi(m)} \equiv 1\pmod m.$  ■

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

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

См. такжеПравить

• Список объектов, названных в честь Леонарда Эйлера

ЛитератураПравить

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.

СсылкиПравить

• Topics: Euler’s Theorem, Chinese Remainder Theorem, Amir Kamil, CS70, Fall 2003. UC Berkeley  (англ.)
• RSA and the Chinese remainder theorem / Discrete Mathematics for CS Lecture 12, Wagner, CS70, Fall 2003. UC Berkeley  (англ.)