Задание №177111: Турнир городов

2. [4] Натуральные числа a и b таковы, что an+1 + bn+1 делится на an + bn для бесконечного
множества различных натуральных n. Обязательно ли тогда a = b?
Б. Френкин
Ответ: обязательно.
an+1 + bn+1
Решение 1. Пусть, например, a > b. Дробь меньше a при всех натуральных n
an + bn
(очевидно после умножения на знаменатель), но стремится к a при n → ∞ (в самом деле, поделив
n
 b 
числитель и знаменатель на an и заметив, что   → 0 при n → ∞, получим, что числитель дроби
 a 
an+1 + bn+1
стремится к a, а знаменатель – к 1). Значит, a – 1 < < a при достаточно больших n и не
an + bn
может быть целым. Противоречие.
an+1 + bn+1
Решение 2. Пусть, например, a > b. Тогда b < < a при всех натуральных n (очевидно
an + bn
после умножения на знаменатель). Так как между b и a конечное число целых чисел, найдутся
am+1 + bm+1 ak+1 + bk+1
такие различные натуральные m и k, что = . Умножив на знаменатели и
am + bm ak + bk
m−k
 a 
приводя подобные, получим ambk(a – b) = akbm(a – b). Сократив на a – b, имеем   =1, откуда
 b 
либо a = b, либо m = k – противоречие.
Решение 3. Пусть наибольший общий делитель чисел a и b равен d, то есть a=ud, b=vd,
где u и v взаимно просты. Из условия, сократив на d, получаем, что d(un+1 + vn+1) делится на un + vn
для бесконечного множества натуральных n. Поскольку u и v взаимно просты, числа un+1 + vn+1 и
un + vn взаимно просты с u и v, а кроме того, могут иметь общим множителем максимум |v – u| (это
следует из того, что un+1 + vn+1 – u(un + vn) = vn(v – u)).
Но ненулевое число, не превосходящее d·|v – u|, не может делиться на un + vn для бесконечно
многих n. Значит, u=v, откуда a=b.