Задача 73809

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

Сложность: 4- Классы: 7,8,9

Условие

Автор: Шлейфер Р.

Найдите наименьшее число вида   а)  |11^k – 5ⁿ|;   б)  |36^k – 5ⁿ|;   в)  |53^k – 37ⁿ|,  где k и n – натуральные числа.

Решение

  а) Если  11^k > 5ⁿ,  то число  |11^k – 5ⁿ|  оканчивается на 6; если  11^k < 5ⁿ,  то на 4.
Поскольку  |11² – 5³| = 4,  то 4 – наименьшее число вида  |11^k – 5ⁿ|.

  б) Число  |36^k – 5ⁿ|  оканчивается на 1 или на 9.
  Заметим, что  |36¹ – 5²| = 11,  и докажем, что 11 – наименьшее число такого вида, то есть что  |36^k – 5ⁿ|  не может равняться ни 1, ни 9.
  1) Если  36^k – 5ⁿ = 1,  то  (6^k – 1)(6^k + 1) = 5ⁿ.  Но  6^k + 1  не может быть степенью 5, так как оканчивается на 7.
  2) Если  5ⁿ – 36^k = 9,  то  5ⁿ = 9 + 36^k,  чего также не может быть, так как правая часть делится на 9, а левая – нет.

  в)  |53^k – 37ⁿ| = |(4·13 + 1)^k – (4·9 + 1)ⁿ|,  то есть делится на 4.
  С другой стороны,  |53^k – 37ⁿ| = |(6·9 – 1)^k – (4·9 + 1)ⁿ|.  Поэтому при делении такого числа на 9 в остатке могут получаться только 0, 2 и –2
  Наименьшее число, удовлетворяющее этим двум условиям – это  16 = 53 – 37.

Ответ

а)  4;   б)  11;   в)  16.

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

журнал
Название	"Квант"
год
Год	1974
выпуск
Номер	7
Задача
Номер	М274