Даны различные натуральные числа x и y такие, что если к x прибавить наибольший де- литель y, отличный от y, то получится тот же результат, что и если к y прибавить наибольший делитель x, отличный от x. Докажите, что один из этих наибольших делителей делится на другой.
More Questions From This User See All
Answers & Comments
Пусть
, где 
— наибольший собственный делитель 
. Аналогично, 
. Без ограничения общности пусть 
. По условию: 
. Пусть 
есть общий делитель 
и 
. Заметим, что 
, в самом деле, пусть не так:
, противоречие. Итак, 
и потому 
. Так мы нашли делитель 
, меньший 
. Значит, если он не равен 1, то 
, противоречие. Значит, 
. Следовательно, 
и 
взаимно просты, откуда 
.