Question

Даны различные натуральные числа x и y такие, что если к x прибавить наибольший де- литель y, отличный от y, то получится тот же результат, что и если к y прибавить наибольший делитель x, отличный от x. Докажите, что один из этих наибольших делителей делится на другой.

Answer 1

Пусть $x=bp$, где $b$ — наибольший собственный делитель $x$. Аналогично, $y=aq$. Без ограничения общности пусть $a> b$. По условию: $x+a = y+b,\; bp+a=aq+b \Leftrightarrow b(p-1) = a(q-1)$. Пусть $d>1$ есть общий делитель $b$ и $q-1$. Заметим, что $q<p$, в самом деле, пусть не так:$a-b = aq-bp\geq ap-bp = p(a-b)$, противоречие. Итак, $d\mid q-1$ и потому $d\leq q-1 <p-1$. Так мы нашли делитель $b$, меньший $p$. Значит, если он не равен 1, то $x/d>b$, противоречие. Значит, $d=1$. Следовательно, $b$ и $q-1$ взаимно просты, откуда $b\mid a$.