Алгоритм Евклида нахождения наибольшего общего делителя

Модулярная арифметика

Пусть а и п – натуральные числа. "Разделить число а на число п с остатком" – это значит найти целые числа а и r, удовлетворяющие условию

а = q ∙ п + r, где 0 ≤ r < п.

При этом число q называют неполным частным, а r – остатком от деления числа а на число п. Буква r здесь используется как первая буква иностранного слова, в переводе на русский означающего «остаток».

Если остаток r равен нулю, то говорят, что число п делит число а, или, по-другому, п является делителем числа а, или, по-другому, а делится на п.

Целые числа а и b называют сравнимыми по модулю п, если их остатки при делении на п совпадают. Обычно для обозначения этого факта используется запись

а ≡ b (mod n).

Отсюда, в частности, следует, что число п делит разность чисел а и b. Для обозначения остатка часто используют бесскобочную запись

b = a mod п.

Операцию нахождения числа b = a mod п называют приведением числа а по модулю п.

Множество целых чисел a ₀,..., a_{n - 1} таких, что для любого целого числа b найдется
k ∈ {0,..., n - 1} со свойством a_k ≡ b (mod n), называется полной системой вычетов по модулю п.

Обычно используется полная система вычетов Z _n ={0,1,..., n - 1}.

Разложение чисел на простые множители

Натуральное число а, большее 1, называется простым, если оно не имеет натуральных делителей, отличных от 1 и самого числа а.

Любое натуральное число, отличное от 1, либо является простым, либо может быть представлено в виде произведения простых чисел, и тогда оно называется составным.
Это представление определено однозначно с точностью до порядка сомножителей в произведении. Это утверждение называют «Основной теоремой арифметики».

Следует отметить, что в настоящее время нет достаточно эффективных алгоритмов разложения произвольного целого числа на простые множители даже в случае, когда известно, что оно разлагается в произведение двух простых чисел. Отсутствие эффективных алгоритмов с доказуемыми оценками сложности позволяет использовать задачу факторизации – разложения натуральных чисел на простые множители – при обосновании стойкости некоторых криптографических алгоритмов. Примеры – криптосистемы RSA, BBS.

Алгоритм Евклида нахождения наибольшего общего делителя

Наибольшее целое число, делящее одновременно целые числа а и b, называется их наибольшим общим делителем и обозначается НОД(a, b) или нод(a, b) или просто (а, b).
Если (а, b) = 1, то а и b называются взаимно простыми числами. Числа a,b,…c называются попарно взаимно простыми числами, если любые два из них взаимно просты.

Алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел заключается в проведении следующей последовательности операций деления с остатком:

а = q ∙ b + c, где 0 ≤ c < b,
b = q ₁ ∙ c + d, где 0 ≤ d < c,
c = q ₂ ∙ d + e, где 0 ≤ e < d,
d = q ₃ ∙ e + f, где 0 ≤ f < e,
e = q ₄ ∙ f + g, где 0 ≤ g < f,

...

Корректное завершение алгоритма гарантируется тем, что остатки от делений образуют строго убывающую последовательность натуральных чисел. Из приведенных равенств следует, что

(a, b) = (b, с) = (с, d) =...

Поэтому наибольший делитель чисел а и b совпадает с последним ненулевым остатком.

Этому алгоритму несколько тысяч лет. Говоря без формул, надо делить с остатком первое на второе с остатком – это третье число, затем второе на третье с остатком – это четвёртое число, и так далее, пока в остатке не будет нуль (последнее число), тогда предпоследнее число будет искомым наибольшим общим делителем данных двух чисел. Так коротко этот алгоритм описывается даже на древнегреческом. Кстати, он пригоден и для нахождения наибольшего общего делителя двух многочленов над данным полем.

Как следствие из алгоритма Евклида, можно получить утверждение, что наибольший делитель (a,b) целых чисел а и b может быть представлен в виде линейной комбинации этих чисел, т.е. существуют целые числа и и v такие, что справедливо равенство

а ∙ и + b ∙ v = (a,b).

Алгоритм их нахождения называется расширенным алгоритмом Евклида.

Поиск по сайту: