Основно съдържание

Курс: Компютърни науки > Раздел 2

Урок 5: Модулна аритметика

Алгоритъм на Евклид

Припомни си, че най-големият общ делител (НОД) на две цели числа А и В е най-голямото цяло число, което е делител едновременно на А и на В.

Алгоритъмът на Евклид е метод за бързо намиране на НОД на две цели числа.

Алгоритъмът

Алгоритъмът на Евклид за намиране на НОД(A,B) е следният:

Ако A = 0, то НОД(A,B)=B, тъй като НОД(0,B)=B, и можем да спрем дотук.
Ако B = 0, то НОД(A,B)=A, тъй като НОД(A,0)=A, и можем да спрем дотук.
Запиши А като частно с остатък (A = B⋅Q + R)
Намери НОД(B,R), като използваш алгоритъма на Евклид при условие, че НОД(A,B) = НОД(B,R)

Пример:

Намери НОД на 270 и 192

A=270, B=192
A ≠0
B ≠0
Използвай дълго деление, за да получиш 270/192 = 1 с остатък 78. Можем да го запишем така: 270 = 192 * 1 +78
Намери НОД(192,78), при условие, че НОД(270,192)=НОД(192,78)

A=192, B=78

A ≠0
B ≠0
Използвай дълго деление, за да намериш 192/78 = 2 с остатък 36. Можем да го запишем така:
192 = 78 * 2 + 36
Намери НОД(78,36), при условие, че НОД(192,78)=НОД(78,36)

A=78, B=36

A ≠0
B ≠0
Използвай дълго деление, за да намериш, че 78/36 = 2 с остатък 6. Можем да го запишем така:
78 = 36 * 2 + 6
Намери НОД(36,6), при условие, че НОД(78,36)=НОД(36,6)

A=36, B=6

A ≠0
B ≠0
Използвай дълго деление, за да намериш, че 36/6 = 6 с остатък 0. Можем да го запишем така:
36 = 6 * 6 + 0
Намери НОД(6,0), при условие, че НОД(36,6)=НОД(6,0)

A=6, B=0

A ≠0
B =0, GCD(6,0)=6

Показахме, че:

НОД(270,192) = НОД(192,78) = НОД(78,36) = НОД(36,6) = НОД(6,0) = 6

НОД(270,192) = 6

Обяснение на алгоритъма на Евклид

Ако разгледаме алгоритъма на Евклид, ще видим, че в него се използват следните свойства:

НОД(A,0) = A
НОД(0,B) = B
Ако A = B⋅Q + R и B≠0, то НОД(A,B) = НОД(B,R), където Q е цяло число, а R е цяло число между 0 и B-1

Първите две свойства ни позволяват да намерим НОД, ако някое от числата е равно на 0. Третото свойство ни позволява да вземем по-голяма и по-трудна за решаване задача и да я редуцираме до по-малка и по-лесна за решаване задача.

Алгоритъмът на Евклид използва тези две свойства, за да редуцира бързо задачата на все по-лесни и по-лесни задачи, като използва третото свойство, докато не я реши лесно с първите две свойства.

Можем да разберем как действат тези свойства, като ги докажем.

Можем да докажем, че НОД(A,0)=A така:

Най-голямото цяло число, което дели без остатък А е числото А.
Всички цели числа делят 0 без остатък, тъй като за всяко цяло число С можем да запишем C ⋅ 0 = 0. Така можем да стигнем до заключението, че А дели 0 без остатък.
Най-голямото число, което дели А и 0 е А.

Доказателството за НОД(0,B)=B е подобно. (Същото доказателство, но заменяме А с В).

За да докажем, че НОД(A,B)=НОД(B,R), първо трябва да покажем, че НОД(A,B)=НОД(B,A-B).

Да приемем, че имаме 3 цели числа A,B и C, за които A-B=C.

Доказателство, че НОД(A,B) дели без остатък C

По определение НОД(A,B) дели без остатък А. В резултат на това А трябва да е множител на НОД(A,B). Т.е. X⋅НОД(A,B)=A, където Х е цяло число.

По определение НОД(A,B) дели без остатък В. В резултат на това В трябва да е множител на НОД(A,B). Т.е. Y⋅НОД(A,B)=B, където Y е цяло число.

A-B=C ни дава:

X⋅НОД(A,B) - Y⋅НОД(A,B) = C
(X - Y)⋅НОД(A,B) = C

Така виждаме, че НОД(A,B) дели без остатък C.

В лявата част на фигурата по-долу е показана илюстрация на това доказателство:

Доказателство, че НОД(B,C) дели A без остатък

По определение НОД(B,C) дели B без остатък. В резултат на това В трябва да е множител на НОД(B,C). Т.е. M⋅НОД(B,C)=B, където М е цяло число.

По определение НОД(B,C) дели С без остатък. В резултат на това С трябва да е множител на НОД(B,C). Т.е. N⋅НОД(B,C)=C, където N е цяло число.

A-B=C ни дава:

B+C=A
M⋅НОД(B,C) + N⋅НОД(B,C) = A
(M + N)⋅НОД(B,C) = A

Виждаме, че НОД(B,C) дели A без остатък.

На фигурата по-долу е показана илюстрация на това доказателство:

Доказателство, че НОД(A,B)=НОД(A,A-B)

По определение НОД(A,B) дели B без остатък.
Доказахме, че НОД(A,B) дели C без остатък.
Тъй като НОД(A,B) дели В и С без остатък, то е общ делител на В и С.

НОД(A,B) трябва да е по-малко или равно на НОД(B,C), тъй като НОД(B,C) е "най-големият" общ делител на В и С.

По определение НОД(B,C) дели В без остатък.
Доказахме, че НОД(B,C) дели А без остатък.
Тъй като НОД(B,C) дели А и В без остатък, то е общ делител на А и В.

НОД(B,C) трябва да е по-малко или равно на НОД(A,B), защото НОД(A,B) е "най-големият" общ делител на А и В.

При условие, че НОД(A,B)≤НОД(B,C) и НОД(B,C)≤НОД(A,B), можем да направим заключението, че:

НОД(A,B)=НОД(B,C)

Което е еквивалентно на:

НОД(A,B)=НОД(B,A-B)

В дясната част на фигурата по-долу е дадена илюстрация на това доказателство.

Доказателство за НОД(A,B) = НОД(B,R)

Доказахме, че НОД(A,B)=НОД(B,A-B)

Редът нянам значение, затова можем да кажем НОД(A,B)=НОД(A-B,B)

Можем да приложим няколко пъти НОД(A,B)=НОД(A-B,B) и ще получим:

НОД(A,B)=НОД(A-B,B)=НОД(A-2B,B)=НОД(A-3B,B)=...=НОД(A-Q⋅B,B)

Но A= B⋅Q + R, така че A-Q⋅B=R

Следователно НОД(A,B)=НОД(R,B)

Редът няма значение, така че:

НОД(A,B)=НОД(B,R)

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.