Наибольший общий делитель двух натуральных чисел равен одному из этих чисел, а…

Пусть меньшее число равно , большее равно . НОД равен одному из чисел, значит, он равен меньшему числу , то есть делится на : , где — натуральное число.

Произведение: .

Раскладываем число на простые множители:

.

Нужно, чтобы делилось на без остатка в виде , то есть — делитель числа . Квадрат делителя может содержать каждый простой множитель только в чётной степени, не больше :

, откуда .

Тогда , .

Проверка: , НОД — равен одному из чисел.