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

Пусть , где — наибольший собственный делитель . Аналогично, . Без ограничения общности пусть . По условию: . Пусть есть общий делитель и . Заметим, что , в самом деле, пусть не так:, противоречие. Итак, и потому . Так мы нашли делитель , меньший . Значит, если он не равен 1, то , противоречие. Значит, . Следовательно, и взаимно просты, откуда .