Задача
Докажите, что при любом целом a
a) a5 – a делится на 30;
б) a17 – a делится на 510;
в) a11 – a делится на 66;
г) a73 – a делится на 2·3·5·7·13·19·37·73.
Решение
a) Делимость на 2 очевидна, делимость на 5 следует из малой теоремы Ферма. Кроме того, a5 = a³·a² ≡ a·a² = a³ ≡ a (mod 3). б) Делимость на 2 очевидна, делимость на 17 следует из малой теоремы Ферма, делимость на 3 доказывается аналогично а). Кроме того,
a17 = (a5)³·a² ≡ a³·a² = a5 ≡ a (mod 5). в) Доказывается аналогично а). г) Делимость на 2, 3, 5, 73 доказывается аналогично б); a73 = (a7)10·a³ ≡ a10·a3 = a5·a6 ≡ a·a6 = a7 ≡ a (mod 7),
a73 = (a13)5·a8 ≡ a5·a8 = a13 ≡ a (mod 13), a73 = (a19)3·a16 ≡ a³·a16 = a19 ≡ a (mod 19), a73 = a37·a36 ≡ a·a36 = a37 ≡ a (mod 37).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь