Алгоритъмът на Евклид е метод на обучение в университет. Алгоритъм на Евклид

Тази статия е за намиране на най-голям общ делител (НОД)две и Повече ▼числа. Първо, нека да разгледаме алгоритъма на Евклид; той ви позволява да намерите gcd на две числа. След това ще се съсредоточим върху метод, който ни позволява да изчислим gcd на числа като произведение на техните общи прости множители. След това ще разгледаме намирането на най-големия общ делител на три или повече числа и ще дадем примери за изчисляване на gcd на отрицателни числа.

Навигация в страницата.

Евклидов алгоритъм за намиране на НОД

Обърнете внимание, че ако се бяхме обърнали към таблицата на простите числа от самото начало, щяхме да разберем, че числата 661 и 113 са прости числа, от което веднага бихме могли да кажем, че техните най-големи общ делителе равно на 1.

Отговор:

НОД(661, 113)=1.

Намиране на НОД чрез разлагане на числа на прости множители

Нека разгледаме друг начин за намиране на GCD. Най-големият общ делител може да бъде намерен чрез разлагане на числа на прости множители. Нека формулираме правило: Gcd на две положителни цели числа a и b е равна на произведението на всички общи прости множители, намиращи се в разширенията на числата a и b в основни фактори .

Нека дадем пример, за да обясним правилото за намиране на GCD. Нека знаем разлагането на числата 220 и 600 на прости множители, те имат формата 220=2·2·5·11 и 600=2·2·2·3·5·5. Общите прости множители, включени в разлагането на числата 220 и 600, са 2, 2 и 5. Следователно НОД(220, 600)=2·2·5=20.

Така, ако разложим числата a и b на прости множители и намерим произведението на всички техни общи множители, тогава това ще намери най-големия общ делител на числата a и b.

Нека разгледаме пример за намиране на GCD според посоченото правило.

Пример.

Намерете най-големия общ делител на числата 72 и 96.

Решение.

Нека разложим числата 72 и 96 на прости множители:

Тоест 72=2·2·2·3·3 и 96=2·2·2·2·2·3. Често срещаните прости множители са 2, 2, 2 и 3. Така НОД(72, 96)=2·2·2·3=24.

Отговор:

НОД(72, 96)=24.

В заключение на този параграф отбелязваме, че валидността на горното правило за намиране на GCD следва от свойството на най-големия общ делител, което гласи, че НОД(m a 1, m b 1)=m НОД(a 1, b 1), където m е всяко положително цяло число.

Намиране на gcd на три или повече числа

Намирането на най-големия общ делител на три или повече числа може да се сведе до последователно намиране на НОД на две числа. Споменахме това, когато изучавахме свойствата на GCD. Там формулирахме и доказахме теоремата: най-големият общ делител на няколко числа a 1, a 2, …, a k равно на числото d k , което се намира чрез последователно изчисляване на НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k - 1 , a k)=d k .

Нека видим как изглежда процесът на намиране на gcd на няколко числа, като разгледаме решението на примера.

Пример.

Намерете най-големия общ множител на четири числа 78, 294, 570 и 36.

Решение.

В този пример a 1 =78, a 2 =294, a 3 =570, a 4 =36.

Първо, използвайки алгоритъма на Евклид, ние определяме най-големия общ делител d 2 на първите две числа 78 и 294. При деление се получават равенствата 294 = 78 3 + 60 ; 78=60·1+18 ; 60=18·3+6 и 18=6·3. Така d 2 =НОД(78, 294)=6.

Сега нека изчислим d 3 = НОД (d 2, a 3) = НОД (6, 570). Нека отново приложим алгоритъма на Евклид: 570=6·95, следователно d 3 = НОД(6, 570)=6.

Остава да изчислим d 4 =НОТ(d 3, a 4)=НОТ(6, 36). Тъй като 36 се дели на 6, тогава d 4 = НОД(6, 36) = 6.

Така най-големият общ делител на четирите дадени числа е d 4 =6, тоест gcd(78, 294, 570, 36)=6.

Отговор:

НОД(78, 294, 570, 36)=6 .

Разлагането на числа на прости множители също ви позволява да изчислите gcd на три или повече числа. В този случай най-големият общ делител се намира като произведение на всички общи прости множители на дадените числа.

Пример.

Изчислете gcd на числата от предишния пример, като използвате техните прости множители.

Решение.

Нека разложим числата 78, 294, 570 и 36 на прости множители, получаваме 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2 ·3· 3. Общите прости множители на всички тези четири числа са числата 2 и 3. следователно НОД(78, 294, 570, 36)=2·3=6.

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

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

Алгоритъм за намиране на НОД чрез деление

1. Разделете по-голямото число на по-малкото.
2. Ако е разделено без остатък, тогава по-малкото число е НОД (трябва да излезете от цикъла).
3. Ако има остатък, заменете по-голямото число с остатъка от делението.
4. Да преминем към точка 1.

Пример:
Намерете gcd за 30 и 18.
30 / 18 = 1 (остатък 12)
18 / 12 = 1 (остатък 6)
12 / 6 = 2 (остатък 0)
Край: НОД е делител на 6.
НОД(30, 18) = 6

a = 50 b = 130 докато a != 0 и b != 0 : ако a > b: a = a % b else : b = b % a печат (a + b)

В цикъла остатъкът от делението се записва в променливата a или b. Цикълът завършва, когато поне една от променливите е нула. Това означава, че другият съдържа gcd. Не знаем обаче кой точно. Следователно за GCD намираме сумата от тези променливи. Тъй като една от променливите е нула, това няма ефект върху резултата.

Алгоритъм за намиране на НОД чрез изваждане

1. Извадете по-малкото число от по-голямото число.
2. Ако резултатът е 0, това означава, че числата са равни едно на друго и са НОД (трябва да излезете от цикъла).
3. Ако резултатът от изваждането не е равен на 0, тогава заменете по-голямото число с резултата от изваждането.
4. Да преминем към точка 1.

Пример:
Намерете gcd за 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Край: НОД е умалено или субтрахенд.
НОД(30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

Нека разгледаме два основни метода за намиране на НОД по два основни начина: с помощта на Евклидовия алгоритъм и чрез разлагане на прости множители. Нека приложим и двата метода за две, три или повече числа.

Евклидов алгоритъм за намиране на НОД

Алгоритъмът на Евклид улеснява изчисляването на най-големия общ множител на две положителни числа. Представихме формулировките и доказателството на алгоритъма на Евклид в раздела „Най-голям общ делител: детерминанта, примери“.

Същността на алгоритъма е последователно да се извърши деление с остатък, при което се получават поредица от равенства на формата:

a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Можем да завършим разделянето, когато r k + 1 = 0, при което r k = gcd (a, b).

Пример 1

64 И 48 .

Решение

Нека въведем следните обозначения: a = 64, b = 48.

Въз основа на алгоритъма на Евклид ще извършим разделяне 64 На 48 .

Получаваме 1 и остатъка 16. Оказва се, че q 1 = 1, r 1 = 16.

Втората стъпка е да се раздели 48 до 16 получаваме 3. Това е q 2 = 3, А r 2 = 0.Така числото 16 е най-големият общ делител на числата от условието.

Отговор:НОД (64, 48) = 16.

Пример 2

Какво е НОД на числата? 111 И 432 ?

Решение

Ние разделяме 432 На 111 . Според алгоритъма на Евклид получаваме веригата от равенства 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Така най-големият общ делител на числата е 111 И 432 – това е 3.

Отговор:НОД (111, 432) = 3.

Пример 3

Намерете най-големия общ делител на числата 661 и 113.

Решение

Нека последователно разделим числата и да получим НОД (661 , 113) = 1 . Това означава, че 661 и 113 са относително прости числа. Можем да разберем това, преди да започнем изчислението, ако се консултираме с таблица с прости числа.

Отговор:НОД (661, 113) = 1.

Намиране на НОД чрез разлагане на числа на прости множители

За да се намери най-големият общ делител на две числа, като се използва методът на факторизиране, е необходимо да се умножат всички прости множители, които се получават при разлагането на тези две числа и са общи за тях.

Пример 4

Ако разложим числата 220 и 600 на прости множители, получаваме два продукта: 220 = 2 2 5 11И 600 = 2 2 2 3 5 5. Общите множители в тези два продукта са 2, 2 и 5. Това означава, че GCD (220, 600) = 2 2 5 = 20.

Пример 5

Намерете най-големия общ делител на числата 72 И 96 .

Решение

Намерете всички прости множители на числа 72 И 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Общите прости множители за две числа са 2, 2, 2 и 3. Това означава, че GCD (72, 96) = 2 2 2 3 = 24.

Отговор:НОД (72, 96) = 24.

Правилото за намиране на най-големия общ делител на две числа се основава на свойствата на най-големия общ делител, според които gcd (m a 1, m b 1) = m gcd (a 1, b 1), където m е всяко положително цяло число .

Намиране на gcd на три или повече числа

Независимо от броя на числата, за които трябва да намерим НОД, ще следваме същия алгоритъм, който се състои в последователно намиране на НОД на две числа. Този алгоритъм се основава на прилагането на следната теорема: НОД на няколко числа a 1 , a 2 , … , a kравно на числото dk, което се намира чрез последователно изчисляване на gcd (a 1 , a 2) = d 2, НОД (d 2 , a 3) = d 3 , НОД (d 3 , a 4) = d 4 , … , НОД (d k - 1 , a k) = d k .

Пример 6

Намерете най-големия общ делител на четири числа 78, 294, 570 и 36 .

Решение

Нека въведем обозначението: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Нека започнем с намирането на gcd на числата 78 и 294: d 2 = GCD (78 , 294) = 6 .

Сега нека започнем да намираме d 3 = НОД (d 2 , a 3) = НОД (6, 570). Според алгоритъма на Евклид 570 = 6 95.Означава, че d 3 = GCD (6 , 570) = 6 .

Нека намерим d 4 = НОД (d 3 , a 4) = НОД (6, 36). 36 делимо на 6 без остатък. Това ни позволява да получим d 4 = GCD (6 , 36) = 6 .

d4 = 6, тоест GCD (78 , 294 , 570 , 36) = 6 .

Отговор:

Сега нека разгледаме друг начин за изчисляване на GCD за тези и повече числа. Можем да намерим gcd, като умножим всички общи прости множители на числата.

Пример 7

Изчислете НОД на числата 78, 294, 570 и 36 .

Решение

Нека разложим тези числа на прости множители: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.

И за четирите числа общите прости множители ще бъдат числата 2 и 3.

Оказва се, че GCD (78, 294, 570, 36) = 2 3 = 6.

Отговор:НОД (78, 294, 570, 36) = 6.

Намиране на НОД на отрицателни числа

Ако трябва да имаме работа с отрицателни числа, тогава можем да използваме модулите на тези числа, за да намерим най-големия общ делител. Можем да направим това, като знаем свойството на числата с противоположни знаци: числа нИ -нимат еднакви делители.

Пример 8

Намерете gcd на отрицателни цели числа − 231 И − 140 .

Решение

За да извършим изчисления, вземаме модулите на числата, дадени в условието. Това ще бъдат числата 231 и 140. Нека го запишем накратко: GCD (− 231 , − 140) = НОД (231, 140) . Сега прилагаме алгоритъма на Евклид, за да намерим прости множители на две числа: 231 = 140 · 1 + 91 ; 140 = 91 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 1 + 7 и 42 = 7 6. Получаваме, че НОД (231, 140) = 7 .

И тъй като GCD (− 231 , − 140) = GCD (231 , 140) , след това gcd от числа − 231 И − 140 равно на 7 .

Отговор:НОД (− 231, − 140) = 7.

Пример 9

Определете НОД на три числа − 585, 81 и − 189 .

Решение

Нека заменим отрицателните числа в горния списък с техните абсолютни стойности, получаваме НОД (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . След това разлагаме всички тези числа на прости множители: 585 = 3 3 5 13, 81 = 3 3 3 3 и 189 = 3 3 3 7. Общи за трите числа са простите множители 3 и 3. Оказва се, че НОД (585, 81, 189) = НОД (− 585, 81, − 189) = 9.

Отговор:НОД (− 585, 81, − 189) = 9.

Ако забележите грешка в текста, моля, маркирайте я и натиснете Ctrl+Enter

Алгоритъм на Евклиде метод за намиране на най-голям общ делител (НОД) на две цели числа. Оригиналната версия на алгоритъма, когато НОД се намира чрез изваждане, е открита от Евклид (III век пр.н.е.). Понастоящем разделянето се използва по-често при изчисляване на GCD с помощта на евклидовия алгоритъм, тъй като този метод е по-ефективен.

Изчисляване на gcd чрез деление

Най-големият общ делител на двойка числа е най-голямото число, което дели поравно и двете числа от двойката. Да предположим, че трябва да изчислите gcd за числата 108 и 72. Алгоритъмът за изчисление чрез деление ще бъде както следва:

1. Разделете по-голямото число (дивидент) на по-малкото число (делител): 108 / 72 = 1, остатък 36.
2. Тъй като остатъкът не е равен на нула, ще направим делителя дивидент, а остатъка делител: 72 / 36 = 2, остатък 0.
3. Когато остатъкът е нула, тогава делителят е желаната gcd за двойка дадени числа. Тоест, НОД(108, 72) = 36. Наистина, 108 / 36 = 3 и 72 / 36 = 2.

В този алгоритъм делението се повтаря, докато остатъкът стане нула. Когато той стане такъв, НОД е делителя на последното деление. Например, трябва да намерите GCD(106, 16):

1. 106/16 = 6, остатък 10
2. 16/10 = 1, остатък 6
3. 10/6 = 1, остатък 4
4. 6/4 = 1, остатък 2
5. 4/2 = 2, остатък 0
6. gcd(106, 16) = 2

Изчисляване на НОД чрез изваждане

Когато намирате НОД чрез изваждане, вие също трябва да достигнете нула. Алгоритъмът е подобен на метода на делене, само че при всяка следваща стъпка изместеното и умаляваното стават изваждаемото и разликата от предходната стъпка. В този случай по-малкото число винаги се изважда от по-голямото число. Този тип алгоритъм е подходящ само за положителни цели числа.

Да кажем, че трябва да намерим GCD(108, 72):

1. 108 - 72 = 36
2. 72 - 36 = 36
3. 36 - 36 = 0
4. gcd(108, 72) = 36

Нека намерим gcd(44, 60):

1. 60 - 44 = 16
2. 44 - 16 = 28
3. 28 - 16 = 12
4. 16 - 12 = 4
5. 12 - 4 = 8
6. 8 - 4 = 4
7. 4 - 4 = 0
8. gcd(44, 60) = 4

Този алгоритъм понякога се описва по различен начин. Изваждането завършва по-рано, на стъпката, когато едно число напълно разделя друго. Тоест, те комбинират изваждане с тест за делимост. Тогава намирането на gcd за 44 и 60 ще изглежда така:

1. 44 дели ли 60? Не. 60 - 44 = 16.
2. 16 дели ли 44? Не. 44 - 16 = 28.
3. 16 дели ли 28? Не. 28 - 16 = 12.
4. 12 дели ли 16? Не. 16 - 12 = 4.
5. 4 дели ли 12? да Това означава gcd(44, 60) = 4.

Забележка, НОД не е частното, а делителя. Ако в примера разделим 12 на 4, получаваме частното 3. Но това не е gcd.

Доказателство за алгоритъма на Евклид

Нека вземем предвид факта, че ако едно естествено число от двойка дели напълно друго, то техният gcd ще бъде равен на по-малкото от тях. Можете да го напишете така:

ако a / b е пълно, тогава gcd(a, b) = b. Например gcd(15, 5) = 5.

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

Втори факт. Трябва да докажете, че ако едно число е по-голямо от другото, тогава техният най-голям общ делител е равен на най-големия общ делител на по-малкото число от двойката и разликата между по-голямото и по-малкото числа. Това може да се напише така:

ако< b, то НОД(a, b) = НОД(a, b - a).

Можете да докажете, че НОД(a, b) = НОД(a, b - a), както следва. Нека b - a = c. Ако някое число x дели a и b на цяло число, то също ще дели c на цяло число. В крайна сметка, ако a и b са различни, тогава делителят се вписва в цяло число, но различен номерведнъж. И ако извадите едното от другото, тогава делителят също трябва да се побере цял брой пъти в получената разлика.

Ако последователно намаляваме a и b, тогава рано или късно ще стигнем до стойност за по-малката от тях, която напълно разделя по-голямата. По-малкото от такава двойка ще бъде най-големият общ делител на първоначалната двойка естествени числа. Това е алгоритъмът на Евклид.

Най-голямата обща разделителна линия на две регионални числа $a$ и $b$ - $NOD(a, b)$ - е най-голямото число , на някакво число $a$ и $b$ се делят без остатък.

За да намерите $НОД(a, b)$, можете да продължите по следния естествен начин: разложите двете числа la по степени на прости числа: $a = 2^(\alpha_1) \cdot 3^(\alpha_2) \cdot \ldots \cdot p^(\alpha_n)_n$ , $b = 2 ^(\beta_1) \cdot 3^(\beta_2) \cdot \ldots \cdot p^(\beta_n)_n$ , ($\alpha_k$ и $ \beta_k$ може да бъде равно на нула). Тогава $$GCD(a, b) = 2^(\min(\alpha_1, \beta_1)) \cdot 3^(\min(\alpha_2, \beta_2)) \cdot \ldots \cdot p^(\ min( \alpha_n, \beta_n))_n.$$ Например, за да намерим най-често срещаната стойност от $2625$ и $8100 $, получаваме: $2625 = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^2 \cdot 7^0$, означава $GCD(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.

Основният недостатък на този метод е, че разделянето на голямо число на прости множества не е толкова просто, сто, или по-скоро не толкова бързо.

Евклид в 7-ма книга „Начало” описва ал-го-ритъма на „общата мярка на две числа”. Ал-го-ритъмът се описва от гео-мет-ри-че-ски, като подобие на общата мярка на два разфасовки. Тя се свежда до „последване от-нацията“ от по-голямото-от-по-малкото-от-разрязването. Сега този al-go-ритъм от стените е като al-go-ритъма на Ev-kli-da за намиране на най-често срещаните de-li-those - за две натурални числа.

Основната идея, на която се основава al-go-ритъмът, е, че $GCD$ числата $a$ и $b$ са равни $NOD$ chi-sel $b$ и $a-b$. От тук следва, че ако добавите $a$ към $b$ с остатъка, т.е. представено във формата $a = b \cdot q + r$, тогава $NOD(a, b) = GCD(b, r)$.

Ще опишем красивата geo-met-ri-che-skaya in-ter-pre-ta-tion на al-go-rit-ma, inter-active-tiv-naya re-a-li-za -tion на нещо пред-същото-по-високо.

В прав ъгъл с дълги страни $a$ и $b$ за възможно най-големия квадрат. В останалите прави въглища отново вземаме максимално възможния квадрат. И така докато се покрие целия оригинален правоъгълник. Дължината на квадрата е сто и ще бъде равна на $НОД(a, b)$.

По-подробно, но geo-met-ri-che-skaya in-ter-pre-ta-tion op-sa-na по-долу и par-ral-lel-но с-ve-de-но arif-me-ti- che-skoe opis-sa-nie al-go-rit-ma Ev-kli-da.

Ал-го-ритъмът на Ев-кли-да е мощен инструмент, използван при решаването на различни лични проблеми. Например, използва се за решаване на уравнения в цели числа, представяйки числата под формата на постоянни (верижни) дроби, може да се обобщи, за да се намери най-често срещаният de-li-the two many-go-member-nov.

Литература

Евклид. На-ча-ла Ев-кли-да. Книги VII, X. - M.-L.: GITTL, 1950.

Р. Ку-рант, Г. Робинс. Каква е тази ма-те-ма-ти-ка? - М.: МЦНМО, 2010.