`101^(12)-64^2` кратно `99.`

Задача: проверить, кратно ли 99 число 101^12 − 64^2. Поскольку 99 = 9 · 11 и gcd(9, 11) = 1, достаточно проверить делимость по mod 9 и mod 11. 1) Модуль 9: - 101 ≡ 2 (mod 9), значит 101^12 ≡ 2^12 (mod 9). - Так как 2^3 ≡ 8 ≡ -1 (mod 9), имеем 2^12 = (2^3)^4 ≡ (-1)^4 ≡ 1 (mod 9). - 64 ≡ 1 (mod 9), поэтому 64^2 ≡ 1 (mod 9). - Следовательно 101^12 − 64^2 ≡ 1 − 1 ≡ 0 (mod 9). 2) Модуль 11: - 101 ≡ 2 (mod 11), значит 101^12 ≡ 2^12 (mod 11). - 2^5 ≡ -1 (mod 11) (потому что 2^5 = 32 ≡ 10 ≡ -1), значит 2^10 ≡ 1 (mod 11). - Тогда 2^12 ≡ 2^10 · 2^2 ≡ 1 · 4 ≡ 4 (mod 11). - 64 ≡ 9 (mod 11), поэтому 64^2 ≡ 9^2 = 81 ≡ 4 (mod 11). - Следовательно 101^12 − 64^2 ≡ 4 − 4 ≡ 0 (mod 11). Так как число делится и на 9, и на 11, а 9 и 11 взаимно просты, оно делится и на 99. Ответ: да, 101^12 − 64^2 кратно 99.