Тэарэма Эйлера, тэорыя лікаў

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

Тэарэма Эйлера ў тэорыі лікаў абвяшчае:


Калі a і m узаемна простыя, то a^{\varphi(m)} \equiv 1 \pmod m, дзе \varphi(m)функцыя Эйлера.


Частковым выпадкам тэарэмы Эйлера з'яўляецца малая тэарэма Ферма (пры простым m). У сваю чаргу, тэарэма Эйлера з'яўляецца следствам тэарэмы Лагранжа.

Доказы[правіць | правіць зыходнік]

З дапамогай тэорыі лікаў[правіць | правіць зыходнік]

Хай x_1, \dots, x_{\varphi(m)} — усе розныя натуральныя лікі, меншыя m і ўзаемна простыя з ім.

Разгледзім усе магчымыя здабыткі x_i a для ўсіх i ад 1 да \varphi(m)

Паколькі a ўзаемна просты з m і x_i ўзаемна просты з m, то і x_i a таксама ўзаемна просты з m, г. зн. x_i a \equiv x_j\pmod m для некаторага j.

Адзначым, што ўсе астачы x_i a пры дзяленні на m розныя. Сапраўды, хай гэта не так, то існуюць такія i_1 \neq i_2, што

x_{i_1} a \equiv x_{i_2} a\pmod m

або

(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.

Так як a ўзаемна просты з m, то апошняе роўнасць раўнасільная таму , што

x_{i_1} - x_{i_2} \equiv 0\pmod m или x_{i_1} \equiv x_{i_2}\pmod m.

Гэта супярэчыць таму, што лікі x_1, \dots, x_{\varphi(m)} парамі розныя па модулю m.

Перамножым ўсе параўнанні выгляду x_i a \equiv x_j\pmod m. Атрымаем:

x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m

або

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

Паколькі лік x_1 \cdots x_{\varphi(m)} ўзаемна просты з m, то апошняе параўнанне раўнасільнае таму, што

a^{\varphi(m)}-1 \equiv 0\pmod m

или

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

З дапамогай тэорыі груп[правіць | правіць зыходнік]

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

Гл. таксама[правіць | правіць зыходнік]