$p$ се нарича просто число, ако има само $2$ делители: $1$ и себе си.
Разделител естествено число$a$ е естествено число, на което оригиналното число $a$ се дели без остатък.
Пример 1
Намерете делителите на числото $6$.
Решение: Трябва да намерим всички числа, на които даденото число $6$ се дели без остатък. Това ще бъдат числата: $1,2,3, 6$. Така че делителя на числото $6$ ще бъдат числата $1,2,3,6.$
Отговор: $1,2,3,6$.
Това означава, че за да намерите делителите на едно число, трябва да намерите всички естествени числа, на които даденото число се дели без остатък. Лесно се вижда, че числото $1$ ще бъде делител на всяко естествено число.
Определение 2
КомпозитенТе наричат число, което има други делители освен единица и себе си.
Пример за просто число би било числото $13$, пример за съставно число би било $14.$
Бележка 1
Числото $1$ има само един делител - самото число, така че не е нито просто, нито съставно.
Взаимопрости числа
Определение 3
Взаимно прости числате са тези, чиято gcd е равна на $1$.Това означава, че за да разберете дали числата са относително прости, трябва да намерите тяхната gcd и да я сравните с $1$.
Двойно взаимно прости
Определение 4
Ако в набор от числа всеки две са взаимно прости, тогава такива числа се наричат взаимно прости по двойки. За две числа понятията „взаимопрости“ и „двойно взаимно прости“ съвпадат.
Пример 2
$8, $15 - не просто, но относително просто.
$6, 8, 9$ са взаимно прости числа, но не и взаимно прости числа по двойки.
$8, 15, 49$ са относително прости по двойки.
Както виждаме, за да определим дали числата са взаимно прости, първо трябва да ги разложим на основни фактори. Нека да обърнем внимание как да направим това правилно.
Разлагане на прости множители
Например, нека разложим числото $180$ на прости множители:
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$
Нека използваме свойството на правомощията, тогава получаваме,
$180=2^2\cdot 3^2\cdot 5$
Тази нотация на разлагане на прости множители се нарича канонична, т.е. за да се разложи число в канонична форма, е необходимо да се използва свойството на степените и да се представи числото като произведение на степени с различни бази
Канонично разширение на естествено число в общ вид
Канонично разширение на естествено число в общ изгледима формата:
$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$
където $p_1,p_2\dots \dots .p_k$ са прости числа, а експонентите са естествени числа.
Представянето на число като канонично разлагане на прости множества улеснява намирането на най-големия общ делител на числата и действа като следствие от доказателството или дефиницията на взаимно прости числа.
Пример 3
Намерете най-големия общ делител на числата $180$ и $240$.
Решение: Нека разложим числата на прости множества с помощта на канонично разлагане
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, след това $180=2^2\cdot 3^2\cdot 5$
$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, след това $240=2^4\cdot 3\cdot 5$
Сега нека намерим gcd на тези числа, за това избираме степени с една и съща основа и с най-малък показател, тогава
$GCD\(180;240)= 2^2\cdot 3\cdot 5=60$
Да композираме алгоритъм за намиране на НОД, като се вземе предвид каноничното разлагане на прости множители.
За да намерите най-големия общ делител на две числа с помощта на канонично разширение, трябва да:
- разложете числата на прости множители в канонична форма
- изберете степени с една и съща основа и с най-малък показател от тези, включени в разширението на тези числа
- Намерете произведението на числата, намерени в стъпка 2. Полученото число ще бъде желаният най-голям общ делител.
Пример 4
Определете дали числата $195$ и $336$ са прости, взаимно прости числа.
$195=3\cdot 5\cdot 13$
$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$
$GCD\(195;336) =3\cdot 5=15$
Виждаме, че gcd на тези числа е различен от $1$, което означава, че числата не са относително прости. Виждаме също, че всяко от числата включва фактори, в допълнение към $1$ и самото число, което означава, че числата няма да бъдат прости, а ще бъдат съставни.
Пример 5
Определете дали числата $39$ и $112$ са прости, взаимно прости числа.
Решение: Нека използваме каноничното факторизиране, за да факторизираме:
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
$GCD\(39;112)=1$
Виждаме, че gcd на тези числа е равен на $1$, което означава, че числата са относително прости. Виждаме също, че всяко от числата включва фактори, в допълнение към $1$ и самото число, което означава, че числата няма да бъдат прости, а ще бъдат съставни.
Пример 6
Определете дали числата $883$ и $997$ са прости, взаимно прости числа.
Решение: Нека използваме каноничното факторизиране, за да факторизираме:
$883=1\cdot 883$
$997=1\cdot 997$
$GCD\(883;997)=1$
Виждаме, че gcd на тези числа е равен на $1$, което означава, че числата са относително прости. Виждаме също, че всяко число включва само множители, равни на $1$ и самото число, което означава, че числата ще бъдат прости.
В тази статия ще говорим какво представляват взаимнопростите числа. В първия параграф ще формулираме определения за две, три или повече относително прости числа, ще дадем няколко примера и ще покажем в кои случаи две числа могат да се считат за прости едно спрямо друго. След това преминаваме към формулирането на основните свойства и техните доказателства. В последния абзац ще говорим за свързано понятие - прости числа по двойки.
Какво представляват взаимнопростите числа
Две цели числа или повече от тях могат да бъдат взаимно прости. Първо, нека въведем дефиниция за две числа, за които се нуждаем от понятието техен най-голям общ делител. Ако е необходимо, повторете материала, посветен на това.
Определение 1
Две такива числа a и b ще бъдат взаимно прости, чийто най-голям общ делител е равен на 1, т.е. НОД (a, b) = 1.
От това определение можем да заключим, че единственият положителен общ делител на две взаимно прости числа ще бъде равен на 1. Само две такива числа имат два общи делителя - едно и минус едно.
Кои са някои примери за взаимно прости числа? Например, такава двойка би била 5 и 11. Те имат само един общ положителен делител, равен на 1, което потвърждава тяхната взаимна простота.
Ако вземем две прости числа, тогава едно спрямо друго те ще бъдат взаимно прости във всички случаи, но такива взаимоотношения се образуват и между съставните числа. Има случаи, когато едно число в двойка относително прости числа е съставно, а второто е просто или и двете са съставни.
Това твърдение се илюстрира със следния пример: съставните числа 9 и 8 образуват относително проста двойка. Нека докажем това, като изчислим техния най-голям общ делител. За да направите това, записваме всичките им делители (препоръчваме да прочетете отново статията за намиране на делителите на число). За 8 тези числа ще бъдат ± 1, ± 2, ± 4, ± 8, а за 9 – ± 1, ± 3, ± 9. Избираме от всички делители този, който ще бъде общ и най-голям - това е единство. Следователно, ако НОД (8, − 9) = 1, тогава 8 и - 9 ще бъдат взаимно прости едно с друго.
Взаимнопростите числа не са 500 и 45, тъй като имат друг общ делител - 5 (виж статията за критериите за делимост на 5). Пет е по-голямо от едно и е положително число. Друга подобна двойка може да бъде - 201 и 3, тъй като и двете могат да бъдат разделени на 3, както е посочено от съответния знак за делимост.
На практика доста често се налага да се определи относителната простота на две цели числа. Откриването на това може да се сведе до намирането на най-големия общ делител и сравняването му с единица. Също така е удобно да използвате таблица с прости числа, за да не правите ненужни изчисления: ако едно от дадените числа е в тази таблица, то се дели само на едно и само на себе си. Нека да разгледаме решението на такъв проблем.
Пример 1
Състояние:разберете дали числата 275 и 84 са взаимно прости.
Решение
И двете числа очевидно имат повече от един делител, така че не можем веднага да ги наречем относително прости.
Изчисляваме най-големия общ делител с помощта на алгоритъма на Евклид: 275 = 84 3 + 23, 84 = 23 3 + 15, 23 = 15 1 + 8, 15 = 8 1 + 7, 8 = 7 1 + 1, 7 = 7 · 1.
Отговор:тъй като GCD (84, 275) = 1, тогава тези числа ще бъдат относително прости.
Както казахме по-рано, дефиницията на такива числа може да бъде разширена до случаите, когато имаме не две числа, а повече.
Определение 2
Целите числа a 1 , a 2 , … , a k , k > 2 ще бъдат взаимно прости, когато имат най-голям общ делител равен на 1 .
С други думи, ако имаме набор от някои числа с най-голям положителен делител, по-голям от 1, тогава всички тези числа не са взаимно обратни едно спрямо друго.
Нека вземем няколко примера. Следователно целите числа − 99, 17 и − 27 са относително прости. Всеки брой прости числа ще бъде взаимнопрост по отношение на всички членове на популацията, както в последователностите 2, 3, 11, 19, 151, 293 и 667. Но числата 12, − 9, 900 и − 72 няма да са относително прости, защото освен единица ще имат още един положителен делител, равен на 3. Същото важи и за числата 17, 85 и 187: с изключение на едно, всички те могат да бъдат разделени на 17.
Обикновено взаимната простота на числата не е очевидна на пръв поглед; този факт се нуждае от доказателство. За да разберете дали някои числа са относително прости, трябва да намерите техния най-голям общ делител и да направите заключение въз основа на сравнението му с единица.
Пример 2
Състояние: определи дали числата 331, 463 и 733 са условно прости.
Решение
Нека проверим таблицата на простите числа и определим, че и трите от тези числа са в нея. Тогава техният общ делител може да бъде само единица.
Отговор:всички тези числа ще бъдат взаимно прости едно с друго.
Пример 3
Състояние:дайте доказателство, че числата − 14, 105, − 2 107 и − 91 не са взаимно прости.
Решение
Нека започнем, като идентифицираме техния най-голям общ делител и след това се уверим, че той не е равен на 1. Тъй като отрицателните числа имат същите делители като съответните положителни, тогава gcd (− 14, 105, 2 107, − 91) = gcd (14, 105, 2 107, 91). Според правилата, които дадохме в статията за намиране на най-голям общ делител, в този случай gcd ще бъде равно на седем.
Отговор:седем е по-голямо от едно, което означава, че тези числа не са относително прости.
Основни свойства на взаимно простите числа
Такива числа имат някои практически важни свойства. Нека ги изброим по ред и да ги докажем.
Определение 3
Ако разделим целите числа a и b на числото, съответстващо на техния най-голям общ делител, получаваме относително прости числа. С други думи, a: gcd (a, b) и b: gcd (a, b) ще бъдат относително прости.
Вече сме доказали това свойство. Доказателството може да се намери в статията за свойствата на най-големия общ делител. Благодарение на него можем да определим двойки относително прости числа: просто трябва да вземем произволни две цели числа и да ги разделим на НОД. В резултат на това трябва да получим взаимно прости числа.
Определение 4
Необходимо и достатъчно условие за взаимната простота на числата a и b е съществуването на такива цели числа u 0И v 0, за което равенство a · u 0 + b · v 0 = 1ще бъде вярно.
Доказателство 1
Нека започнем с доказване на необходимостта от това условие. Да кажем, че имаме две относително прости числа, означени като a и b. Тогава по дефиницията на това понятие техният най-голям общ делител ще бъде равен на едно. От свойствата на gcd знаем, че за цели числа a и b има релация на Bezout a · u 0 + b · v 0 = gcd (a, b). От него получаваме това a · u 0 + b · v 0 = 1. След това трябва да докажем достатъчността на условието. Нека равенство a · u 0 + b · v 0 = 1ще бъде вярно в този случай, ако НОД (a, b)разделя и a , и b , тогава също ще раздели сумата a · u 0 + b · v 0, и съответно единица (това може да се твърди въз основа на свойствата на делимост). А това е възможно само ако НОД (a, b) = 1, което доказва взаимната простота на a и b.
Всъщност, ако a и b са взаимно прости, тогава според предишното свойство ще има истинско равенство a · u 0 + b · v 0 = 1. Умножаваме двете страни по c и получаваме това a · c · u 0 + b · c · v 0 = c. Можем да разделим първия член a · c · u 0 + b · c · v 0по b, защото това е възможно за a · c, и вторият член също се дели на b, защото един от нашите множители е равен на b. От това заключаваме, че цялата сума може да бъде разделена на b и тъй като тази сума е равна на c, тогава c може да бъде разделена на b.
Определение 5
Ако две цели числа a и b са взаимно прости, тогава gcd (a c, b) = gcd (c, b).
Доказателство 2
Нека докажем, че НОД (a c, b) ще раздели НОД (c, b), а след това, че НОД (c, b) ще раздели НОД (a c, b), което ще бъде доказателство за правилността на равенството НОД (a · c, b) = НОД (c, b) .
Тъй като НОД (a · c, b) дели както a · c, така и b, а НОД (a · c, b) дели b, тогава той също ще дели b · c. Това означава, че НОД (a c, b) разделя както a c, така и b c, следователно, поради свойствата на НОД, той също разделя НОД (a c, b c), което ще бъде равно на c НОД (a, b ) = c . Следователно НОД (a · c, b) разделя и b, и c, следователно също разделя НОД (c, b).
Може също да се каже, че тъй като НОД (c, b) дели и c, и b, тогава ще раздели и c, и a c. Това означава, че НОД (c, b) разделя както a · c, така и b, следователно също разделя НОД (a · c, b).
Така gcd (a c, b) и gcd (c, b) се разделят взаимно, което означава, че са равни.
Определение 6
Ако числата са от редицата a 1 , a 2 , … , a kще бъде относително просто по отношение на числата на редицата b 1, b 2, …, b m(за естествени стойности на k и m), след това техните продукти a 1 · a 2 · … · a kИ b 1 · b 2 · … · b mсъщо са относително основни, по-специално, a 1 = a 2 = … = a k = aИ b 1 = b 2 = … = b m = b, Че a kИ b m- взаимно прости.
Доказателство 3
Съгласно предходното свойство можем да запишем равенствата следния тип: НОД (a 1 · a 2 · … · a k , b m) = НОД (a 2 · … · a k , b m) = … = НОД (a k , b m) = 1 . Възможността за последния преход се осигурява от факта, че a k и b m са относително прости по условие. Това означава НОД (a 1 · a 2 · … · a k , b m) = 1 .
Нека означим a 1 · a 2 · … · a k = A и получаваме, че НОД (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = НОД (b 1 · b 2 · … · b m , A) = НОД (b 2 · … · b · b m , A) = … = НОД (b m , A) = 1 . Това ще е вярно поради последното равенство от построената по-горе верига. Така имаме равенството НОД (b 1 · b 2 · … · b m, a 1 · a 2 · … · a k) = 1, с което можем да докажем взаимната простота на произведенията a 1 · a 2 · … · a kИ b 1 · b 2 · … · b m
Това са всички свойства на взаимно простите числа, за които бихме искали да ви разкажем.
Концепцията за двойни прости числа
Знаейки какво представляват взаимнопростите числа, можем да формулираме дефиниция на прости числа по двойки.
Определение 7
Прости числа по двойкие поредица от цели числа a 1 , a 2 , ... , a k , където всяко число ще бъде относително просто по отношение на останалите.
Пример за поредица от двойки прости числа би бил 14, 9, 17 и −25. Тук всички двойки (14 и 9, 14 и 17, 14 и − 25, 9 и 17, 9 и − 25, 17 и − 25) са взаимно прости. Обърнете внимание, че условието за взаимно прости числа е задължително за прости числа по двойки, но взаимно простите числа няма да бъдат прости по двойки във всички случаи. Например в редицата 8, 16, 5 и 15 числата не са такива числа, тъй като 8 и 16 няма да са взаимно прости.
Трябва също да се спрете на концепцията за колекция от определен брой прости числа. Те винаги ще бъдат както взаимно, така и по двойки прости. Пример за това е последователността 71, 443, 857, 991. В случай на прости числа понятията за взаимно и по двойки прости ще съвпадат.
Ако забележите грешка в текста, моля, маркирайте я и натиснете Ctrl+Enter
Естествените числа a и b се наричат взаимно прости, ако техният най-голям общ делител е 1 (НОД(a; b) = 1). С други думи, ако числата a и b нямат общи множители, различни от 1, тогава те са взаимно прости.
Примери за двойки взаимно прости числа: 2 и 5, 13 и 16, 35 и 88 и т.н. Можете да посочите няколко взаимно прости числа, например числата 7, 9, 16 са взаимно прости.
Често взаимно простите числа се обозначават по следния начин: (a, b) = 1. Например, (23, 30) = 1. Тази нотация е, така да се каже, съкратена нотация за най-големия общ делител на две числа (НОД(23 , 30) = 1) и казва, че техният най-голям общ делител е 1.
Две съседни естествени числа винаги ще бъдат относително прости.Например 15 и 16 са двойка относително прости числа, точно като 16 и 17. Това е лесно за разбиране, ако вземете предвид „правилото“, че ако две естествени числа a и b се делят на едно и също естествено число, по-голямо отколкото 1 ( n > 1), то разликата им също трябва да се дели на това число n (тук имаме предвид, че a, b и разликата им се делят на цяло число, т.е. те са кратни на числото n). Но ако a и b са две съседни числа (нека a< b ), то b – a = 1; но 1 делится только на 1 (из ряда натуральных чисел). Следовательно, a и b не имеют других общих делителей, кроме 1.
От определението за взаимно прости числа и прости числа следва също, че различните прости числа винаги са взаимно прости. В крайна сметка делителите на всяко просто число са само то и 1.
Свойства на взаимно простите числа
- Най-малкото общо кратно (LCM) на двойка взаимно прости числа е равно на техния продукт.Например (3, 8) = 1 (това означава взаимно прости), следователно техният LCM е 3 × 8 = 24 (LCM (3, 8) = 24). Наистина, няма да намерите по-малко число от 24, което да е кратно както на 3, така и на 8.
- Ако числата a и b са взаимно прости и числото c е кратно както на a, така и на b, то това число също ще бъде кратно на произведението ab. Това може да се запише така: ако c a и c b, тогава c ab. Например, (3, 10) = 1, числото 60 е кратно както на 3, така и на 10 и също е кратно на 30 (3 × 10).
- Ако числата a и b са взаимно прости и числото c е кратно на b (c b ), тогава произведението ac също ще бъде кратно на b (ac b ). Например (2, 17) = 1, нека c = 34. Числото 34 е кратно на b = 17, тогава ac = 2 × 34 = 68. Проверяваме: 68 ÷ 17 = 4, т.е. то се дели на цяло, което означава, че 68 е кратно на 17.
Обикновено има повече имоти, отколкото са изброени тук. Освен това свойствата на взаимно простите числа се формулират по различни начини. Може също да е необходимо да се докажат тези свойства (в този случай не се дава доказателство).
Ключови думи: теория на числата, лекции, взаимно прости числа.
Определение.Казват, че целите числа a и b са относително прости, ако (a, b) = 1.
Две числа a и b са взаимно прости тогава и само ако има цели числа u и v такива, че au + bv = 1.
Нека X = ( x n | n = 1, 2,...) е произволна строго нарастваща последователност от естествени числа (или, ако желаете, X е произволно подмножество от естествени числа, подредени по естествен начин). Нека означим с ξ(N; X) броя на членовете на редицата X, които не превишават N .
Определение.Числото се нарича (горна асимптотична) плътност на последователността X = (x n | n = 1, 2,...) в множеството N.
Пример 1.Нека x n = 2n, където n минава през N, е последователността от всички четни числа. Очевидно е, че
Между другото, това се съгласува добре с нашите интуитивни идеи, че има половината от четните числа.
Пример 2.Нека x n =2 n, където n минава през N, е геометрична прогресия. Интуитивно е ясно, че има малко такива числа в естествения ред, защото колкото по-навътре в гората се отива в естествения ред, толкова по-рядко се срещат степените на две. Концепцията за плътност потвърждава това усещане: ξ (2 k; ( x n )) = k и е лесно да се провери, че
Плътносте вероятността за случаен избор на число от естествена серия, което принадлежи на дадена последователност.
Подобно на определението за плътност на редица, можем да дефинираме плътността на набор от двойки естествени числа. Нека има произволно множество X от подредени двойки естествени числа. Нека означим с ξ (N ; X) броя на двойките от множеството X, всяка компонента на което не превишава N. Полезно е да мислим за двойки числа от множеството X като координати на точки в координатната равнина, тогава ξ (N; X) е просто броят точки от множеството X, които попадат в квадрата ((x, y) | 0< x ≤ N ; 0 < y ≤ N }.
Определение.Номер
се нарича (горна асимптотична) плътност на набора от двойки X в набора N 2 .
Пример 3.Нека X е множеството от всички двойки естествени числа, чийто първи компонент е стриктно повече от второто. Множеството X съответства на точките от първата четвърт на координатната равнина, лежащи под ъглополовящата y = x. Плътността на такъв набор е лесна за изчисляване:
Нека X е множеството от всички подредени двойки (u, v) естествени числа, така че (u, v) = 1, т.е. множеството от всички двойки взаимно прости числа.
Теорема (Чезаро).Вероятността да се избере двойка взаимно прости числа от N е равна на 6/π 2, по-точно доказателство. Нека веднага приемем, че има вероятност p произволно избраните естествени числа a и b да са взаимно прости. Нека d ∈ N. Нека P(S) означава, както обикновено, вероятността за събитието S. Ние разсъждаваме: Р
$p$ се нарича просто число, ако има само $2$ делители: $1$ и себе си.
Делителят на естествено число $a$ е естествено число, което дели оригиналното число $a$, без да оставя остатък.
Пример 1
Намерете делителите на числото $6$.
Решение: Трябва да намерим всички числа, на които даденото число $6$ се дели без остатък. Това ще бъдат числата: $1,2,3, 6$. Така че делителя на числото $6$ ще бъдат числата $1,2,3,6.$
Отговор: $1,2,3,6$.
Това означава, че за да намерите делителите на едно число, трябва да намерите всички естествени числа, на които даденото число се дели без остатък. Лесно се вижда, че числото $1$ ще бъде делител на всяко естествено число.
Определение 2
КомпозитенТе наричат число, което има други делители освен единица и себе си.
Пример за просто число би било числото $13$, пример за съставно число би било $14.$
Бележка 1
Числото $1$ има само един делител - самото число, така че не е нито просто, нито съставно.
Взаимопрости числа
Определение 3
Взаимно прости числате са тези, чиято gcd е равна на $1$.Това означава, че за да разберете дали числата са относително прости, трябва да намерите тяхната gcd и да я сравните с $1$.
Двойно взаимно прости
Определение 4
Ако в набор от числа всеки две са взаимно прости, тогава такива числа се наричат взаимно прости по двойки. За две числа понятията „взаимопрости“ и „двойно взаимно прости“ съвпадат.
Пример 2
$8, $15 - не просто, но относително просто.
$6, 8, 9$ са взаимно прости числа, но не и взаимно прости числа по двойки.
$8, 15, 49$ са относително прости по двойки.
Както виждаме, за да определим дали числата са относително прости, е необходимо първо да ги разделим на прости множители. Нека да обърнем внимание как да направим това правилно.
Разлагане на прости множители
Например, нека разложим числото $180$ на прости множители:
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$
Нека използваме свойството на правомощията, тогава получаваме,
$180=2^2\cdot 3^2\cdot 5$
Тази нотация на разлагане на прости множители се нарича канонична, т.е. за да се разложи число в канонична форма, е необходимо да се използва свойството на степените и да се представи числото като произведение на степени с различни бази
Канонично разширение на естествено число в общ вид
Каноничното разширение на естествено число в общ вид има формата:
$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$
където $p_1,p_2\dots \dots .p_k$ са прости числа, а експонентите са естествени числа.
Представянето на число като канонично разлагане на прости множества улеснява намирането на най-големия общ делител на числата и действа като следствие от доказателството или дефиницията на взаимно прости числа.
Пример 3
Намерете най-големия общ делител на числата $180$ и $240$.
Решение: Нека разложим числата на прости множества с помощта на канонично разлагане
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, след това $180=2^2\cdot 3^2\cdot 5$
$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, след това $240=2^4\cdot 3\cdot 5$
Сега нека намерим gcd на тези числа, за това избираме степени с една и съща основа и с най-малък показател, тогава
$GCD\(180;240)= 2^2\cdot 3\cdot 5=60$
Да композираме алгоритъм за намиране на НОД, като се вземе предвид каноничното разлагане на прости множители.
За да намерите най-големия общ делител на две числа с помощта на канонично разширение, трябва да:
- разложете числата на прости множители в канонична форма
- изберете степени с една и съща основа и с най-малък показател от тези, включени в разширението на тези числа
- Намерете произведението на числата, намерени в стъпка 2. Полученото число ще бъде желаният най-голям общ делител.
Пример 4
Определете дали числата $195$ и $336$ са прости, взаимно прости числа.
$195=3\cdot 5\cdot 13$
$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$
$GCD\(195;336) =3\cdot 5=15$
Виждаме, че gcd на тези числа е различен от $1$, което означава, че числата не са относително прости. Виждаме също, че всяко от числата включва фактори, в допълнение към $1$ и самото число, което означава, че числата няма да бъдат прости, а ще бъдат съставни.
Пример 5
Определете дали числата $39$ и $112$ са прости, взаимно прости числа.
Решение: Нека използваме каноничното факторизиране, за да факторизираме:
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
$GCD\(39;112)=1$
Виждаме, че gcd на тези числа е равен на $1$, което означава, че числата са относително прости. Виждаме също, че всяко от числата включва фактори, в допълнение към $1$ и самото число, което означава, че числата няма да бъдат прости, а ще бъдат съставни.
Пример 6
Определете дали числата $883$ и $997$ са прости, взаимно прости числа.
Решение: Нека използваме каноничното факторизиране, за да факторизираме:
$883=1\cdot 883$
$997=1\cdot 997$
$GCD\(883;997)=1$
Виждаме, че gcd на тези числа е равен на $1$, което означава, че числата са относително прости. Виждаме също, че всяко число включва само множители, равни на $1$ и самото число, което означава, че числата ще бъдат прости.
