Слишком сложно? Тогда запросите консультацию специалиста!
Наша компания занимается тем, что помогает студентам выполнять различные учебные работы на заказ. Вы можете ознакомиться с перечнем выполняемых работ, а так же с их стоимостью на странице с ценами.
Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое rk — это остаток от деления предыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
a = bq0 + r1
b = r1q1 + r2
r1 = r2q2 + r3
rk − 2 = rk − 1qk − 1 + rk
rn − 1 = rnqn
Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.
Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого 
, доказывается индукцией по m.
Корректность этого алгоритма вытекает из следующих двух утверждений:
§ Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).
