Наибольший общий делитель

 

Если u и v – целые числа, не оба рвные нулю, то их наибольшим общим делителем D(u, v) называется наибольшее целое число, на которое делятся без остатка как u, так и v. Если u и v оба равны нулю, то, поскольку нуль делится без остатка на любое целое число, выше приведенное определение не применимо; для удобства условимся, что D(0,0) = 0.

Для нахождения D(u, v) используется алгоритм Евклида. Чтобы найти наибольший общий делитель двух целых положительных чисел, нужно сначала большее число разделить на меньшее, затем второе число разделить на остаток от первого деления, потом первый остаток – на второй и т. д. Последний ненулевой положительный остаток в этом процессе и будет наибольшим общим делителем данных чисел.

Обоначив исходные числа через u и v, положительные остатки, получающиеся в результате делений, через r₁, r₂, ..., r_n, а неполные частные через q₁, q₂, ..., q_n+1, можно записать алгоритм Евклида в виде цепочки равенств

u = vq₁ + r₁,

v = r₁q₂ + r₂,

r₁ = r₂q₃ + r₃,

. . . . . .

r_n–2 = r_n–1q_n + r_n,

r_n–1 = r_nq_n+1.

Алгоритм. (Алгоритм Евклида в современной редакции.) По данным неотрицательным числам u и v этот алгоритм находит их наибольший общий делитель. (Замечание: наибольший общий делитель произвольных целых чисел u и v можно получить, применяя алгоритм к êu êи çvï.)

1. [v = 0?] Если v = 0, то алгоритм заканчивается, давая в качестве ответа u.

2. [Взять u mod v.] Установить r ¬ u mod v, u ¬ v, v ¬ r и возвратиться в шаг 1.

Алгоритм Евклида можно обобщить одним способом, который имеет большое значение. При этом способе во время вычисления D(u, v) можно попутно вычислить такие целые числа m и n, что

u×m = v×n = D(u, v).

Это обобщение удобно записать, используя векторные обозначения.

Алгоритм. (Обобщенный алгоритм Евклида.) При заданных неотрицательных целых числах u и v этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что uu₁ + vu₂ = u₃ = D(u, v). В процессе вычисления используются вспомогательные векторы (v₁, v₂, v₃), (t₁, t₂, t₃); действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

ut₁ + vt₂ = t₃, uu₁ + vu₂ = u₃, uv₁ + vv₂ = v₃.

1. [Начальная установка.] Установить (u₁, u₂, u₃) ¬ (1, 0, u), (v₁, v₂, v₃) ¬ (0, 1, v).

2. [v₃ = 0?] Если v₃ = 0, то алгоритм заканчивается.

3. [Разделить, вычесть.] Установить , затем установить

(t₁, t₂, t₃) ¬ (u₁, u₂, u₃) – (v₁, v₂, v₃)q,

(u₁, u₂, u₃) ¬ (v₁, v₂, v₃),

(v₁, v₂, v₃) ¬ (t₁, t₂, t₃).

Возвратиться в шаг 2.