9.10. Указание. Возведите в куб обе части сравнения
. )5(mod1
4
≡а
9.11. Указание. Воспользуйтесь равенством
)()( bаааbа
рр
−+−=− и примените малую теорему Ферма.
9.12. 1) Указание. Если число
а не делится на 7, то из малой теоремы
Ферма следуют сравнения
и . Сло-
жив эти сравнения почленно, получаем
, что
противоречит условию.
)7(mod1
6
≡
т
а )7(mod1
6
≡
n
а
)7(mod2
66
≡+
пт
аа
9.13. Указание. С помощью малой теоремы Ферма докажите делимость
данного числа на
5 и на 13.
9.14. 1) Указание. Так как числа
а и b взаимно просты, то оба они на
11 делиться не могут. Если одно из них делится на 11, а другое не де-
лится, то утверждение очевидно. Если оба числа
а и b не делятся на 11,
из малой теоремы Ферма следует, что число
на 11 не делит-
ся. Остается заметить, что
.
1010
4 ba −
)2)(2(4
55551010
babаba −+=−
9.15. 1) Решение. Число
делится на 7 тогда и только тогда, ко-
гда имеет место сравнение
, которое равносильно
сравнению
. По малой теореме Ферма имеем сравнение
. Поэтому, если число п представить в виде
, где , то выполняется сравнение
, откуда следует, что сравнение
справедливо тогда и только тогда, когда справедливо
сравнение
. Непосредственная проверка показывает,
что среди чисел, удовлетворяющих двойному неравенству
92 −
п
)7(mod92 ≡
п
)7(mod22 ≡
п
)7(mod12
6
≡
rqn += 6 60 <≤ r
)7(mod22)2(2
6 rrqп
≡⋅=
)7(mod22 ≡
п
)7(mod22 ≡
r
60
r ,
последнему сравнению удовлетворяют лишь
1 и 4. Таким образом, ис-
ходное сравнение имеет место тогда и только тогда, когда число
п име-
ет вид
или . Так как в первом случае
, а во втором
16 += qп 46 += qп
1)2(3 +⋅= qп 1)12(3
+⋅= qп , окончательно имеем
. 13 += kп
219