Задача 73687

Темы:    [ Деление с остатком ] [ Разложение на множители ] [ НОД и НОК. Взаимная простота ]

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

Условие

Автор: Григорьев Д.Ю.

Пусть a, b, m, n – натуральные числа, причём числа a и b взаимно просты и  a > 1.
Докажите, что если  a^m + b^m  делится на  aⁿ + bⁿ,  то m делится на n.

Решение

  Мы докажем не только то, что m делится на n, то есть  m = kn,  но и то, что частное k нечётно. Предположим, что это не так и рассмотрим два случая.
  1)  m = kn + r,  где k нечётно, а  0 < r < n.  Тогда  a^m + b^m = a^kn+r + b^kn+r = a^r(a^kn + b^kn) + b^kn(b^r – a^r).
  Первое слагаемое делится на  aⁿ + bⁿ,  а второе – нет, так как b^kn взаимно просто с  aⁿ + bⁿ  и  0 < |b^r – a^r| < aⁿ + bⁿ.  Следовательно, сумма не делится на  aⁿ + bⁿ.
  2)  m = kn + r,  где k чётно, а  0 ≤ r < n.  Тогда  a^m + b^m = a^kn+r + b^kn+r = a^r(a^kn – b^kn) + b^kn(a^r + b^r).  Первое слагаемое делится на  a²ⁿ – b²ⁿ,  а значит, и на  aⁿ + bⁿ,  а второе – не делится на  aⁿ + bⁿ,  так как  a^r + b^r < aⁿ + bⁿ.  Следовательно, сумма снова не делится на  aⁿ + bⁿ.

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

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