|
|
 |
Условие
Докажите, что при любом целом 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).
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 4 |
| Название | Арифметика остатков |
| Тема | Деление с остатком. Арифметика остатков |
| параграф | |
| Номер | 4 |
| Название | Теоремы Ферма и Эйлера |
| Тема | Малая теорема Ферма |
| задача | |
| Номер | 04.157 |
