$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
Взаимопрости числасе наричат тези, чиито НОД е равен на $1$ Така че, за да разберете дали числата са взаимно прости, е необходимо да намерите техния НОД и да го сравните с $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 \ (180;240)= 2^2\cdot 3\cdot 5=60$
Да композираме алгоритъм за намиране на gcd, като се вземе предвид каноничното разлагане на прости множители.
За да намерите най-големия общ делител на две числа с помощта на каноничното разширение, трябва:
- разлагат числата на прости множители в канонична форма
- изберете градуси с една и съща основа и с най-малък показател на числата, включени в разлагането на тези числа
- Намерете произведението на числата, намерени в стъпка 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, т.е. gcd (a, b) = 1.
От тази дефиниция можем да заключим, че единственият положителен общ делител на две взаимно прости числа ще бъде равен на 1. Само две такива числа имат два общи делителя - едно и минус едно.
Кои са някои примери за относително прости числа? Например, такава двойка би била 5 и 11. Те имат само един общ положителен делител, равен на 1, което е потвърждение на тяхната взаимна простота.
Ако вземем две прости числа, тогава те ще бъдат относително прости във всички случаи едно спрямо друго, но такива взаимоотношения се образуват и между съставните числа. Има случаи, когато едно число в двойка взаимно прости числа е съставно, а второто е просто или и двете са съставни.
Това твърдение се илюстрира със следния пример: съставните числа - 9 и 8 образуват взаимнопроста двойка. Нека го докажем, като изчислим техния най-голям общ делител. За да направите това, записваме всичките им делители (препоръчваме да прочетете отново статията за намиране на делителите на число). За 8 това ще бъдат числата ± 1, ± 2, ± 4, ± 8, а за 9 - ± 1, ± 3, ± 9. Избираме от всички делители този, който ще бъде общ и най-голям - това е едно. Следователно, ако gcd (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) . Според правилата, които дадохме в статията за намиране на най-голям общ делител, в този случай НОД ще бъде равен на седем.
Отговор:седем е по-голямо от едно, което означава, че тези числа не са взаимно прости.
Основни свойства на взаимно простите числа
Такива числа имат някои практически важни свойства. Изброяваме ги по ред и ги доказваме.
Определение 3
Ако разделим целите числа a и b на числото, съответстващо на техния най-голям общ делител, получаваме относително прости числа. С други думи, a: gcd(a, b) и b: gcd(a, b) ще бъдат взаимно прости.
Ние вече доказахме това свойство. Доказателството може да се намери в статията за свойствата на най-големия общ делител. Благодарение на него можем да дефинираме двойки взаимно прости числа: просто вземете произволни две цели числа и ги разделете на gcd. В резултат на това трябва да получим взаимно прости числа.
Определение 4
Необходимо и достатъчно условие за взаимната простота на числата a и b е съществуването на такива цели числа u 0и v0, за които равенството 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ще бъде вярно, ако gcd (a, b)разделя и a , и b , тогава ще раздели и сумира a u 0 + b v 0, и съответно единица (това може да се твърди въз основа на свойствата на делимост). А това е възможно само ако gcd(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
Нека докажем, че gcd (a c , b) ще дели gcd (c , b) , а след това - че gcd (c , b) дели gcd (a c , b) , което ще докаже правилността на равенството gcd (a · c, b) = gcd (c, b) .
Тъй като gcd (a c , b) дели както a c, така и b и gcd (a c , b) дели b , той също ще дели b c . Следователно, gcd (a c, b) дели както a c, така и b c, следователно, поради свойствата на gcd, той също дели gcd (a c, b c), което ще бъде равно на c gcd (a, b ) = c. Следователно gcd(a c, b) дели и b и c, следователно gcd(c, b) също дели.
Можете също така да кажете, че тъй като gcd (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
Съгласно предходното свойство можем да запишем равенствата следния вид: gcd (a 1 a 2 ... a k , b m) = gcd (a 2 a k , b m) = ... = gcd (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 и получаваме, че gcd (b 1 b 2 … b m , a 1 a 2 … a k) = gcd (b 1 b 2 … b m , A) = GCD (b 2 · … · b · b m , A) = … = НОД (b m , A) = 1 . Това ще е вярно поради последното равенство от построената по-горе верига. Така получихме равенството gcd (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 (gcd(a ; b ) = 1). С други думи, ако числата a и b нямат общи делители, различни от 1, тогава те са взаимно прости.
Примери за двойки взаимно прости числа: 2 и 5, 13 и 16, 35 и 88 и т.н. Можете да посочите няколко взаимно прости числа, например числата 7, 9, 16 са взаимно прости.
Често взаимно простите числа се обозначават по следния начин: (a, b) = 1. Например (23, 30) = 1. Този запис е, така да се каже, съкращение за обозначаването на най-големия общ делител на две числа (НОД (23, 30) \u003d 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
Взаимопрости числасе наричат тези, чиито НОД е равен на $1$ Така че, за да разберете дали числата са взаимно прости, е необходимо да намерите техния НОД и да го сравните с $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 \ (180;240)= 2^2\cdot 3\cdot 5=60$
Да композираме алгоритъм за намиране на gcd, като се вземе предвид каноничното разлагане на прости множители.
За да намерите най-големия общ делител на две числа с помощта на каноничното разширение, трябва:
- разлагат числата на прости множители в канонична форма
- изберете градуси с една и съща основа и с най-малък показател на числата, включени в разлагането на тези числа
- Намерете произведението на числата, намерени в стъпка 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$ и самото число, което означава, че числата ще бъдат прости.
