Задача 116450

Темы:    [ Делимость чисел. Общие свойства ] [ Арифметика остатков (прочее) ] [ Разложение на множители ]

Сложность: 2+ Классы: 8,9,10

Условие

Автор: Фольклор

Делится ли число  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).

Ответ

Да.

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

олимпиада
Название	Московская математическая регата
год
Год	2011/12
класс
	1
Класс	9
задача
Номер	9.2.3