Докажите что выражение a17 2a16 a15 делится на a 1

Докажите что выражение a17 2a16 a15 делится на a 1

Докажите, что при любом целом a
a) a 5 – a делится на 30;
б) a 17 – a делится на 510;
в) a 11 – a делится на 66;
г) a 73 – a делится на 2·3·5·7·13·19·37·73.

Решение

a) Делимость на 2 очевидна, делимость на 5 следует из малой теоремы Ферма. Кроме того, a 5 = a³·a² ≡ a·a² = a³ ≡ a (mod 3).

б) Делимость на 2 очевидна, делимость на 17 следует из малой теоремы Ферма, делимость на 3 доказывается аналогично а). Кроме того,
a 17 = (a 5 )³·a² ≡ a³·a² = a 5 ≡ a (mod 5).

в) Доказывается аналогично а).

г) Делимость на 2, 3, 5, 73 доказывается аналогично б); a 73 = (a 7 ) 10 ·a³ ≡ a 10 ·a 3 = a 5 ·a 6 ≡ a·a 6 = a 7 ≡ a (mod 7),
a 73 = (a 13 ) 5 ·a 8 ≡ a 5 ·a 8 = a 13 ≡ a (mod 13), a 73 = (a 19 ) 3 ·a 16 ≡ a³·a 16 = a 19 ≡ a (mod 19), a 73 = a 37 ·a 36 ≡ a·a 36 = a 37 ≡ a (mod 37).

Источники и прецеденты использования

Источник