Нека намерим най-големия общ делител на НОД (36; 24)
Стъпки на решението
Метод №1
36
- съставно число
24
- съставно число
Нека разширим числото 36
36:
2
= 18
18:
2
= 9
- дели се на простото число 2
9:
3
=
3
- дели се на простото число 3.
Нека разбием числото 24 на прости множители и ги маркирайте в зелено. Започваме да избираме делител от прости числа, започвайки с най-малкото просто число 2, докато частното се окаже просто число
24:
2
= 12
- дели се на простото число 2
12:
2
= 6
- дели се на простото число 2
6:
2
=
3
Завършваме делението, тъй като 3 е просто число
2) Маркирайте го в синьо и напишете общите множители
36
=
2
⋅
2
⋅
3
⋅
3
24
=
2
⋅
2
⋅
2
⋅
3
Общи множители (36; 24): 2, 2, 3
3) Сега, за да намерите НОД, трябва да умножите общите множители
Отговор: НОД (36; 24) = 2 ∙ 2 ∙ 3 = 12
Метод № 2
1) Намерете всички възможни делители на числата (36; 24). За да направите това, последователно ще разделим числото 36 на делители от 1 до 36, а числото 24 - на делители от 1 до 24. Ако числото се дели без остатък, тогава записваме делителя в списъка с делители.
За номер 36
36:
1
= 36;
36:
2
= 18;
36:
3
= 12;
36:
4
= 9;
36:
6
= 6;
36:
9
= 4;
36:
12
= 3;
36:
18
= 2;
36:
36
= 1;
За числото 24 Нека запишем всички случаи, когато се дели без остатък:
24:
1
= 24;
24:
2
= 12;
24:
3
= 8;
24:
4
= 6;
24:
6
= 4;
24:
8
= 3;
24:
12
= 2;
24:
24
= 1;
2) Нека да запишем всички общи делители на числата (36; 24) и да маркираме най-големия в зелено, това ще бъде най-големият общ делител на НОД на числата (36; 24)
Общи множители на числата (36; 24): 1, 2, 3, 4, 6, 12
Отговор: НОД (36; 24) = 12
Нека намерим най-малкото общо кратно на LCM (52; 49)
Стъпки на решението
Метод №1
1) Нека разложим числата на прости множители. За да направите това, нека проверим дали всяко от числата е просто (ако едно число е просто, то не може да се разложи на прости множители и самото то е разлагане)
52
- съставно число
49
- съставно число
Нека разширим числото 52 на прости множители и ги маркирайте в зелено. Започваме да избираме делител от прости числа, започвайки с най-малкото просто число 2, докато частното се окаже просто число
52:
2
= 26
- дели се на простото число 2
26:
2
=
13
- дели се на простото число 2.
Завършваме делението, тъй като 13 е просто число
Нека разширим числото 49 на прости множители и ги маркирайте в зелено. Започваме да избираме делител от прости числа, започвайки с най-малкото просто число 2, докато частното се окаже просто число
49:
7
=
7
- дели се на простото число 7.
Завършваме делението, тъй като 7 е просто число
2) Първо запишете множителите на най-голямото число, а след това на по-малкото число. Нека намерим липсващите фактори, маркирайте в синьо в разгръщането на по-малкото число факторите, които не са включени в разгръщането на по-голямото число.
52
= 2 ∙ 2 ∙ 13
49
=
7
∙
7
3) Сега, за да намерите LCM, трябва да умножите факторите на по-голямото число с липсващите фактори, които са маркирани в синьо
LCM (52; 49) = 2 ∙ 2 ∙ 13 ∙ 7 ∙ 7 = 2548
Метод № 2
1) Намерете всички възможни кратни на числата (52; 49). За целта последователно ще умножим числото 52 по числата от 1 до 49 и числото 49 по числата от 1 до 52.
Изберете всички кратни 52 в зелено:
52 ∙ 1 =
52
;
52 ∙ 2 =
104
;
52 ∙ 3 =
156
;
52 ∙ 4 =
208
;
52 ∙ 5 =
260
;
52 ∙ 6 =
312
;
52 ∙ 7 =
364
;
52 ∙ 8 =
416
;
52 ∙ 9 =
468
;
52 ∙ 10 =
520
;
52 ∙ 11 =
572
;
52 ∙ 12 =
624
;
52 ∙ 13 =
676
;
52 ∙ 14 =
728
;
52 ∙ 15 =
780
;
52 ∙ 16 =
832
;
52 ∙ 17 =
884
;
52 ∙ 18 =
936
;
52 ∙ 19 =
988
;
52 ∙ 20 =
1040
;
52 ∙ 21 =
1092
;
52 ∙ 22 =
1144
;
52 ∙ 23 =
1196
;
52 ∙ 24 =
1248
;
52 ∙ 25 =
1300
;
52 ∙ 26 =
1352
;
52 ∙ 27 =
1404
;
52 ∙ 28 =
1456
;
52 ∙ 29 =
1508
;
52 ∙ 30 =
1560
;
52 ∙ 31 =
1612
;
52 ∙ 32 =
1664
;
52 ∙ 33 =
1716
;
52 ∙ 34 =
1768
;
52 ∙ 35 =
1820
;
52 ∙ 36 =
1872
;
52 ∙ 37 =
1924
;
52 ∙ 38 =
1976
;
52 ∙ 39 =
2028
;
52 ∙ 40 =
2080
;
52 ∙ 41 =
2132
;
52 ∙ 42 =
2184
;
52 ∙ 43 =
2236
;
52 ∙ 44 =
2288
;
52 ∙ 45 =
2340
;
52 ∙ 46 =
2392
;
52 ∙ 47 =
2444
;
52 ∙ 48 =
2496
;
52 ∙ 49 =
2548
;
Изберете всички кратни 49 в зелено:
49 ∙ 1 =
49
;
49 ∙ 2 =
98
;
49 ∙ 3 =
147
;
49 ∙ 4 =
196
;
49 ∙ 5 =
245
;
49 ∙ 6 =
294
;
49 ∙ 7 =
343
;
49 ∙ 8 =
392
;
49 ∙ 9 =
441
;
49 ∙ 10 =
490
;
49 ∙ 11 =
539
;
49 ∙ 12 =
588
;
49 ∙ 13 =
637
;
49 ∙ 14 =
686
;
49 ∙ 15 =
735
;
49 ∙ 16 =
784
;
49 ∙ 17 =
833
;
49 ∙ 18 =
882
;
49 ∙ 19 =
931
;
49 ∙ 20 =
980
;
49 ∙ 21 =
1029
;
49 ∙ 22 =
1078
;
49 ∙ 23 =
1127
;
49 ∙ 24 =
1176
;
49 ∙ 25 =
1225
;
49 ∙ 26 =
1274
;
49 ∙ 27 =
1323
;
49 ∙ 28 =
1372
;
49 ∙ 29 =
1421
;
49 ∙ 30 =
1470
;
49 ∙ 31 =
1519
;
49 ∙ 32 =
1568
;
49 ∙ 33 =
1617
;
49 ∙ 34 =
1666
;
49 ∙ 35 =
1715
;
49 ∙ 36 =
1764
;
49 ∙ 37 =
1813
;
49 ∙ 38 =
1862
;
49 ∙ 39 =
1911
;
49 ∙ 40 =
1960
;
49 ∙ 41 =
2009
;
49 ∙ 42 =
2058
;
49 ∙ 43 =
2107
;
49 ∙ 44 =
2156
;
49 ∙ 45 =
2205
;
49 ∙ 46 =
2254
;
49 ∙ 47 =
2303
;
49 ∙ 48 =
2352
;
49 ∙ 49 =
2401
;
49 ∙ 50 =
2450
;
49 ∙ 51 =
2499
;
49 ∙ 52 =
2548
;
2) Нека запишем всички общи кратни на числата (52; 49) и маркирайте най-малкото в зелено, това ще бъде най-малкото общо кратно на числата (52; 49).
Общи кратни на числа (52; 49): 2548
Отговор: LCM (52; 49) = 2548
За да намерите НОД (най-голям общ делител) на две числа, трябва да:
2. Намерете (подчертайте) всички общи прости множители в получените разширения.
3. Намерете произведението на общи прости множители.
За да намерите LCM (най-малкото общо кратно) на две числа, трябва:
1. Разделете дадените числа на прости множители.
2. Разширението на едно от тях се допълва с онези фактори от разширението на другото число, които не са в разширението на първото.
3. Изчислете произведението на получените множители.
Намиране на gcd
НОД е най-големият общ делител.
За да намерите най-големия общ делител на няколко числа, трябва:
- определяне на множителите, общи за двете числа;
- намерете произведението на общите множители.
Пример за намиране на GCD:
Нека намерим gcd на числата 315 и 245.
315 = 5 * 3 * 3 * 7;
245 = 5 * 7 * 7.
2. Нека запишем коефициентите, общи за двете числа:
3. Намерете произведението на общите множители:
НОД(315, 245) = 5 * 7 = 35.
Отговор: НОД(315, 245) = 35.
Намиране на НОК
LCM е най-малкото общо кратно.
За да намерите най-малкото общо кратно на няколко числа, трябва:
- разложете числата на прости множители;
- запишете факторите, включени в разширяването на едно от числата;
- Нека добавим към тях липсващите множители от разлагането на второто число;
- намерете произведението на получените множители.
Пример за намиране на LOC:
Нека намерим LCM на числата 236 и 328:
1. Нека разложим числата на прости множители:
236 = 2 * 2 * 59;
328 = 2 * 2 * 2 * 41.
2. Нека запишем множителите, включени в разширението на едно от числата и добавим към тях липсващите множители от разширението на второто число:
2; 2; 59; 2; 41.
3. Намерете произведението на получените фактори:
LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.
Отговор: LCM(236, 328) = 19352.
Ключови думи от резюмето:Цели числа. Аритметични действия с естествени числа. Делимост на естествените числа. Прости и съставни числа. Разлагане на естествено число на прости множители. Знаци за делимост на 2, 3, 5, 9, 4, 25, 10, 11. Най-голям общ делител (НОД), както и най-малко общо кратно (НК). Деление с остатък.
Цели числа- това са числа, които се използват за броене на обекти - 1, 2, 3, 4 , ... Но броят 0 не е естествено!
Множеството от естествени числа се означава с н. Записвайте "3 ∈ N"означава, че числото три принадлежи към множеството от естествени числа, а нотацията "0 ∉ N"означава, че числото нула не принадлежи на това множество.
Десетична бройна система- позиционна числена система 10 .
Аритметични действия с естествени числа
За естествените числа са дефинирани следните действия: събиране, изваждане, умножение, деление,степенуване, извличане на корен. Първите четири действия са аритметика.
Тогава нека a, b и c са естествени числа
1. ДОПЪЛНЕНИЕ. Срок + Срок = Сума
Свойства на добавянето
1. Комуникативен a + b = b + a.
2. Съединител a + (b + c) = (a + b) + c.
3. a + 0= 0 + a = a.
2. ИЗВАДВАНЕ. Minuend – Subtrahend = Разлика
Свойства на изваждането
1. Изваждане на сбора от числото a - (b + c) = a - b - c.
2. Изваждане на число от сбора (a + b) - c = a + (b - c); (a + b) - c = (a - c) + b.
3. а - 0 = а.
4. а - а = 0.
3. УМНОЖЕНИЕ. Множител * Множител = Продукт
Свойства на умножението
1. Комуникативен a*b = b*a.
2. Съединител a*(b*c) = (a*b)*c.
3. 1 * a = a * 1 = a.
4. 0 * a = a * 0 = 0.
5. Разпределение (a + b) * c = ac + bc; (a - b) * c = ac - bc.
4. РАЗДЕЛЕНИЕ. Дивидент: делител = частно
Свойства на делението
1. a: 1 = a.
2. а: а = 1. Не можеш да делиш на нула!
3. 0: а= 0.
Процедура
1. На първо място, действията в скоби.
2. След това умножение, деление.
3. И само накрая събиране и изваждане.
Делимост на естествените числа. Прости и съставни числа.
Делител на естествено число Ае естественото число, към което Аразделено без остатък. Номер 1 е делител на всяко естествено число.
Естественото число се нарича просто, ако има само дведелител: едно и самото число. Например числата 2, 3, 11, 23 са прости числа.
Нарича се число, което има повече от два делителя композитен. Например числата 4, 8, 15, 27 са съставни числа.
Тест за делимост върши работаняколко числа: ако поне един от множителите се дели на определено число, то продуктът също се дели на това число. работа 24 15 77 разделена на 12 , тъй като множителят на това число 24 разделена на 12 .
Тест за делимост на сбор (разлика)числа: ако всеки член се дели на определено число, тогава цялата сума се дели на това число. Ако а: бИ c:b, Че (a + c) : b. И ако а: б, А ° Сне се дели на b, Че a+cне се дели на число b.
Ако а: вИ c:b, Че а: б. Въз основа на факта, че 72: 24 и 24: 12, заключаваме, че 72: 12.
Представяне на число като произведение на степени на прости числа се нарича разлагане на число на прости множители.
Основна теорема на аритметиката: всяко естествено число (освен 1 ) или е просто, или може да бъде факторизирано само по един начин.
При разлагането на числото на прости множители се използват знаците за делимост и се използва записът "колона". В този случай делителят се намира вдясно от вертикалната линия, а частното се записва под дивидента.
Например задача: разложете число на прости множители 330 . Решение:
Признаци за делимост на 2, 5, 3, 9, 10, 4, 25 и 11.
Има признаци на делимост на 6, 15, 45 и т.н., тоест в числа, чийто продукт може да бъде факторизиран 2, 3, 5, 9 И 10 .
Най-голям общ делител
Нарича се най-голямото естествено число, на което се дели всяко от две дадени естествени числа най-голям общ делителтези числа ( GCD). Например НОД (10; 25) = 5; и НОД (18; 24) = 6; НОД (7; 21) = 1.
Ако най-големият общ делител на две естествени числа е равен на 1 , тогава тези числа се наричат взаимно прости.
Алгоритъм за намиране на най-голям общ делител(КИМАНЕ)
GCD често се използва при проблеми. Например 155 тетрадки и 62 химикалки бяха разпределени поравно между учениците в един клас. Колко ученици има в този клас?
Решение: Намирането на броя на учениците в този клас се свежда до намирането на най-големия общ делител на числата 155 и 62, тъй като тетрадките и химикалките са разделени по равно. 155 = 5 31; 62 = 2 31. НОД (155; 62) = 31.
Отговор: 31 ученици в класа.
Най-малко общо кратно
Кратни на естествено число Ае естествено число, което се дели на Абез следа. Например число 8 има кратни: 8, 16, 24, 32 , ... Всяко естествено число има безкрайно много кратни.
Най-малко общо кратно(LCM) е най-малкото естествено число, кратно на тези числа.
Алгоритъм за намиране на най-малкото общо кратно ( НОК):
LCM също често се използва при проблеми. Например, двама велосипедисти са тръгнали едновременно по велосипедна писта в една и съща посока. Единият прави кръг за 1 минута, а другият за 45 секунди. След какъв минимален брой минути след началото на движението те ще се срещнат на старта?
Решение:
Броят на минутите, след които те ще се срещнат отново в началото, трябва да бъде разделен на 1 минута, както и на 45 с. За 1 мин = 60 сек. Тоест, необходимо е да се намери LCM (45; 60).
45
= 3 2 5;
60
= 2 2 3 5.
НОК (45; 60)= 2 2 3 2 5 = 4 9 5 = 180
.
Резултатът е, че колоездачите ще се срещнат на старта за 180 s = 3 min.
Отговор: 3 мин.
Деление с остатък
Ако естествено число Ане се дели на естествено число b, тогава можете да направите деление с остатък. В този случай полученото частно се извиква непълна. Равенството е справедливо:
a = b n + r,
Където А- делим, b- разделител, н- непълен коефициент, r- остатък. Например, нека дивидентът е равен 243 , разделител - 4 , Тогава 243: 4 = 60 (остатък 3). Тоест a = 243, b = 4, n = 60, r = 3, тогава 243 = 60 4 + 3 .
Числата, които се делят на 2 без остатък, се наричат дори: a = 2n, н ∈ Н.
Останалите номера се извикват странно: b = 2n + 1, н ∈ Н.
Това е обобщение на темата „Цели числа. Признаци на делимост". За да продължите, изберете следващите стъпки:
- Отидете на следващото резюме:
Тази статия е посветена на въпроса за намирането на най-голям общ делител. Първо ще обясним какво е това и ще дадем няколко примера, ще въведем определения за най-голям общ делител на 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
Определение.Нарича се най-голямото естествено число, на което числата a и b се делят без остатък най-голям общ делител (НОД)тези числа.
Нека намерим най-големия общ делител на числата 24 и 35.
Делителите на 24 са числата 1, 2, 3, 4, 6, 8, 12, 24, а делителите на 35 са числата 1, 5, 7, 35.
Виждаме, че числата 24 и 35 имат само един общ делител - числото 1. Такива числа се наричат взаимно прости.
Определение.Естествените числа се наричат взаимно прости, ако техният най-голям общ делител (НОД) е 1.
Най-голям общ делител (НОД)може да се намери, без да се изписват всички делители на дадените числа.
Разлагайки числата 48 и 36 на множители, получаваме:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
От факторите, включени в разширяването на първото от тези числа, задраскваме онези, които не са включени в разширяването на второто число (т.е. две двойки).
Останалите множители са 2 * 2 * 3. Тяхното произведение е равно на 12. Това число е най-големият общ делител на числата 48 и 36. Намерен е и най-големият общ делител на три или повече числа.
Да намеря най-голям общ делител
2) от факторите, включени в разширяването на едно от тези числа, зачеркнете онези, които не са включени в разширяването на други числа;
3) намерете произведението на останалите множители.
Ако всички дадени числа се делят на едно от тях, то това число е най-голям общ делителдадени числа.
Например най-големият общ делител на числата 15, 45, 75 и 180 е числото 15, тъй като на него се делят всички останали числа: 45, 75 и 180.
Най-малко общо кратно (LCM)
Определение. Най-малко общо кратно (LCM)естествените числа a и b е най-малкото естествено число, което е кратно на a и b. Най-малкото общо кратно (LCM) на числата 75 и 60 може да се намери, без да се записват кратните на тези числа подред. За да направите това, нека разложим 75 и 60 на прости множители: 75 = 3 * 5 * 5 и 60 = 2 * 2 * 3 * 5.
Нека запишем факторите, включени в разгръщането на първото от тези числа, и добавим към тях липсващите фактори 2 и 2 от разширяването на второто число (т.е. комбинираме факторите).
Получаваме пет фактора 2 * 2 * 3 * 5 * 5, чийто продукт е 300. Това число е най-малкото общо кратно на числата 75 и 60.
Те също намират най-малкото общо кратно на три или повече числа.
Да се намерете най-малкото общо кратноняколко естествени числа, трябва:
1) разложете ги на прости множители;
2) запишете факторите, включени в разширяването на едно от числата;
3) добавете към тях липсващите множители от разширенията на останалите числа;
4) намерете произведението на получените фактори.
Обърнете внимание, че ако едно от тези числа се дели на всички други числа, тогава това число е най-малкото общо кратно на тези числа.
Например най-малкото общо кратно на числата 12, 15, 20 и 60 е 60, защото се дели на всички тези числа.
Питагор (VI в. пр. н. е.) и неговите ученици изучават въпроса за делимостта на числата. Те наричат число, равно на сбора от всичките си делители (без самото число), перфектно число. Например числата 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) са перфектни. Следващите съвършени числа са 496, 8128, 33 550 336. Питагорейците са знаели само първите три съвършени числа. Четвъртият - 8128 - става известен през 1 век. н. д. Петият - 33 550 336 - е намерен през 15 век. До 1983 г. вече са известни 27 съвършени числа. Но учените все още не знаят дали има нечетни съвършени числа или има най-голямо съвършено число.
Интересът на древните математици към простите числа се дължи на факта, че всяко число е или просто, или може да бъде представено като произведение на прости числа, т.е. простите числа са като тухли, от които са изградени останалите естествени числа.
Вероятно сте забелязали, че простите числа в редицата от естествени числа се срещат неравномерно - в някои части на редицата са повече, в други - по-малко. Но колкото по-нататък се движим по редицата от числа, толкова по-рядко срещани са простите числа. Възниква въпросът: има ли последно (най-голямо) просто число? Древногръцкият математик Евклид (3 век пр. н. е.) в книгата си „Елементи“, която е основният учебник по математика в продължение на две хиляди години, доказва, че има безкрайно много прости числа, т.е. зад всяко просто число има още по-голямо просто число. номер.
За да намери прости числа, друг гръцки математик от същото време, Ератостен, излезе с този метод. Той записа всички числа от 1 до някакво число и след това задраска едно, което не е нито просто, нито съставно число, след това задраска през едно всички числа, идващи след 2 (числа, кратни на 2, т.е. 4, 6, 8 и т.н.). Първото останало число след 2 беше 3. След това, след две, всички числа, идващи след 3 (числа, кратни на 3, т.е. 6, 9, 12 и т.н.), бяха зачеркнати. накрая само простите числа останаха незачертани.
