Как алгоритм Евклида может быть применен для упрощения математических выражений?

Алгоритм Евклида может быть применён для упрощения математических выражений, в частности для нахождения наибольшего общего делителя (НОД) пары целых чисел. school-science.ru younglinux.info

Суть алгоритма: большее число делят на меньшее. younglinux.info Если деление происходит без остатка, то меньшее число и есть НОД (нужно выйти из цикла). younglinux.info Если есть остаток, то большее число заменяют на остаток от деления и переходят к первому пункту. younglinux.info

Пример: нужно найти НОД чисел 272 и 36: school-science.ru

1. 272 = 7 |* 36 + 20 — большее число (272) делят на меньшее (36) и обращают внимание на остаток (20). school-science.ru
2. 36 = 1 |* 20 + 16 — предыдущий делитель (36) делят на предыдущий остаток (20) и обращают внимание на новый остаток (16). school-science.ru
3. 20 = 1 |* 16 + 4 — предыдущий делитель (20) делят на предыдущий остаток (16) и обращают внимание на новый остаток (4). school-science.ru
4. 16 = 4 |* 4 + 0 — предыдущий делитель (16) делят на предыдущий остаток (4). school-science.ru Так как остаток равен 0, можно сказать, что 4 — НОД исходных двух чисел (272 и 36). school-science.ru

После нахождения НОД можно упростить математическое выражение, разделив на него все коэффициенты, если такое возможно. school-science.ru