Нахождение НОК и НОД - Free Pascal

Помогите пожалуйста написать программу которая будет вычислять наименьший общий делитель и наибольшее общее кратное. Использовать алгоритм Евклида. В помощь: На множестве целых чисел определены операции сложения, обратная операция вычитания и операция умножения. Операция деления, обратная операции умножения, выполняется не для всех пар чисел, то есть является на множестве целых чисел «частичной операцией». Число а делится на число b 0, если существует число q такое, что b=qc. , (все числа целые). В этом случае говорят, что число b делит число a. При этом число b является делителем числа а или множителем в разложении числа a на множители. Общим делителем двух или нескольких чисел называется число, являющееся делителем каждого из этих чисел. Если а1,…,аn целые числа и хотя бы одно из них не равно нулю, то множество их общих делителей конечно и среди этих делителей существует наибольшее число. Наибольшим общий делителем (НОД) чисел а1,…,аn называется наибольший из их общих делителей. НОД целых чисел а и b называется положительный делитель чисел а и b, делящийся на любой другой общий делитель этих чисел. Cвойства НОД: 1) НОД(a,b) = НОД(b,a) 2) НОД(a,0) = |a| 3) НОД(a,b,с) = НОД(a, НОД(b,c)) 4) НОД(a,b) = НОД(-a,b) Для вычисления наибольшего общего делителя двух целых чисел можно использовать метод разложения на сомножители. 70 делится на 2, 5, 7, 10, 14, 35. 42 делится на 2, 3, 6, 7, 14, 18, 21. НОД(70, 42) = 14. Когда а не делится на b, то говорят о делении а на b с остатком r. Теорема о делении с остатком. Если а и b целые положительные числа, то существуют единственные целые числа q и r такие, что a = b*q + r, 0 ≤. r< b Число q называют неполным частным при делении a на b, число r называют остатком от деления а на b. Деление по модулю (в более узком значении) - арифметическая операция, результатом которой является остаток от деления целого числа на другое целое число, то есть операция нахождения остатка от деления, а также сам остаток от деления . Деление по модулю (в более широком значении) - арифметическая операция, результатом которой является два целых числа: неполное частное и остаток от деления целого числа на другое целое число. То есть имеется в виду операция, которую правильнее называть делением c остатком. Пример, в котором мы сталкиваемся с Модульной арифметикой в повседневной жизни - "арифметика часов". Допустим, сейчас 3 часа после полудня, через 14 часов будет 5 часов утра следующего дня: (3+14) mod 12= 17 mod 12=5. Это арифметика по модулю 12. А вот тоже самое, но по модулю 24: (15+14) mod 24= 29 mod 24=5. Также вычисляются минуты, секунды как деление по модулю 60. Алгоритм вычисления наибольшего общего делителя Евклида ("Начала", 300 лет до н.э.) – один из древнейших классических нетривиальных алгоритмов. В основе алгоритма Евклида лежит повторное деление с остатком: вычисляется остаток от деления (a mod b), затем b mod (a mod b) и так далее, пока остаток не будет равен нулю. Алгоритм Евклида вычисления НОД(a,b) для a, b  0. 1. Если b =0, то результат := а и алгоритм заканчивает работу. 2. Положить r := a mod b, a := b, b := r, и вернуться на шаг 1. Процесс вычисления наибольшего общего делителя чисел a1, a2 по алгоритму Евклида выглядит так: a1 = a2 q1 + a3 0 ≤ a3 < a2 a2 = a3 q2 + a4 0 ≤ a4 < a3 a3 = a4 q3 + a5 0 ≤ a5 < a4 am-2 =am-1 qm-2 + am 0 ≤ am < am-1 am-1 =am qm-1 Результат: НОД(a1, a2) = am. Остановка гарантируется, поскольку остатки от делений образуют строго убывающую последовательность натуральных чисел. Пример: НОД(70, 42) 70 = 42 * 1 + 28 r := 70 mod 42 = 28, a := 42, b := 28 42 = 28 * 1 + 14 r := 42 mod 28 = 14, a := 28, b := 14 28 = 14 * 2 r := 28 mod 14 = 0 Результат: НОД(70, 42)=3. Еще пример: НОД(723,288): Результат: НОД(723,288)=3. Эта процедура хороша как для вычисления вручную, так и для программной реализации. Соответствующая программа короткая и быстрая. Некоторые свойства целых чисел позволяют улучшить программную реализацию алгоритма Евклида: 1) если числа а и b четные, то НОД(a, b) = 2 НОД(a/2, b/2), 2) если а четное и b нечетное, то НОД(a, b) = НОД(a/2, b), 3) НОД(a, b) = НОД(a–b, b), 4) если числа а и b нечетные, то (а – b) четное и НОД(a, b) = НОД((a–b)/2, b). ДОПОЛНЕНИЕ Алгоритм Евклида для целых чисел Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности. Проще сформулировать алгоритм Евклида так: если даны натуральные числа и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД. Пример Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим разность меньше чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147 1071 = 2 × 462 + 147. Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21. 462 = 3 × 147 + 21. Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка. 147 = 7 × 21 + 0. Таким образом последовательность a>b>R1>R2>R3>R4>...>Rn в данном конкретном случае будет выглядеть так: 1071>462>147>21 Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21. В табличной форме, шаги были следующие Шаг k Равенство Частное и остаток 0 1071 = q0 462 + r0 q0 = 2 и r0 = 147 1 462 = q1 147 + r1 q1 = 3 и r1 = 21 2 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм заканчивается