НОД решений диофантового уравнения

[Shadow]

Пусть $a,b$ - натуральные числа, такие, что $\dfrac{a+1}{b}+\dfrac{b+1}{a}$ - целое.
Докажите, что $\gcd(a,b) \le \sqrt{a+b}$

[Shadow]

UPD: Тот случай, когда кажется что получилась хорошая задача, а еще неможко подумав оказывается почти тривиальная. Ну ладно, пусть стоит.

[Утундрий]

Тот случай, когда хочется прибавить двойку и выражение действительно упрощается. Но что дальше - не ясно.

[Shadow]

Утундрий в сообщении #1604176 писал(а):

Но что дальше - не ясно.

Оказывается что это - известная задача специалистам по ТЧ и предложили доказать, что $\gcd(a,b)=\sqrt{\dfrac{a+b}{q}}, \; q \in \{1,2,3,5\}$

[Утундрий]

Ну, если добавить двойку, это никак не затронет условие целостности (на самом деле - натуральности). Получится, что натуральным должно быть

$$\dfrac{(a+b)(a+b+1)}{ab}$$

Значит, один из множителей в числителе - чётный, значит, или $a$ или $b$ - чётно... Такая возня предполагается или есть вундерметод?

[Shadow]

Утундрий в сообщении #1604189 писал(а):

Значит, один из множителей в числителе - чётный, значит, или $a$ или $b$ - чётно...

Совсем не обязательно, напр. $a=21,b=77$

[Утундрий]

А, точно, двойку же не нужно сокращать, она натуральность не портит.

[Shadow]

Утундрий в сообщении #1604189 писал(а):

Такая возня предполагается или есть вундерметод?

Да никакая возня, а вундерметод заключается в том, чтобы обозначить $a=dm,b=dn,\; \gcd(m,n)=1$

Тогда условие $d \le \sqrt{dm+dn}$ равносильно $d \le m+n$

Поставить эти значения в вашей же формуле,

Утундрий в сообщении #1604189 писал(а):

$$\dfrac{(a+b)(a+b+1)}{ab}$$

сократить один раз на $d$, и ..... сократить еще один раз на $d$.

[Утундрий]

Shadow в сообщении #1604202 писал(а):

сократить один раз на $d$, и ..... сократить еще один раз на $d$.

Почему возможно второе сокращение?

[Leeb]

Shadow в сообщении #1604186 писал(а):

Утундрий в сообщении #1604176 писал(а):

Но что дальше - не ясно.

Оказывается что это - известная задача специалистам по ТЧ и предложили доказать, что $\gcd(a,b)=\sqrt{\dfrac{a+b}{q}}, \; q \in \{1,2,3,5\}$

Для q = 1 (исходная задача) вроде бы можно так рассуждать:
Сложим $\dfrac{a+1}{b}+\dfrac{b+1}{a} = \dfrac{a^2+a+b^2+b}{ab}=\dfrac{(a+b)(a+b+1)}{ab}-2$. Теперь положим $\gcd(a,b) = d,\ a = kd, b=ld$:
$\dfrac{(kd+ld)(kd+ld+1)}{kld^2} = \dfrac{(k+l)(kd+ld+1)}{kld} $. Отсюда видно, что $k+l$ обязано делиться на d, поскольку вторая скобка очевидно не делится на d. При этом, $a+b = kd+ld=(k+l)d=cd^2$, поэтому $d = \sqrt{(a+b)/c}$

[mathematician123]

Если в натуральных числах выполнено

$$\frac{a + 1}{b} + \frac{b + 1}{a} = c$$

то

$$a^2 + b^2 + a + b = cab$$

Отсюда сразу следует, что $\gcd(a, b)^2 \mid a + b$.

Shadow в сообщении #1604186 писал(а):

Оказывается что это - известная задача специалистам по ТЧ и предложили доказать, что $\gcd(a,b)=\sqrt{\dfrac{a+b}{q}}, \; q \in \{1,2,3,5\}$

А это интересно. Прыжками Виета можно доказать, что $c = 3$ или $c = 4$. Для каждого из этих значений $c$ получится уравнение Пелля. Но не очень понятно как это поможет.

[KhAl]

Ну так
$(a+b)(a+b+1) = (c+2)ab$
$(dm+dn)(dm+dn+1)=(c+2)d^2mn$
$(m+n)(dm+dn+1) = (c+2)dmn$
Так как $m + n \perp mn$ и $dm + dn + 1 \perp d$, то
$m+n = q d$, $dm + dn + 1 = r mn$, где $qr = c+2$. Остался перебор.

[Shadow]

mathematician123 в сообщении #1604220 писал(а):

А это интересно. Прыжками Виета можно доказать, что $c = 3$ или $c = 4$. Для каждого из этих значений $c$ получится уравнение Пелля. Но не очень понятно как это поможет.

Моя попытка:
Пусть $a=dx,b=dy,\gcd(x,y)=1$. Уже доказано, что $d \mid x+y$. Условие $\gcd(a,b)=\sqrt{\dfrac{a+b}{q}}$ равносилно $d=\dfrac{x+y}{q}$

Или, $a=\dfrac{x(x+y)}{q},b=\dfrac{y(x+y)}{q}$

Подставив данные значения в стартовом выражении, получаем $\dfrac{x^2+y^2+q}{xy}$ - целое. Тут для любых $x,y$ можно подобрать подходящее $q$, но вряд ли будет вполнятся $q \mid x+y$.

Добавим двойку: $\dfrac{(x+y)^2+q}{xy}$ - целое. И не только целое, но и делящееся на $q$. (т.к числитель должен делится на $q$, а знаменатель взаимнопростой с $q$ - если $x,q$ имею общий делитель, то и $y$ должен иметь такой же делитель, что противоречит взаимной простоты $x,y$

Приходим к
$(x+y)^2+q=kqxy \quad(***)$

$x^2-(kq-2)yx+y^2+q=0$

Стандартная техника для Vieta jumping: Пусть для фиксиранных $k,q$ есть минимальное решение $(x_1,y)$, где $y \le x_1\le x_2$. Из этого следует

$(x_1-y)(x_2-y) \ge 0$

Дальше формулы Виета, неравенство сводится к

$y^2(kq-4)<=q$

Условие $kq>4$ немедленно следует из $(***)$

Небольшой перебор и все.

[Andrey A]

Shadow в сообщении #1604162 писал(а):

$\dfrac{a+1}{b}+\dfrac{b+1}{a}$ - целое.

Решения укладываются в две последовательности

$$\dfrac{a_n}{b_n}=\dfrac{1}{1},\dfrac{2}{1},\dfrac{6}{2},...,\dfrac{a_{n+1}=4a_n-b_n-1}{b_{n+1}=a_n},...$$

$$=\dfrac{2}{2},\dfrac{3}{2},\dfrac{6}{3},...,\dfrac{a_{n+1}=3a_n-b_n-1}{b_{n+1}=a_n},...$$

Отношение $\dfrac{a+b}{\gcd(a,b)^2}$ в первом случае образует период $(2,3)$, во втором — $(1,5).$ Доказывать это неинтересно. А вот что нет других решений — да, требует доказательства. Их вообще-то полно, но все имеют начальной дробью $\dfrac{0}{0}$ и, как следствие, отрицательные значения $a_n,b_n$ (всё это выходит за рамки условия). Думаю, нужно составить обратное рекуррентное правило и показать, что любая последовательность начинается с пары $a_1=b_1.$ А ненулевых таких всего две, это ясно.