• Въведете понятието "алгоритъм на Евклид".
• Да научи как да намираме най-често срещаните делители по различни математически начини.

По време на занятията

Концепция за алгоритъм на Евклид

Той е един от най-старите математици, който е на повече от 2000 години.

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

Най-голям общ делител

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

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

Алгоритъм за намиране на GCD чрез деление

Описание на алгоритъма за намиране на най-голям общ делител чрез деление

По-голямото число се дели на по-малкото

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

Ако има остатък, заменете по-голямото число с остатъка от деленето

Преминете към точка 1.

пример:

Намерете най-големия общ множител на 300 и 180.

300/180 = 1 (остатък 120)

180/120 = 1 (остатък 60)

120/60 = 2 (остатък 0).

Край:най-големият общ фактор е 6.

V цикъл"A" или "b" е остатъкът от разделението. Когато няма остатък (не знаем в "a" той или "b", така че проверяваме и двете условия), след което цикълът свършва.

В края се показва сборът от "a" и "b", тъй като не знаем в коя променлива е записан най-големият общ делител, а в един от тях, във всеки случай, 0, което не влияе на резултата от сумата.

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

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

По-малкото се изважда от по-голямото число.

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

Ако резултатът от изваждането не е 0, тогава по-голямото число се заменя с резултата от изваждането

Преминете към точка 1.

пример:Намерете за числа 300 и 180.

Край:Най-често срещаният делител на 300 и 180 е 60.

Като начин за намиране на най-голямата обща мярка на два сегмента (методът на редуващо се изваждане) е бил известен на питагорейците.

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

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

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

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

пример:

Като отсечки вземаме страната AB и AC на равнобедрения триъгълник ABC, в който A = C = 72 °, B = 36 °.

Като първи остатък получаваме отсечката AD (CD-бисектриса на ъгъл C) и, както е лесно да се види, последователността от нулеви остатъци ще бъде безкрайна.

Това означава, че отсечките AB и AC не са съизмерими.

Въпроси

1. Какво представлява алгоритъмът на Евклид?

2. Кой е най-големият общ фактор?

Списък на използваните източници

1. Урок на тема: "Алгоритъм на Евклид", P. I. Korchevoy, Луцк

2. Shchetnikov AI Евклидов алгоритъм и непрекъснати дроби. - Новосибирск: АНТ, 2003

3. Kountinho S. Въведение в теорията на числата. Алгоритъм RSA, - М., 2001

4. Кострикин A.I. Въведение в алгебрата, - М., 2000

Редактирано и изпратено от учителя Киевски национален университет. Тарас ШевченкоСоловьев М.С.

Работи върху урока

Korchevoy P.I.

Соловьев М.С.

Задайте въпрос относно съвременно образование, да изразите идея или да решите спешен проблем, можете на Образователен форум

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

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

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

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

В този алгоритъм деленето се повтаря, докато остатъкът стане нула... Когато той стане такъв, GCD е делителят на последното деление... Например, трябва да намерите 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 чрез изваждане

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

Нека се изисква да се намери 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.

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

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

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

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

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

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

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

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

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

Алгоритъмът на Евклид за намиране на GCD (най-голям общ делител)

Дадени са две неотрицателни цели числа и. Необходимо е да се намери техния най-голям общ делител, т.е. най-голямото число, което е делител на двете и, и. На английски език"най-голям общ делител" се изписва като "най-голям общ делител", а общото му обозначение е:

(тук символът "" означава делимост, т.е. "" означава "дели")

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

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

Този алгоритъм е описан за първи път в книгата на Евклид "Начало" (около 300 г. пр. н. е.), въпреки че, много вероятно, този алгоритъм има по-ранен произход.

Алгоритъм

Самият алгоритъм е изключително прост и се описва със следната формула:

Изпълнение

int gcd (int a, int b) (ако (b == 0) връща a; иначе връща gcd (b, a% b);)

Използвайки тройния условен оператор C ++, алгоритъмът може да бъде написан дори по-кратко:

int gcd (int a, int b) (връщане b? gcd (b, a% b): a;)

И накрая, ето нерекурсивна форма на алгоритъма:

int gcd (int a, int b) (докато (b) (a% = b; суап (a, b);) върне a;)

Доказателство за коректност

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

За доказателство за коректносттрябва да покажем това за всяко>.

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

Ние означаваме ... Тогава, по дефиниция, и.

Но тогава от това следва:

И така, запомняйки изявлението, получаваме системата:

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

Или, замествайки дефиницията му като вместо това, получаваме:

И така, извършихме половината от доказателството: показахме, че лявата страна разделя дясната. Втората половина на доказателството е подобна.

Работни часове

Времето за работа на алгоритъма се изчислява Теорема на Ламе, което установява невероятна връзка между евклидовия алгоритъм и последователността на Фибоначи:

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

Широко използван в електронната търговия. Също така, алгоритъмът се използва за решаване на линейни диофантови уравнения при конструиране на продължителни дроби по метода на Щурм. Алгоритъмът на Евклид е основният инструмент за доказване на теореми в съвременната теория на числата, като теоремата на Лагранж за сбора от четири квадрата и основната теорема на аритметиката.

Колегиален YouTube

1 / 5

✪ Математика. Естествени числа: алгоритъмът на Евклид. Онлайн учебен център Foxford

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

✪ Алгоритъм на Евклид, бърз начиннамерете gcd

✪ Математика 71. Най-голям общ делител. Алгоритъм на Евклид - Академия на развлекателните науки

✪ 20 While Loop Euclidean Python алгоритъм

Субтитри

История

Древногръцките математици наричат ​​този алгоритъм ἀνθυφαίρεσις или ἀνταναίρεσις - "взаимно изваждане". Този алгоритъм не е открит от Евклид, тъй като вече е споменат в ТопикаАристотел. В „Елементите“ на Евклид е описано два пъти – в VII книга за намиране на най-големия общ делител на две естествени числа и в X книга за намиране на най-голямата обща мярка на две еднородни величини. И в двата случая се дава геометрично описание на алгоритъма, за да се намери "общата мярка" на два сегмента.

Описание

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

Позволявам a (\ displaystyle a)и b (\ displaystyle b)- цели числа, които не са равни на нула едновременно, и поредица от числа

a> b> r 1> r 2> r 3> r 4>…> rn (\ displaystyle a> b> r_ (1)> r_ (2)> r_ (3)> r_ (4)> \ \ точки \ > r_ (n))

се определя от факта, че всеки r k (\ displaystyle r_ (k))- това е остатъкът от разделянето на предишното число на предишното, а предпоследното се дели на последното напълно, тоест:

a = b q 0 + r 1, (\ displaystyle a = bq_ (0) + r_ (1),) b = r 1 q 1 + r 2, (\ displaystyle b = r_ (1) q_ (1) + r_ (2),) r 1 = r 2 q 2 + r 3, (\ displaystyle r_ (1) = r_ (2) q_ (2) + r_ (3),) ⋯ (\ displaystyle \ cdots) r k - 2 = r k - 1 q k - 1 + r k, (\ displaystyle r_ (k-2) = r_ (k-1) q_ (k-1) + r_ (k),) ⋯ (\ displaystyle \ cdots) r n - 2 = r n - 1 q n - 1 + r n, (\ displaystyle r_ (n-2) = r_ (n-1) q_ (n-1) + r_ (n),) r n - 1 = r n q n. (\ displaystyle r_ (n-1) = r_ (n) q_ (n).)

След това gcd ( а, б), най-големият общ фактор аи б, е равно на r n, последният ненулев член в тази последователност.

Съществуванетакъв r 1 , r 2 , ..., r n, тоест възможността за деление с остатък мна нза всяко цяло ми цяла н≠ 0 се доказва чрез индукция по м.

Коректносттози алгоритъм следва от следните две твърдения:

• Позволявам а = б⋅q + r, тогава gcd (a, b) = gcd (b, r).

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

• GCD ( r, 0) = rза всяка различна от нула r(тъй като 0 се дели на всяко цяло число, различно от нула).

Геометричен евклидов алгоритъм

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

Пример

За илюстрация, алгоритъмът на Евклид ще бъде използван за намиране на GCD а= 1071 и б= 462. Като начало извадете кратно 462 от 1071, докато не получим разлика, по-малка от 462. Трябва да извадим 462 два пъти, ( q 0 = 2), оставайки с остатък от 147:

1071 = 2 × 462 + 147.

След това изваждаме кратно на 147 от 462, докато не получим разлика, по-малка от 147. Трябва да извадим 147 ( q 1 = 3), оставайки с остатък от 21:

462 = 3 × 147 + 21.

След това изваждаме кратно на 21 от 147, докато не получим разлика, по-малка от 21. Трябва да извадим 21 ( q 2 = 7), не оставяйки остатък:

147 = 7 × 21 + 0.

Така последователността a> b> r 1 > r 2 > r 3 > … > r n в този конкретен случай ще изглежда така:

1071 > 462 > 147 > 21.

Тъй като последният остатък е нула, алгоритъмът завършва с 21 и GCD (1071, 462) = 21.

В табличен вид стъпките бяха както следва:

Приложения

Разширен евклидов алгоритъм и съотношение на Безут

Формули за r i (\ displaystyle r_ (i))може да се пренапише, както следва:

r 1 = a + b (- q 0) (\ displaystyle r_ (1) = a + b (-q_ (0))) r 2 = b - r 1 q 1 = a (- q 1) + b (1 + q 1 q 0) (\ displaystyle r_ (2) = b-r_ (1) q_ (1) = a (-q_ ( 1)) + b (1 + q_ (1) q_ (0))) ⋮ (\ displaystyle \ vdots) Gcd (a, b) = r n = a s + b t (\ displaystyle (a, b) = r_ (n) = as + bt)

Тук си тцяла. Това представяне на най-големия общ делител се нарича коефициент на Безут и числата си т- Коефициенти на Безут. Отношението Безут е ключово в доказателството на лемата на Евклид и основната теорема на аритметиката.

Продължени дроби

Алгоритъмът на Евклид е тясно свързан с непрекъснати дроби. Поведение а/бможе да се представи като непрекъсната дроб:

a b = [q 0; q 1, q 2, ⋯, q n] (\ displaystyle (\ frac (a) (b)) =).

В този случай продължителната дроб без последния член е равна на съотношението на коефициентите на Безут т/свзето със знак минус:

[q 0; q 1, q 2, ⋯, q n - 1] = - t s (\ displaystyle = - (\ frac (t) (s))).

Последователността от равенства, определящи евклидовия алгоритъм, може да бъде пренаписана във вида:

ab = q 0 + r 0 bbr 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ rk - 2 rk - 1 = qk + rkrk - 1 ⋮ r N - 2 r N - 1 = q N (\ displaystyle (\ начало (подравнено) (\ frac (a) (b)) & = q_ (0) + (\ frac (r_ (0)) (b)) \\ (\ frac (b) ) (r_ (0))) & = q_ (1) + (\ frac (r_ (1)) (r_ (0))) \\ (\ frac (r_ (0)) (r_ (1))) & = q_ (2) + (\ frac (r_ (2)) (r_ (1))) \\ & () \ \ vdots \\ (\ frac (r_ (k-2)) (r_ (k-1) )) & = q_ (k) + (\ frac (r_ (k)) (r_ (k-1))) \\ & () \ \ vdots \\ (\ frac (r_ (N-2)) (r_ (N-1))) & = q_ (N) \ край (подравнен)))

Последният член от дясната страна на равенството винаги е равен на реципрочната стойност на лявата страна на следващото уравнение. Следователно първите две уравнения могат да се комбинират във формата:

ab = q 0 + 1 q 1 + r 1 r 0 (\ displaystyle (\ frac (a) (b)) = q_ (0) + (\ cfrac (1) (q_ (1) + (\ cfrac (r_ ( 1)) (r_ (0))))))

Третото равенство може да се използва за замяна на знаменателя на израз r 1 /r 0, получаваме:

ab = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\ displaystyle (\ frac (a) (b)) = q_ (0) + (\ cfrac (1) (q_ (1) + (\ cfrac (1) (q_ (2) + (\ cfrac (r_ (2)) (r_ (1)))))))

Последно съотношение на остатъци r к /r к−1 винаги може да бъде заменен със следващото равенство в последователността и така до последното уравнение. Резултатът е непрекъсната дроб:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [q 0; q 1, q 2,…, q N] (\ displaystyle (\ frac (a) (b)) = q_ (0) + (\ cfrac (1) (q_ (1) + (\ cfrac (1) (q_) (2) + (\ cfrac (1) (\ ddots + (\ cfrac (1) (q_ (N))))))))) =)

Обобщен евклидов алгоритъм за полиноми

Евклидовият алгоритъм и разширеният евклидов алгоритъм естествено се обобщават до пръстена от полиноми к[х] от една променлива върху произволно поле к, тъй като деленето с остатък е дефинирано за такива полиноми. Когато се изпълнява евклидовият алгоритъм за полиноми, подобно на евклидовия алгоритъм за цели числа, се получава последователност от полиномиални остатъци (PRS).

Пример за пръстен З[х]

Нека cont (f) по дефиниция е GCD на коефициентите на полинома f (x) от Z [x] - съдържаниеполином. Коефициентът на деление на f (x) на cont (f) се нарича примитивна частна полинома f (x) и се означава с primpart (f (x)). Тези дефиниции ще са необходими за намиране на GCD на два полинома p 1 (x)и p 2 (x)в пръстена Z [x]. За полиноми над цели числа е вярно следното:

C o n t ((\ displaystyle cont () NODNOD (c o n t (p 1 (x)), c o n t (p 2 (x))), (\ displaystyle \ (продължение (p_ (1) (x)), продължение (p_ (2) (x)) \),)

P r i m p a r t ((\ displaystyle primpart () Gcd (p 1 (x), p 2 (x))) = (\ displaystyle \ (p_ (1) (x), p_ (2) (x) \)) =) Gcd (p r i m p a r t (p 1 (x)), p r i m p a r t (p 2 (x))). (\ displaystyle \ (primpart (p_ (1) (x)), primpart (p_ (2) (x)) \).)

По този начин проблемът за намиране на НОД на два произволни полинома се свежда до проблема за намиране на НОД на примитивни полинома.

Нека има два примитивни полинома p 1 (x) и p 2 (x) от Z [x], за които е валидна връзката между техните степени: deg (p 1 (x)) = m и deg (p 2 (x)) = n, m> n. Делението на полиноми с остатък предполага точната делимост на водещия коефициент на делителя на старшия коефициент на делителя; в общия случай делението с остатъка е невъзможно. Поради това се въвежда алгоритъм за псевдоразделяне, който въпреки това позволява да се получи псевдочестота и псевдо остатък (prem), които сами по себе си принадлежат към множеството от полиноми над цели числа.

Под псевдоделение имаме предвид, че самото деление се предхожда от умножението на полинома p 1 (x) (\ displaystyle p_ (1) (x))на (l c (p 2 (x))) m - n + 1 (\ displaystyle (lc (p_ (2) (x))) ^ (m-n + 1)), това е

L c (p 2 (x)) m - n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x), deg ⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

където q (x) (\ displaystyle q (x))и r (x) (\ displaystyle r (x))- съответно псевдочестота и псевдо остатъчна.

Така, p 1 (x), p 2 (x) ∈ Z [x] (\ displaystyle p_ (1) (x), p_ (2) (x) \ in Z [x]), и deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 (\ displaystyle \ deg (p_ (1)) = n_ (1) \ geq \ deg (p_ (2)) = n_ (2) )... Тогава алгоритъмът на Евклид се състои от следните стъпки:

1. Изчисляване на съдържанието на GCD:

C: = (\ displaystyle c: =) Gcd (c o n t (p 1), c o n t (p 2)) (\ displaystyle \ (продължение (p_ (1)), продължение (p_ (2)) \)).

2. Изчисляване на примитивни части:

P 1 ′ (x): = p r i m p a r t (p 1 (x)); (\ displaystyle p_ (1) "(x): = primpart (p_ (1) (x));)

P 2 ′ (x): = p r i m p a r t (p 2 (x)). (\ displaystyle p_ (2) "(x): = primpart (p_ (2) (x)).)

3. Построяване на последователност от полиномни остатъци:

P 1 ′ (x), (\ displaystyle p_ (1) "(x),)

P 2 ′ (x), (\ displaystyle p_ (2) "(x),)

P 3 (x): = prem (p 1 ′ (x), p 2 ′ (x)), (\ displaystyle p_ (3) (x): = prem (p_ (1) "(x), p_ (2) ) "(х)),)

P 4 (x): = prem (p 2 ′ (x), p 3 (x)), (\ displaystyle p_ (4) (x): = prem (p_ (2) "(x), p_ (3) (х)),)

P 5 (x): = prem (p 3 (x), p 4 (x)), (\ displaystyle p_ (5) (x): = prem (p_ (3) (x), p_ (4) (x) )))

... ... ... (\ displaystyle ...)

P h (x): = p r e m (p h - 2 (x), p h - 1 (x)). (\ displaystyle p_ (h) (x): = prem (p_ (h-2) (x), p_ (h-1) (x)).)

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

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

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

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

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 е най-големият общ делител на числата в условието.

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

Пример 2

Какво е GCD на числата 111 и 432 ?

Решение

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

По този начин, най-големият общ делител на числата 111 и 432 е 3.

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

Пример 3

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

Решение

Нека извършим последователно деление на числата и да получим gcd (661 , 113) = 1 ... Това означава, че 661 и 113 са взаимно прости числа. Бихме могли да разберем това, преди да започнем изчислението, ако погледнем таблицата на простите числа.

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

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

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

Пример 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.

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

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

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

Независимо от броя на числата, за които трябва да намерим GCD, ще действаме по същия алгоритъм, който се състои в последователно намиране на GCD на две числа. Този алгоритъм се основава на прилагането на следната теорема: GCD на няколко числа а 1, а 2,..., а кравно на числото г к, което се намира в последователното изчисление на GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3, GCD (d 3, a 4) = d 4, ..., GCD (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 = gcd (d 2, a 3) = gcd (6, 570). Според алгоритъма на Евклид 570 = 6 · 95.Означава, че d 3 = Gcd (6 , 570) = 6 .

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

d 4 = 6, тоест gcd (78 , 294 , 570 , 36) = 6 .

Отговор:

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

Пример 7

Изчислете 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.

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

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

Намиране на gcd за отрицателни числа

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

Пример 8

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

Решение

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

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

Отговор: GCD (- 231, - 140) = 7.

Пример 9

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

Решение

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

Отговор: GCD (- 585, 81, - 189) = 9.

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