Процесс, называемый сегодня “алгоритмом Эвклида”, предназначен для нахождения наибольшего общего делителя (НОД) двух чисел. Иными словами, это самое большое число, на которое можно разделить два заданных числа без остатка. Заданные числа должны быть составными (то есть не простыми, поскольку простые числа не имеют общих делителей). Первый шаг – деление большего числа на меньшее, результатом которого будет частное и остаток. Далее меньшее из заданных чисел делится на остаток первого деления с тем же результатом – частное и остаток. Остаток предыдущего деления делится на этот полученный остаток и так далее до тех пор, пока в остатке не получится 0 (то есть до тех пор, пока не произойдет деление нацело).
Задача: найти НОД 4433 и 1122.
Решение:
4433 : 1122 = 3, в остатке – 1067;
1122 : 1067 = 1, в остатке – 55;
1067 : 55 = 19, в остатке – 22;
55 : 22 = 2, в остатке – 11;
22 : 11 = 2, в остатке – 0.
Ответ: наибольшим общим делителем 4433 и 1122 является 11.