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

Много делители

Помислете за следния проблем: намерете делителя на числото 140. Очевидно е, че числото 140 има не един делител, а няколко. В такива случаи се казва, че задачата има няколкорешения. Нека ги намерим всички. Първо, разлагаме това число на прости множители:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Сега можем лесно да изпишем всички делители. Нека започнем с прости делители, тоест тези, които присъстват в разширението по-горе:

След това изписваме тези, които се получават чрез умножение по двойки на прости делители:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

След това - тези, които съдържат три прости делителя:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

И накрая, нека не забравяме единицата и самото разложимо число:

Формират се всички намерени от нас делители няколкоделители на числото 140, което се записва с къдрави скоби:

Множеството от делители на числото 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

За удобство на възприемането тук сме изписали делителите ( набор елементи) във възходящ ред, но най-общо казано, това не е необходимо. Освен това въвеждаме съкращение. Вместо "Множество делители на числото 140" ще напишем "D (140)". По този начин,

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

105 = 3 ∙ 5 ∙ 7

получаваме:

D(105) = (1, 3, 5, 7, 15, 21, 35, 105).

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

PD(140) = (2, 5, 7).

PD(105) = (3, 5, 7).

Трябва да се подчертае, че при разлагането на числото 140 на прости множители две присъстват два пъти, докато в множеството PD(140) е само едно. Множеството от PD(140) по същество е всички отговори на задачата: "Намерете прост множител на числото 140". Ясно е, че един и същ отговор не трябва да се повтаря повече от веднъж.

Намаляване на фракцията. Най-голям общ делител

Помислете за дроб

Знаем, че тази дроб може да бъде намалена с число, което е едновременно делител на числителя (105) и делител на знаменателя (140). Нека разгледаме множествата D(105) и D(140) и да запишем техните общи елементи.

D(105) = (1, 3, 5, 7, 15, 21, 35, 105);

D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).

Общи елементи на множествата D(105) и D(140) =

Последното равенство може да се запише по-кратко, а именно:

D(105) ∩ D(140) = (1, 5, 7, 35).

Тук специалната икона "∩" ("чанта с дупката надолу") просто показва, че от двата набора, написани от противоположните й страни, трябва да бъдат избрани само общи елементи. Записът "D (105) ∩ D (140)" гласи " пресичанекомплекти Te от 105 и Te от 140.

[Забележете по пътя, че можете да извършвате различни бинарни операции с набори, почти като с числа. Друга често срещана двоична операция е съюз, което се обозначава с иконата "∪" ("чанта с отвора нагоре"). Обединението на две множества включва всички елементи на двете множества:

PD(105) = (3, 5, 7);

PD(140) = (2, 5, 7);

PD(105) ∪ PD(140) = (2, 3, 5, 7). ]

И така, разбрахме, че фракцията

може да се сведе до всяко от числата, принадлежащи на множеството

D(105) ∩ D(140) = (1, 5, 7, 35)

и не може да се намали с друго естествено число. Ето всички възможни начини за намаляване (с изключение на безинтересното намаляване с един):

Очевидно е, че най-практично е дробът да се намали с число, ако е възможно, по-голямо. В този случай се казва, че е числото 35 най-голям общ делител (GCD) числа 105 и 140. Това се записва като

gcd(105, 140) = 35.

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

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Умножавайки подчертаните числа (в което и да е от разширенията), получаваме:

gcd(105, 140) = 5 ∙ 7 = 35.

Разбира се, възможно е да има повече от два подчертани фактора:

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

От тук става ясно, че

gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.

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

42 = 2 ∙ 3 ∙ 7;

В такъв случай,

gcd(42, 55) = 1.

Извикват се две естествени числа, за които gcd е равно на едно взаимно прости. Ако направите дроб от такива числа, напр.

тогава такава дроб е несводим.

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

		а/ gcd( а, б)
		б/ gcd( а, б)

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

Събиране и изваждане на дроби. Най-малко общо кратно

Да предположим, че искате да изчислите сумата от две дроби:

Вече знаем как знаменателите се разлагат на прости множители:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

От това разлагане веднага следва, че за да доведем дробите до общ знаменател, е достатъчно числителят и знаменателят на първата дроб да се умножат по 2 ∙ 2 (продуктът на ненапрегнатите прости множители на втория знаменател) и числителя и знаменателя на втората дроб по 3 („продукт“ неподчертани прости множители на първия знаменател). В резултат на това знаменателите на двете дроби ще станат равни на число, което може да бъде представено, както следва:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Лесно е да се види, че и двата оригинални знаменателя (и 105, и 140) са делители на числото 420, а числото 420 от своя страна е кратно на двата знаменателя - и не просто кратно, то е най-малко общо кратно (НОК) числа 105 и 140. Това се пише така:

LCM(105, 140) = 420.

Разглеждайки по-отблизо разширяването на числата 105 и 140, виждаме това

105 ∙ 140 = LCM(105, 140) ∙ GCD(105, 140).

По същия начин, за произволни естествени числа би д:

б ∙ д= LCM( б, д) ∙ GCD( б, д).

Сега нека завършим сумирането на нашите дроби:

3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 5 ∙ 7

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 3 ∙ 5 ∙ 7

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7

2 ∙ 2 ∙ 3 ∙ 5

Забележка.За да решите някои задачи, трябва да знаете какъв е квадратът на число. Числово квадратче анаречен номер аумножено по себе си, т.е а∙а. (Както можете да видите, той е равен на площта на квадрат със страна а).

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

Основни понятия

Делителят на цяло число X е друго цяло число Y, на което X се дели без остатък. Например, делителят на 4 е 2, а 36 е 4, 6, 9. Кратно на цялото число X е число Y, което се дели на X без остатък. Например 3 е кратно на 15, а 6 е кратно на 12.

За всяка двойка числа можем да намерим общите им делители и кратни. Например за 6 и 9 общото кратно е 18, а общият делител е 3. Очевидно двойките могат да имат няколко делителя и кратни, така че при изчисленията се използват най-големият делител на GCD и най-малкото кратно на LCM .

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

Намиране на GCD

Има много методи за намиране на най-големия общ делител, най-известните от които са:

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

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

Намиране на NOC

Най-малкото общо кратно също се определя точно чрез итеративно изброяване или разлагане на неделими фактори. Освен това е лесно да се намери LCM, ако най-големият делител вече е определен. За числата X и Y LCM и GCD са свързани чрез следната връзка:

LCM(X,Y) = X × Y / GCM(X,Y).

Например, ако gcd(15,18) = 3, тогава LCM(15,18) = 15 × 18 / 3 = 90. Най-очевидната употреба на LCM е да се намери общият знаменател, който е най-малкото общо кратно на дадени дроби.

Взаимно прости числа

Ако двойка числа няма общи делители, тогава такава двойка се нарича взаимно проста. GCM за такива двойки винаги е равен на единица и въз основа на връзката на делителите и кратните, GCM за взаимно простите е равен на тяхното произведение. Например числата 25 и 28 са взаимно прости, тъй като нямат общи делители и LCM(25, 28) = 700, което съответства на тяхното произведение. Всякакви две неделими числа винаги ще бъдат взаимно прости.

Общ делител и множествен калкулатор

С нашия калкулатор можете да изчислите GCD и LCM за произволен брой числа, от които да избирате. Задачите за изчисляване на общи делители и кратни се намират в аритметиката на 5 и 6 клас, но GCD и LCM са ключовите понятия на математиката и се използват в теорията на числата, планиметрията и комуникативната алгебра.

Примери от реалния живот

Общ знаменател на дроби

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

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

За да добавите дроби, изразът трябва да бъде сведен до общ знаменател, което се свежда до проблема за намиране на LCM. За да направите това, изберете 5 числа в калкулатора и въведете стойностите на знаменателя в съответните клетки. Програмата ще изчисли LCM (8, 9, 12, 15, 18) = 360. Сега трябва да изчислите допълнителни фактори за всяка фракция, които се определят като отношението на LCM към знаменателя. Така че допълнителните множители ще изглеждат така:

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

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

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Можем лесно да добавим такива дроби и да получим резултата под формата на 159/360. Намаляваме дроба с 3 и виждаме крайния отговор - 53/120.

Решение на линейни диофантови уравнения

Линейните диофантови уравнения са изрази от вида ax + by = d. Ако съотношението d / gcd(a, b) е цяло число, тогава уравнението е разрешимо в цели числа. Нека проверим няколко уравнения за възможността за целочислено решение. Първо проверете уравнението 150x + 8y = 37. С помощта на калкулатор намираме gcd (150,8) = 2. Разделете 37/2 = 18,5. Числото не е цяло число, следователно, уравнението няма цели числа.

Нека проверим уравнението 1320x + 1760y = 10120. Използвайте калкулатор, за да намерите gcd(1320, 1760) = 440. Разделете 10120/440 = 23. В резултат на това получаваме цяло число, следователно диофантовият коефициент е равен на коефициента в e .

Заключение

GCD и LCM играят важна роля в теорията на числата, а самите понятия се използват широко в различни области на математиката. Използвайте нашия калкулатор, за да изчислите най-големите делители и най-малките кратни на произволен брой числа.

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

Определение 2

Ако естествено число a се дели на естествено число $b$, тогава $b$ се нарича делител на $a$, а числото $a$ се нарича кратно на $b$.

Нека $a$ и $b$ са естествени числа. Числото $c$ се нарича общ делител както за $a$, така и за $b$.

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

$gcd \ (a;b) \ ​​или \ D \ (a;b)$

За да намерите най-големия общ делител на две числа:

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

Пример 1

Намерете gcd на числата $121$ и $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Изберете числата, които са включени в разширението на тези числа

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

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

$gcd=2\cdot 11=22$

Пример 2

Намерете GCD на мономи $63$ и $81$.

Ще намерим според представения алгоритъм. За това:

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

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Избираме числата, които са включени в разширението на тези числа

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

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

$gcd=3\cdot 3=9$

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

Пример 3

Намерете gcd на числата $48$ и $60$.

решение:

Намерете множеството от делители на $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Сега нека намерим набора от делители на $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$

Нека намерим пресечната точка на тези множества: $\left\((\rm 1,2,3,4,6,12)\right\)$ - този набор ще определи множеството от общи делители на числата $48$ и $60 $. Най-големият елемент в този набор ще бъде числото $12$. Така че най-големият общ делител на $48$ и $60$ е $12$.

Определение за NOC

Определение 3

общо кратно на естествените числа$a$ и $b$ е естествено число, което е кратно както на $a$, така и на $b$.

Общите кратни на числата са числа, които се делят на оригинала без остатък. Например за числата $25$ и $50$ общите кратни ще бъдат числата $50,100,150,200$ и т.н.

Най-малкото общо кратно ще се нарича най-малко общо кратно и ще се означава с LCM$(a;b)$ или K$(a;b).$

За да намерите LCM на две числа, трябва:

1. Разложете числата на прости множители
2. Изпишете факторите, които са част от първото число и добавете към тях факторите, които са част от второто и не отиват към първото

Пример 4

Намерете LCM на числата $99$ и $77$.

Ще намерим според представения алгоритъм. За това

Разложете числата на прости множители

$99=3\cdot 3\cdot 11$

Запишете факторите, включени в първия

добавете към тях фактори, които са част от второто и не отиват към първото

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

$LCC=3\cdot 3\cdot 11\cdot 7=693$

Съставянето на списъци с делители на числа често отнема много време. Има начин да се намери GCD, наречен алгоритъм на Евклид.

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

Ако $a$ и $b$ са естествени числа и $a\vdots b$, тогава $D(a;b)=b$

Ако $a$ и $b$ са естествени числа, такива че $b

Използвайки $D(a;b)= D(a-b;b)$, можем последователно да намаляваме разглежданите числа, докато стигнем до двойка числа, така че едното от тях да се дели на другото. Тогава по-малкото от тези числа ще бъде желаният най-голям общ делител за числата $a$ и $b$.

Свойства на GCD и LCM

1. Всяко общо кратно на $a$ и $b$ се дели на K$(a;b)$
2. Ако $a\vdots b$, тогава K$(a;b)=a$

Ако K$(a;b)=k$ и $m$-естествено число, тогава K$(am;bm)=km$

Ако $d$ е общ делител за $a$ и $b$, тогава K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Ако $a\vdots c$ и $b\vdots c$, тогава $\frac(ab)(c)$ е общо кратно на $a$ и $b$

За произволни естествени числа $a$ и $b$ равенството

$D(a;b)\cdot K(a;b)=ab$

Всеки общ делител на $a$ и $b$ е делител на $D(a;b)$

Но много естествени числа се делят равномерно на други естествени числа.

например:

Числото 12 се дели на 1, на 2, на 3, на 4, на 6, на 12;

Числото 36 се дели на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.

Числата, на които числото се дели (за 12 е 1, 2, 3, 4, 6 и 12) се наричат делители на числа. Делител на естествено число ае естественото число, което дели даденото число абез следа. Нарича се естествено число, което има повече от два фактора композитен. Обърнете внимание, че числата 12 и 36 имат общи делители. Това са числата: 1, 2, 3, 4, 6, 12. Най-големият делител на тези числа е 12.

Общ делител на две дадени числа аи бе числото, на което и двете дадени числа се делят без остатък аи б. Общ делител на множество числа (GCD)е числото, което служи като делител за всяко от тях.

Накратко най-големият общ делител на числата аи бса написани така:

Пример: gcd (12; 36) = 12.

Делите на числата в записа на решението се означават с главна буква "D".

пример:

gcd (7; 9) = 1

Числата 7 и 9 имат само един общ делител - числото 1. Такива числа се наричат взаимно простичи шлем.

Взаимно прости числаса естествени числа, които имат само един общ делител - числото 1. Техният gcd е 1.

Най-голям общ делител (GCD), свойства.

• Основно свойство: най-голям общ делител ми нсе дели на всеки общ делител на тези числа. Пример: за числа 12 и 18 най-големият общ делител е 6; той се дели на всички общи делители на тези числа: 1, 2, 3, 6.
• Следствие 1: набор от общи делители ми нсъвпада с множеството делители gcd( м, н).
• Следствие 2: набор от общи кратни ми нсъвпада с набора от множество LCM ( м, н).

Това означава по-специално, че за да се сведе дроб до неприводима форма, е необходимо да се разделят нейните числител и знаменател на техния gcd.

• Най-голям общ делител на числата ми нможе да се определи като най-малкия положителен елемент от множеството от всичките им линейни комбинации:

и следователно представляват като линейна комбинация от числа ми н:

Това съотношение се нарича Съотношението на Безут, и коефициентите uи v — безаут коефициенти. Коефициентите на Безу се изчисляват ефективно от разширения алгоритъм на Евклид. Това твърдение е обобщено за набори от естествени числа - значението му е, че подгрупата на групата, генерирана от множеството, е циклична и се генерира от един елемент: gcd ( а 1 , а 2 , … , a n).

Изчисляване на най-големия общ делител (gcd).

Ефективни начини за изчисляване на gcd на две числа са Алгоритъм на Евклиди двоиченалгоритъм. В допълнение, стойността на GCD ( м,н) може лесно да се изчисли, ако е известно каноничното разширение на числата ми нза прости фактори:

където са различни прости числа и и са неотрицателни цели числа (те може да са нула, ако съответното просто число не е в разлагането). След това gcd ( м,н) и LCM ( м,н) се изразяват с формулите:

Ако има повече от две числа: , техният GCD се намира по следния алгоритъм:

- това е желаният GCD.

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

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

1. Разложете делителите на числата на прости множители:

Изчисленията се записват удобно с помощта на вертикална лента. Отляво на реда първо запишете дивидента, вдясно - делителя. По-нататък в лявата колона записваме стойностите на private. Нека обясним веднага с пример. Нека размножим числата 28 и 64 на прости множители.

2. Подчертаваме едни и същи прости множители и в двете числа:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Намираме произведението на еднакви прости множители и записваме отговора:

GCD (28; 64) = 2. 2 = 4

Отговор: GCD (28; 64) = 4

Можете да подредите местоположението на GCD по два начина: в колона (както беше направено по-горе) или „в ред“.

Първият начин да напишете GCD:

Намерете GCD 48 и 36.

GCD (48; 36) = 2. 2. 3 = 12

Вторият начин да напишете GCD:

Сега нека напишем решението за търсене на GCD на ред. Намерете GCD 10 и 15.

D(10) = (1, 2, 5, 10)

D(15) = (1, 3, 5, 15)

D(10, 15) = (1, 5)

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

Yandex.RTB R-A-339285-1

Какво представляват общите делители

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

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

Определение 1

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

Пример 1

Ето примери за такъв делител: тройката ще бъде общ делител за числата - 12 и 9, тъй като равенствата 9 = 3 · 3 и − 12 = 3 · (− 4) са верни. Числата 3 и - 12 имат други общи делители, като 1 , - 1 и - 3 . Да вземем друг пример. Четирите цели числа 3 , − 11 , − 8 и 19 ще имат два общи делителя: 1 и - 1 .

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

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

Какъв е най-големият общ делител (gcd)

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

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

Преминаваме към формулирането на основното определение.

Определение 2

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

В писмен вид най-големият общ делител най-често се обозначава със съкращението GCD. За две числа може да се запише като gcd (a, b) .

Пример 2

Какъв е примерът за GCD за две цели числа? Например, за 6 и - 15 би било 3 . Нека обосноваваме това. Първо, записваме всички делители на шест: ± 6, ± 3, ± 1, а след това всички делители на петнадесет: ± 15, ± 5, ± 3 и ± 1. След това избираме общи: това са − 3 , − 1 , 1 и 3 . От тях трябва да изберете най-голямото число. Това ще бъде 3.

За три или повече числа дефиницията на най-големия общ делител ще бъде почти същата.

Определение 3

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

За числа a 1 , a 2 , … , a n делителят е удобно обозначен като GCD (a 1 , a 2 , … , a n) . Самата стойност на делителя се записва като GCD (a 1 , a 2 , …, a n) = b .

Пример 3

Ето примери за най-големия общ делител на няколко цели числа: 12 , - 8 , 52 , 16 . Ще бъде равно на четири, което означава, че можем да запишем, че gcd (12, - 8, 52, 16) = 4.

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

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

Пример 4

И така, най-големият общ делител на числата 60, 15 и - 45 е 15, тъй като петнадесет се дели не само на 60 и - 45, но и на себе си и няма по-голям делител за всички тези числа.

Взаимно простите числа са специален случай. Те са цели числа с най-голям общ делител на 1.

Основни свойства на GCD и алгоритъма на Евклид

Най-големият общ делител има някои характерни свойства. Формулираме ги под формата на теореми и доказваме всяка една от тях.

Имайте предвид, че тези свойства са формулирани за цели числа, по-големи от нула, и ние разглеждаме само положителни делители.

Определение 4

Числата a и b имат най-големия общ делител, равен на gcd за b и a, т.е. gcd (a, b) = gcd (b, a) . Промяната на местата на числата не влияе на крайния резултат.

Това свойство следва от самото определение на GCD и не се нуждае от доказателство.

Определение 5

Ако числото a може да бъде разделено на числото b, тогава множеството общи делители на тези две числа ще бъде подобно на множеството от делители на числото b, тоест gcd (a, b) = b.

Нека докажем това твърдение.

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

Ако числата a и b имат общи делители, тогава всяко от тях може да бъде разделено на тях. В същото време, ако a е кратно на b, тогава всеки делител на b също ще бъде делител на a , тъй като делимостта има такова свойство като транзитивност. Следователно всеки делител b ще бъде общ за числата a и b. Това доказва, че ако можем да разделим a на b, тогава множеството от всички делители на двете числа съвпада с множеството от делители на едно число b. И тъй като най-големият делител на всяко число е самото число, то най-големият общ делител на числата a и b също ще бъде равен на b, т.е. gcd(a, b) = b. Ако a = b, тогава gcd (a, b) = gcd (a, a) = gcd (b, b) = a = b, например gcd (132, 132) = 132.

Използвайки това свойство, можем да намерим най-големия общ делител на две числа, ако едното от тях може да бъде разделено на другото. Такъв делител е равен на едно от тези две числа, на които може да се раздели второто число. Например, gcd (8, 24) = 8, защото 24 е кратно на осем.

Определение 6 Доказателство 2

Нека се опитаме да докажем това свойство. Първоначално имаме равенството a = b q + c и всеки общ делител на a и b също ще раздели c, което се обяснява със съответното свойство на делимост. Следователно всеки общ делител на b и c ще раздели a . Това означава, че множеството от общи делители a и b ще съвпада с множеството от делители b и c, включително най-големия от тях, което означава, че равенството gcd (a, b) = gcd (b, c) е вярно.

Определение 7

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

Преди да формулирате свойството, ви съветваме да повторите теоремата, която доказахме в статията за деление с остатък. Според него делимото число a може да бъде представено като b q + r, като тук b е делител, q е някакво цяло число (нарича се още непълно частно), а r е остатък, който отговаря на условието 0 ≤ r ≤ б.

Да кажем, че имаме две цели числа, по-големи от 0, за които следните равенства ще са верни:

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 . Това определено ще се случи, тъй като последователността b > r 1 > r 2 > r 3 , … е поредица от намаляващи цели числа, които могат да включват само краен брой от тях. Следователно r k е най-големият общ делител на a и b , тоест r k = gcd (a , b) .

Първо, трябва да докажем, че r k е общ делител на числата a и b, а след това, че r k не е просто делител, а най-големият общ делител на двете дадени числа.

Нека разгледаме списъка с равенства по-горе, отдолу нагоре. Според последното равенство,
r k − 1 може да се раздели на r k . Въз основа на този факт, както и на предишното доказано свойство на най-големия общ делител, може да се твърди, че r k − 2 може да бъде разделено на r k , тъй като
r k − 1 се дели на r k и r k се дели на r k .

Третото равенство отдолу ни позволява да заключим, че r k − 3 може да се раздели на r k и т.н. Второто отдолу е, че b се дели на r k , а първото е, че a се дели на r k . От всичко това заключаваме, че r k е общ делител на a и b .

Сега нека докажем, че r k = gcd (a , b) . Какво трябва да направя? Покажете, че всеки общ делител на a и b ще раздели r k . Нека го означим r 0 .

Нека разгледаме същия списък с равенства, но отгоре надолу. Въз основа на предишното свойство можем да заключим, че r 1 се дели на r 0 , което означава, че според второто равенство r 2 се дели на r 0 . Слизаме през всички равенства и от последното заключаваме, че r k се дели на r 0 . Следователно r k = gcd (a, b) .

След като разгледахме това свойство, заключаваме, че множеството от общи делители на a и b е подобно на множеството от делители на gcd на тези числа. Това твърдение, което е следствие от алгоритъма на Евклид, ще ни позволи да изчислим всички общи делители на две дадени числа.

Нека да преминем към други свойства.

Определение 8

Ако a и b са цели числа, които не са равни на 0, тогава трябва да има две други цели числа u 0 и v 0, за които ще е валидно равенството gcd (a , b) = a · u 0 + b · v 0.

Равенството, дадено в изявлението за свойството, е линейно представяне на най-големия общ делител на a и b. Нарича се коефициент на Безут, а числата u 0 и v 0 се наричат ​​коефициенти на Безут.

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

Нека докажем това свойство. Записваме последователността от равенства според алгоритъма на Евклид:

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 1 = a − b · q 1 . Означете 1 = s 1 и − q 1 = t 1 и пренапишете това равенство като r 1 = s 1 · a + t 1 · b . Тук числата s 1 и t 1 ще бъдат цели числа. Второто равенство ни позволява да заключим, че r 2 = b − r 1 q 2 = b − (s 1 a + t 1 b) q 2 = − s 1 q 2 a + (1 − t 1 q 2) b . Означете − s 1 q 2 = s 2 и 1 − t 1 q 2 = t 2 и пренапишете равенството като r 2 = s 2 a + t 2 b , където s 2 и t 2 също ще бъдат цели числа. Това е така, защото сборът от цели числа, тяхното произведение и разлика също са цели числа. По абсолютно същия начин получаваме от третото равенство r 3 = s 3 · a + t 3 · b , от следното r 4 = s 4 · a + t 4 · b и т.н. Накрая заключаваме, че r k = s k a + t k b за цели числа s k и t k . Тъй като r k = GCD (a, b) обозначаваме s k = u 0 и t k = v 0. В резултат на това можем да получим линейно представяне на GCD в необходимата форма: GCD (a, b) \u003d a u 0 + b v 0.

Определение 9

gcd (m a, m b) = m gcd (a, b) за всяка естествена стойност m.

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

Това свойство може да се обоснове по следния начин. Умножете по числото m двете страни на всяко равенство в алгоритъма на Евклид и получаваме, че gcd (m a , m b) = m r k , а r k е gcd (a , b) . Следователно gcd (m a, m b) = m gcd (a, b) . Именно това свойство на най-големия общ делител се използва при намиране на GCD по метода на факторизация.

Определение 10

Ако числата a и b имат общ делител p, тогава gcd (a: p, b: p) = gcd (a, b): p. В случай, когато p = gcd (a , b) получаваме gcd (a: gcd (a , b) , b: gcd (a , b) = 1, следователно числата a: gcd (a , b) и b : gcd (a, b) са взаимно прости.

Тъй като a = p (a: p) и b = p (b: p) , тогава, въз основа на предишното свойство, можем да създадем равенства от формата gcd (a , b) = gcd (p (a: p) , p · (b: p)) = p · GCD (a: p , b: p) , сред които ще има доказателство за това свойство. Ние използваме това твърдение, когато свеждаме обикновените дроби до неприводима форма.

Определение 11

Най-големият общ делител a 1 , a 2 , … , a k ще бъде числото d k , което може да се намери чрез последователно изчисляване 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 .

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

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

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