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

Пусть числа a и b, a ≤ b. НОД(a; b) = a, значит, a делит b, то есть b = a·k, где k — натуральное число.

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

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

.

Чтобы делило , в разложении a каждый простой множитель должен входить не более чем в степени, вдвое меньшей, чем в . Для тройки: позволяет содержать не больше , то есть a содержит не больше . Пятёрка в первой степени в входить не может.

Наибольшее a = . Тогда , .

Проверка: , НОД(; ) = , так как делится на .