Условия про НОД и НОК

Для поиска НОДа или НОКа удобно смотреть на числа, разложенные по простым делителям — так сразу видно, что у них общего.

Теперь представим, что мы уже нашли НОД и также разложили его на простые множители. Логично, что кроме 2, 3, 5 и 7 в его разложении ничего нового появиться не может (это же все-таки делитель). Рассмотрим внимательнее 5 и 7: если НОД кратен 5, то 504 кратно 5 (число же кратно своему делителю), а это неверно! Аналогично 540 не кратно 7, значит, НОД тоже не кратен 7.

Получается, НОД. Оба числа кратны (просто возьмем наименьшую из степеней двойки и тройки в разложениях), значит, это общий делитель.

А вдруг это не НОД? То есть или . Если же хотя бы 3, то 540 кратно как минимум , то есть тройки входит в разложении в хотя бы 3-ей степени. Но это не так. Аналогично получаем противоречие в случае . Получается, что и и НОД . Однако является общим делителем и, значит, он наибольший.