Проверка кратности числа

[xyzman]

Необходимо убедиться в том, что число $a^5 - a$ кратно 5 (a - положительное целое)

В решении число $a^5 - a$ приводиться к виду:
$a^5 - a = (a - 1)a(a + 1)(a^2 + 1)$
после чего предлагается перебрать все подряд остатки от деления на 5, т.е. 0, 1, 2, 3, 4.
При этом приводятся следующие пояснения:
Если остаток равен 0, то кратен 5 второй множитель. Если остаток равен 1 или 4, то кратен 5
первый или третий множитель. Если же остаток равен 2 или 3, то кратен 5 четвертый множитель.

Ни как не могу понять почему такая проверка справедлива. Почему подстановка остатков от деления a на 5 доказывает кратность 5 числа $a^5 - a$. Может кто растолкует?

[ewert]

То, что $r$ есть остаток от деления на 5, означает ровно то, что $a=5m+r$ при некотором $m$. Вот это выражение для каждого конкретного $r$ и надо подставлять в указанный сомножитель, после чего всё очевидно.

Ну или есть достаточно очевидный общий факт: для степени числа остатком будет степень исходного остатка (точнее, остаток от степени остатка). И, скажем, $r^4-1$ для $r=1,2,3,4$ принимает значения $0,15,80,255$, т.е. в любом случае делится на 5.

[Батороев]

Можно также рассмотреть по Малой теореме Ферма:
$ a^5 - a = a(a^4 - 1) $, где либо $a$ , либо $a^4-1$ кратны $5$.

[xyzman]

Не понятен переход от

ewert в сообщении #186033 писал(а):

То, что r есть остаток от деления на 5, означает ровно то, что $a = 5m + r$ при некотором m.

к

ewert в сообщении #186033 писал(а):

Вот это выражение для каждого конкретного r и надо подставлять в указанный сомножитель, после чего всё очевидно.

Предлагаю подставить $a = 7m + r$ при некотором $m$. Да и проверку на кратность 5 проходит не само $a$, а $(a^5 - a)$.

[ewert]

Ну хорошо, тогда будем ещё формальнее. Если $f(a)$ -- некоторый многочлен с целыми коэффициентами, то

$f(a)\mod5=f(a\mod5)\mod5,$

где $\mod5$ -- операция взятия остатка от деления на 5 (утверждение верно, конечно, не только для пятёрки). В частности: $f(a)$ делится на 5 при всех $a$ тогда и только тогда, когда делится на 5 $f(r)$ для всех возможных остатков $r$. У нас $f(a)=a^5-a$; подставляеем все возможные остатки:

$f(0)=0;$
$f(1)=0;$
$f(2)=30;$
$f(3)=240;$
$f(4)=1020.$

Все делятся на 5, что и требуется.

[xyzman]

Ура-а-а-а! Дошло! Спасибо за помощь!