Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

a^{\varphi(m)} \equiv 1 \pmod m, если a и m взаимно просты, \varphi(n)функция Эйлера Теорема Эйлера (теория чисел)/рамка

Частным случаем этой теоремы при простом m является малая теорема Ферма.

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

Пусть x_1,...,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,...,x_{\varphi(m)} попарно различны по модулю m.

Перемножим все равенства x_i a \equiv x_j\pmod m. Получим:

x_1 ... x_{\varphi(m)} a^{\varphi(m)} = x_1 ... x_{\varphi(m)}\pmod m

или

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

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

a^{\varphi(m)}-1 = 0\pmod m или a^{\varphi(m)} = 1\pmod m.Шаблон:ЧТД


bg:Теорема на Ойлер da:Eulers sætninghe:משפט אוילר hu:Euler-Fermat-tétel id:Teorema Eulernl:Stelling van Euler sv:Eulers sats

Викия-сеть

Случайная вики