Разделы 
Дополнительно
Задача по математике - 3053
2019-05-06 
Теорема Эйлера. Пусть $N$ есть какое-то целое число и $r$ - число чисел ряда $1, 2, 3, \cdots, N - 1$, взаимно простых с $N$. Доказать, что если а есть произвольное целое число, взаимно простое с $N$, то разность $a^{ r} - 1$ делится на $N$.
Решение:
Доказательство теоремы Эйлера совершенно» аналогично первому доказательству теоремы Ферма; $r$ чисел, меньших $N$ и взаимно простых с $N$, мы обозначим через $k_1, k_2, k_3, \cdots, к_r$. Рассмотрим $r$ чисел $k_1a, k_2a, \cdots, k_ra$. Все они взаимно просты с $N$ (ибо $a$ взаимно просто с $N$ по условию задачи), и все они дают при делении на $N$ различные остатки (это доказывается в точности так же, как в решении задачи 3052). Отсюда следует, что
$k_1a = q_1N + a_1, k_2a = q_2N + a_2, \cdots, k_ra = q_rN + a_r$,
где $a_1, a_2, \cdots, a_r$ - это те же числа $k_1, k_2, \cdots, k_r$, только расположенные в другом порядке. Перемножив все наши равенства, получим:
$k_1k_2 \cdots k_ra^r = MN + a_1a_2 \cdots a_r, k_1k_2 \cdots k_r(a^r - 1) = MN$,
откуда и следует, что число $a^r - 1$ делится на $N$.
Теорема Эйлера. Пусть $N$ есть какое-то целое число и $r$ - число чисел ряда $1, 2, 3, \cdots, N - 1$, взаимно простых с $N$. Доказать, что если а есть произвольное целое число, взаимно простое с $N$, то разность $a^{ r} - 1$ делится на $N$.
Решение:
Доказательство теоремы Эйлера совершенно» аналогично первому доказательству теоремы Ферма; $r$ чисел, меньших $N$ и взаимно простых с $N$, мы обозначим через $k_1, k_2, k_3, \cdots, к_r$. Рассмотрим $r$ чисел $k_1a, k_2a, \cdots, k_ra$. Все они взаимно просты с $N$ (ибо $a$ взаимно просто с $N$ по условию задачи), и все они дают при делении на $N$ различные остатки (это доказывается в точности так же, как в решении задачи 3052). Отсюда следует, что
$k_1a = q_1N + a_1, k_2a = q_2N + a_2, \cdots, k_ra = q_rN + a_r$,
где $a_1, a_2, \cdots, a_r$ - это те же числа $k_1, k_2, \cdots, k_r$, только расположенные в другом порядке. Перемножив все наши равенства, получим:
$k_1k_2 \cdots k_ra^r = MN + a_1a_2 \cdots a_r, k_1k_2 \cdots k_r(a^r - 1) = MN$,
откуда и следует, что число $a^r - 1$ делится на $N$.
