ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66741
Темы:    [ Теория чисел. Делимость (прочее) ]
[ Многочлены (прочее) ]
[ НОД и НОК. Взаимная простота ]
[ Тождественные преобразования ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Натуральные числа $a$ и $b$ таковы, что $a^{n+1}+b^{n+1}$ делится на $a^n+b^n$ для бесконечного множества различных натуральных $n$. Обязательно ли тогда $a=b$?

Решение

Решение 1.

Пусть, например, $a < b$. Дробь $\dfrac{a^{n+1}+b^{n+1}}{a^n+b^n}$ меньше $a$ при всех натуральных $n$ (очевидно после умножения на знаменатель), но стремится к $a$ при $n\to\infty$ (в самом деле, поделив числитель и знаменатель на $a^n$ и заметив, что $\left(\frac{b}{a}\right)^n\to\infty$ при $n \to \infty$, получим, что числитель дроби стремится к $a$, а знаменатель – к $1$). Значит, $a-1 < \frac{a^{n+1}+b^{n+1}}{a^n+b^n} < a$ при достаточно больших $n$ и не может быть целым. Противоречие.

Решение 2.

Пусть, например, $a < b$. Тогда $b < \dfrac{a^{n+1}+b^{n+1}}{a^n+b^n} < a$ при всех натуральных $n$ (очевидно после умножения на знаменатель). Так как между $b$ и $a$ конечное число целых чисел, найдутся такие различные натуральные $m$ и $k$, что $\dfrac{a^{m+1}+b^{m+1}}{a^m+b^m} =\dfrac{a^{k+1}+b^{k+1}}{a^k+b^k}$. Умножив на знаменатели и приводя подобные, получим $a^mb^k(a-b)=a^kb^m(a-b)$. Сократив на $a-b$, имеем $\left(\frac{a}{b}\right)^{m-k}=1$, откуда либо $a=b$, либо $m=k$ – противоречие.

Решение 3.

Пусть наибольший общий делитель чисел $a$ и $b$ равен $d$, то есть $a=ud$, $b=vd$, где $u$ и $v$ взаимно просты. Из условия, сократив на $d$, получаем, что $d(u^{n+1}+v^{n+1})$ делится на $u^n+v^n$ для бесконечного множества натуральных $n$. Поскольку $u$ и $v$ взаимно просты, числа $u^{n+1}+v^{n+1}$ и $u^n+v^n$ взаимно просты с $u$ и $v$, а кроме того, могут иметь общим множителем максимум $|v-u|$ (это следует из того, что $u^{n+1}+v^{n+1}-u(u^n+v^n)=v^n(v-u))$.

Но ненулевое число, не превосходящее $d\cdot |v-u|$, не может делиться на $u^n+v^n$ для бесконечно многих $n$. Значит, $u=v$, откуда $a=b$.

Ответ

обязательно.

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

олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .