Олимпиадная задача по делимости: Делится ли 21ⁱ⁰ – 1 на 2200? Многочлены и теория чисел

 Первый способ.     21¹⁰– 1 = (21⁵– 1)(21⁵+ 1) = (21 – 1)(21⁴+ 21³+ 21²+ 21 + 1)(21 + 1)(21⁴– 21³+ 21²– 21 + 1) = = 20·22·(21⁴+ 21³ + 21² + 21 + 1)(21⁴– 21³ + 21² – 21 + 1).   Заметим, что сумма  21⁴+ 21³ + 21² + 21 + 1  делится на 5, так как она оканчивается цифрой 5. Следовательно, полученное произведение делится на  22·20·5 = 2200.  Второй способ.  2200 = 8·25·11.  Достаточно доказать, что  21¹⁰– 1  делится на 11, 8 и 25.      21¹⁰– 1 ≡ (–1)¹⁰– 1 = 0 (mod 11).      21¹⁰– 1 ≡ (–3)¹⁰– 1 = 9⁵– 1 ≡ 1⁵– 1 = 0 (mod 8).      21¹⁰– 1 ≡ (–4)¹⁰– 1 = 2²⁰– 1 = 1024² – 1 ≡ (–1)² – 1 = 0 (mod 25).

Да.