Бинарный алгоритм евклида

Этот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 2 или на любую степень двойки является весьма быстрой и простой операцией (в двоичной системе счисления операция деления на 2 есть всего лишь битовый сдвиг вправо).

Учтем, что (2^k∙a,2^s∙b)=2^min(k,s)(a,b).

Алгоритм:

Вход: a, b>0.

1. Представим a и b в виде: ; , где a₁, b₁ – нечетные числа.

k:=min(k₁,k₂).

2. Если a₁>b₁ Шаг 4

a₁< b₁ Шаг 3

a₁= b₁ Шаг 6

3. Меняем местами a₁ и b₁.

4. c:=a₁–b₁=2^s∙c₁ (c₁ - нечетное число)

(Заметим, что с обязательно будет четным, а значит )

5. a₁:= b₁ , b₁:=c₁ . Возвращаемся на Шаг 1.

6. Выход: (a,b)=2^k∙a₁ .

Пример

a=603, b=108

a1
b1
c1			–

1. a₁=603, k₁=0; b=108=4∙27=2²∙27 k₂=2, b₁=27, k=0

2. a₁=603> b₁=27 Ш4

4. c=603-27=56=64∙9, c₁=9

5. a₁=27; b₁=9 Ш1

1. a₁=27; b₁=9

2. a₁> b₁ Ш4

4. c=a₁–b₁=18=2∙9, c₁=9

5. a₁=9, b₁=9

1. a₁=9, b₁=9, k=0

2. a₁= b₁ Ш6

6. (a,b) = 2º∙9=9

Для НОД справедливы следующие свойства:

1) (am,bm)=m(a,b)

Доказательство:

Доказательство строится, умножая почленно соотношения алгоритма Евклида на m.

2) d – общий делитель чисел a и b

(в частности, ).

Доказательство:

Учитывая, что и – целые числа, из свойства НОД №1 получаем соотношение , что и требовалось.

□

3) (a,b)=1 (ac,b)=(c,b)

Доказательство:

a, b, c выполняется (ac,b)\ac, (ac,b)\b (ac,b)\bc (ac,b)\(ac,bc).

По условию теоремы, в силу взаимной простоты a и b (ac,bc)=c, то есть получили (ac,b)\с.

Но (ac,b)\b (ac,b)\(c,b).

С другой стороны, (c,b)\ac, (c,b)\b. (c,b)\(ac,b).

Таким образом, числа (ac,b) и (c,b). взаимно делят друг друга (ac,b)=(c,b).

□

4) (a,b)=1, b\ac b\c.

Доказательство:

Из теоремы №1 о НОД в силу b\ac, (ac,b)=b.

из свойства НОД № 3 b=(c,b)и тогда из теоремы №1 о НОД b\c.

□

5) Если (a_i, b_j)=1 для , ( , )=1.

Доказательство:

имеем ( , ) = ( , ) = ( , ) = … = .

Аналогично, используя полученное соотношение,

( , ) = ( , ) = … = ( , ) = 1.

□

НОК (наименьшее общее кратное)

Если a₁\b, a₂\b, … , a_n\b, то b называется общим кратным чисел a₁,…,a_n. Наименьшее положительное общее кратное чисел a₁,…,a_n называется их наименьшим общим кратным (НОК).

Пусть НОД(a,b)=d, тогда можно записать a=d∙a₁, b=d∙b₁, где (a₁,b₁)=1.

Пусть a\M, b\M M=ak для некоторого целого k, и тогда число – целое. Но, поскольку (a₁,b₁)=1, то b₁\k , и тогда k=b₁t для некоторого , и

. *

Очевидно, , М – общее кратное a и b, и (*) дает формулу всех общих кратных.

При t=1 имеем M=НОК(a,b).

Формулой M = НОК(a,b)∙t можно представить все общие кратные чисел a и b. ( ).

Простые числа

Числа a₁,…,a_n называются взаимно простыми, если НОД(a₁,…,a_n)=1, попарно простыми, если , НОД(a_i,a_j)=1.

Если числа попарно a₁,…,a_n простые, то они взаимно простые. Обратное неверно.

Число p называется простым, если оно имеет лишь два делителя – “1” и р.

Число “1” делится только на себя, и не является ни простым, ни составным, а занимает особое место в теории чисел.

Число а>1 имеющее более двух делителей, называется составным.

Утверждение 1

Наименьший не равный единице делитель числа a: , >1, является простым числом.

Доказательство:
Пусть q: q>1, q\a – наименьший делитель а. Если бы q было составным, то нашлось бы число q₁>1: q₁\q, и тогда для некоторого целого k выполнялось бы q=kq₁ a=qt=q₁kt q₁\a, q₁<q (то есть нашелся делитель числа a, который меньше q) q – не наименьший делитель числа a. Пришли к противоречию с условием теоремы. Предположение неверное, следовательно верно обратное. q – простое число.

□

Утверждение 2

p – наименьший делитель составного числа а, p≠1 .

Доказательство:

Представим a в виде a=pa₁. Поскольку p – наименьший делитель числа a, то a₁≥p a≥p² в силу монотонности квадратичной функции на положительной полуоси, p≤ .

□