Задача 60653

Темы:    [ Деление с остатком ] [ Разложение на множители ] [ Арифметика остатков (прочее) ] [ Малая теорема Ферма ]

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

Условие

Докажите, что
  а)  2⁴¹ + 1  делится на 83;
  б)  2⁷⁰ + 3⁷⁰  делится на 13;
  в)  2⁶⁰ – 1  делится на 20801.

Решение

  а)  2⁹ = 512 ≡ 14 (mod 83),  2¹⁸ ≡ 196 ≡ 30,  2³⁶ ≡ 900 ≡ 70 ≡ –13,  2⁴¹ ≡ –13·32 ≡ –416 ≡ –1.

  б)  2⁷⁰ + 3⁷⁰ = 4³⁵ + 9³⁵  делится на  4 + 9 = 13.

  в)  20801 = 11·31·61.
  Первый способ.  2⁶⁰ – 1  делится на  2¹⁰ – 1 = (2⁵ – 1)(2⁵ + 1) = 31·33.  Это число делится на 31 и на 11. Кроме того,   2⁶ ≡ 3 (mod 61),  2³⁰ ≡ 243 ≡ –1,
2⁶⁰ ≡ 1.
  Второй способ. Согласно малой теореме Ферма (см. задачу 60736)  2⁶⁰ – 1  делится на 61,  2³⁰ – 1  делится на 31,  2¹⁰ – 1  делится на 11. Поэтому
2⁶⁰ – 1  делится на все эти числа.

Замечания

В п. а) школьники, знакомые с квадратичными вычетами могут рассуждать так:  (2⁴¹ – 1)(2⁴¹ + 1) = 2⁸² – 1  делится на 83 по малой теореме Ферма. Двойка не является квадратичным вычетом по модулю 83, поэтому  2⁴¹ – 1  на 83 не делится. Значит, на 83 делится  2⁴¹ + 1.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	2
Название	Делимость
Тема	Теория чисел. Делимость (прочее)
задача
Номер	04.027