Это полезно знать...
Нахождение НОД по алгоритму Эвклида (по разности):
Допустим, что надо найди наибольший общий делитель (НОД) двух чисел. Заменим большее из них разностью этих чисел. Будем повторять этот процесс до тех пор, пока не получим два одинаковых не равных нулю числа. Последнее полученное число и является наибольшим общим делителем заданных двух чисел.
Образец: НОД(420; 150) = ?
1)420-150 = 270
4)120-30 = 90
2) 270 -150 = 120
5)90-30 = 60
3) 150 -120 = 30
6)60-30 = 30
НОД(420; 150)=НОД(270; 150)= НОД(120; 150)=НОД(120;30)=
=НОД(30;90)=НОД(30;60)=НОД(30;30)=30
Найдите наибольший общий делитель заданных чисел по алгоритму Эвклида (по разности):
НОД(451; 287); НОД(198; 254); НОД(1200; 1325).
Нахождение НОД по алгоритму Эвклида (по частному):
Для нахождения наибольшего общего делителя двух чисел (НОД) каждое из чисел делим на одно и то же число до тех пор, пока они не станут взаимно простыми числами. Произведение полученных делителей будет являться наибольшим общим делителем этих чисел.
Образец: НОД(420; 150) = ?
НОД(420; 150) = 10 • НОД(42; 15) = 10 • 3 • НОД(14; 5) = 10 • 3 • 1 = 30
Т.е., НОД(420; 150) = 30
Найдите наибольший общий делитель заданных чисел по алгоритму Эвклида (по частному):
НОД(426; 126); НОД(198; 252); НОД(2316; 136).