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

Определение 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

Намерете НОД на мономите $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

Намерете НОД на числата $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$.

Дефиниция на NPL

Определение 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. Полученото число ще бъде желаното най-малко общо кратно

    $NOK=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$ , тогава К$(a;b)=a$

    3. Ако 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 К(a;b)=ab$

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

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

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

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

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

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

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

Пример 1

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

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

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

Кой е най-големият общ делител (НОД)

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

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

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

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

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

Писмено най-големият общ делител най-често се обозначава със съкращението НОД. За две числа може да се запише като 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 е удобно делителят да се означава като НОД (a 1, a 2, …, a n). Стойността на самия делител се записва като НОД (a 1, a 2, ..., a n) = b.

Пример 3

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

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

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

Пример 4

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

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

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

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

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

Определение 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, т.е. НОД (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

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

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

Да кажем, че имаме две цели числа, по-големи от 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 = НОД (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, за които ще бъде валидно равенството НОД (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 = НОД (a, b), означаваме s k = u 0 и t k = v 0. В резултат на това можем да получим линейно представяне на НОД в необходимата форма: НОД (a, b) = a · u 0 + b · v 0.

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

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

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

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

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

Ако числата a и b имат общ делител p, тогава gcd (a: p, b: p) = gcd (a, b): p. В случай, когато p = НОД (a, b), получаваме НОД (a: НОД (a, b), b: НОД (a, b) = 1, следователно числата a: НОД (a, b) и b : НОД (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, което може да се намери чрез последователно изчисляване на НОД (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 .

Това свойство е полезно при намиране на най-големия общ делител на три или повече числа. Използвайки го, можете да намалите това действие до операции с две числа. Неговата основа е следствие от алгоритъма на Евклид: ако множеството от общи делители 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 ще бъде самото това число, тогава НОД (a 1, a 2, ..., a k) = d k.

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

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

Да решим проблема. Имаме два вида бисквитки. Някои са шоколадови, а други обикновени. Има 48 шоколадови и 36 обикновени. Трябва да направите максималния възможен брой подаръци от тези бисквитки и трябва да ги използвате всички.

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

получаваме

  • 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
  • 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

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

Общите множители ще бъдат: 1, 2, 3, 4, 6, 12.

Най-големият общ делител на всички е числото 12. Това число се нарича най-голям общ делител на числата 36 и 48.

Въз основа на получените резултати можем да заключим, че от всички бисквитки могат да се направят 12 подаръка. Един такъв подарък ще съдържа 4 шоколадови бисквитки и 3 обикновени бисквитки.

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

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

Понякога съкращението GCD се използва за съкращаване на записа.

Някои двойки числа имат единица като най-голям общ делител. Такива номера се наричат взаимно прости числа.Например, числата 24 и 35 имат НОД =1.

Как да намерим най-големия общ делител

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

Можете да го направите по различен начин. Първо разложете двете числа на прости множители.

  • 48 = 2*2*2*2*3,
  • 36 = 2*2*3*3.

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

  • 48 = 2*2*2*2*3 ,
  • 36 = 2*2*3 *3.

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

Това правило може да се разшири до случая на три, четири и т.н. числа.

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

  • 1. Разделете числата на прости множители.
  • 2. От факторите, включени в разширяването на едно от тези числа, задраскайте тези, които не са включени в разширяването на други числа.
  • 3. Изчислете произведението на останалите множители.

Глава 1. Естествени числа

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

По-рано назовахме делителите на числата. Сега нека се опитаме да разделим съставните числа на прости множители.

Определение

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

Разлагането на прости множители на числата ще изглежда така:
; .
Разлагането на прости множители на числата , , може да бъде представено в друга форма:


198 2
2574 2
255 3
3 1287 3
5
3
3 17
11
11



13










Сега ще запиша това на ред
.

Много добре! Ти си просто гений.

Все още не разбирам как така бързо се досетихте, че числото се дели на ?

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

Определение

Числото, на което се дели всяко от тези числа, се нарича общ делител на тези числа.

Тези. в нашия случай числото е общият делител?

Да, това исках да кажа. И ако вземете числата и , тогава, както можете да видите, те имат три общи делителя: , и (без да се брои ).

Не разбирам?...

Определение

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

Трябва да запомните, че GCD играе голяма роля в математиката.

Вече виждам, че в математиката всички понятия играят голяма роля. И как да ги запомним всички? Как да намеря този GCD?

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

Това е добре Но има числа, които нямат общи делители освен единица! Например и , и .

Да, прав си.

Определение

Числата, които нямат общи делители (освен единица), се наричат ​​относително прости.

И така, какво означава това: всички прости числа също ще бъдат относително прости?

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

Определение

Числото, което се дели на всяко от тези числа, се нарича общо кратно на тези числа.

И така, за числата и общото кратно ще бъде всяко от числата: , , , , LCM.

браво Какво мислите, че ще бъде LCM на взаимно простите числа?

Сега ще го разбера. Те нямат общи делители, различни от единица, и следователно техният продукт е техният LCM!

Това е просто невероятно! Какво страхотно заключение.
И в края на нашето изследване, искам да ви кажа как да намерите LOC, ако не е очевиден.

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

Да, доволна съм, хареса ми.


Тази статия е за намиране на най-голям общ делител (НОД)две или повече числа. Първо, нека разгледаме алгоритъма на Евклид; той ви позволява да намерите 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. Следователно gcd(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. Така gcd(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.