Алгоритм Евклида

АЛГОРИТМ ЕВКЛИДА
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.
Евклид
(365-300 до. н. э.)
Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание».

Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка.
НОД(a, b)= НОД(a-b, b)= НОД(a, b-a)
Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.
НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9
Пример :

Найдите НОД и НОК чисел, используя Алгоритм Евклида М=32, N=24; M=696, N=234.
1. Проверить, являются ли два данных числа взаимно простыми.
Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.
2. Найти наименьшее общее кратное (НОК) чисел 645 и 381, если
НОК(n, m) = n * m / НОД (n, m).
3. Даны натуральные числа m(120) и n(75). Найти такие натуральные p и q, не имеющие общих делителей, что
p / q = m / n.
4. Найти НОД трех чисел 112, 81, 342.
Примечание. НОД(a, b, c)= НОД(НОД(a, b), c)
Задачи

Найдите НОД (111 … 111,11 … 11) – в записи первого числа 100 единиц,
в записи второго – 60.
Докажите, что существуют целые числа m и n такие, что ma + nb = 1. e)
Какова последняя цифра числа ?
Найти наибольший общий делитель чисел 420 и 148, путем разложения
на простые множители.