Aby ste sa naučili nájsť najväčšieho spoločného deliteľa dvoch alebo viacerých čísel, musíte pochopiť, čo sú prirodzené, prvočísla a komplexné čísla.

Prirodzené číslo je akékoľvek číslo, ktoré sa používa na počítanie celých čísel.

Ak sa prirodzené číslo dá deliť iba samo sebou a jednotkou, potom sa nazýva prvočíslo.

Všetky prirodzené čísla sa dajú deliť samy sebou a jednotkou, ale jediné párne prvočíslo je 2, všetky ostatné sa dajú deliť dvomi. Preto môžu byť prvočísla iba nepárne čísla.

Prvočísel je veľa, neexistuje ich úplný zoznam. Na nájdenie GCD je vhodné použiť špeciálne tabuľky s takýmito číslami.

Väčšinu prirodzených čísel možno deliť nielen jedným, samými, ale aj inými číslami. Takže napríklad číslo 15 možno deliť 3 a 5. Všetky sa nazývajú deliče čísla 15.

Deliteľ ľubovoľného A je teda číslo, ktorým ho možno bezo zvyšku deliť. Ak má číslo viac ako dvoch prirodzených deliteľov, nazýva sa zložené.

Číslo 30 má deliteľov ako 1, 3, 5, 6, 15, 30.

Môžete vidieť, že 15 a 30 majú rovnakých deliteľov 1, 3, 5, 15. Najväčší spoločný deliteľ týchto dvoch čísel je 15.

Spoločný deliteľ čísel A a B je teda číslo, ktorým ich môžete deliť úplne. Za maximum možno považovať maximálny celkový počet, ktorým ich možno rozdeliť.

Na vyriešenie problémov sa používa nasledujúci skrátený nápis:

GCD (A; B).

Napríklad GCD (15; 30) = 30.

Na zapísanie všetkých deliteľov prirodzeného čísla sa používa zápis:

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

gcd (9; 15) = 1

V tomto príklade majú prirodzené čísla iba jedného spoločného deliteľa. Nazývajú sa coprime, respektíve jednotka je ich najväčším spoločným deliteľom.

Ako nájsť najväčšieho spoločného deliteľa čísel

Ak chcete nájsť GCD niekoľkých čísel, potrebujete:

Nájdite všetkých deliteľov každého prirodzeného čísla samostatne, to znamená rozložte ich na faktory (prvočísla);

Vyberte všetky rovnaké faktory pre dané čísla;

Vynásobte ich spolu.

Napríklad na výpočet najväčšieho spoločného deliteľa 30 a 56 by ste napísali toto:

Aby nedošlo k zámene s , je vhodné písať násobiče pomocou zvislých stĺpcov. Na ľavú stranu čiary musíte umiestniť dividendu a na pravú stranu deliteľa. Pod dividendou by ste mali uviesť výsledný kvocient.

Takže v pravom stĺpci budú všetky faktory potrebné na riešenie.

Identické delitele (nájdené faktory) môžu byť pre pohodlie podčiarknuté. Mali by sa prepísať a vynásobiť a mal by sa zapísať najväčší spoločný deliteľ.

GCD (30; 56) = 2 x 5 = 10

Je naozaj také jednoduché nájsť najväčšieho spoločného deliteľa čísel. S trochou cviku to zvládnete takmer automaticky.

Nazýva sa najväčšie prirodzené číslo, ktorým sú čísla a a b deliteľné bezo zvyšku najväčší spoločný deliteľ tieto čísla. Označte GCD(a, b).

Zvážte nájdenie GCD pomocou príkladu dvoch prirodzených čísel 18 a 60:

1 Rozložme čísla na prvočísla:
18 = 2×3×3
60 = 2×2×3×5

2 Vyškrtnite z rozšírenia prvého čísla všetky faktory, ktoré nie sú zahrnuté do rozšírenia druhého čísla, dostaneme 2×3×3 .

3 Zvyšné prvočísla po prečiarknutí vynásobíme a získame najväčšieho spoločného deliteľa čísel: gcd ( 18 , 60 )=2×3= 6 .

4 Všimnite si, že nezáleží na tom, že od prvého alebo druhého čísla vyškrtneme faktory, výsledok bude rovnaký:
18 = 2×3×3
60 = 2×2×3×5

324 , 111 a 432

Rozložme čísla na prvočísla:

324 = 2×2×3×3×3×3

111 = 3×37

432 = 2×2×2×2×3×3×3

Vymažte z prvého čísla, ktorého faktory nie sú v druhom a treťom čísle, dostaneme:

2 x 2 x 2 x 2 x 3 x 3 x 3 = 3

V dôsledku GCD ( 324 , 111 , 432 )=3

Nájdenie GCD pomocou Euklidovho algoritmu

Druhý spôsob, ako nájsť najväčšieho spoločného deliteľa pomocou Euklidov algoritmus. Euklidov algoritmus je najefektívnejší spôsob hľadania GCD, pomocou neho musíte neustále hľadať zvyšok delenia čísel a aplikovať opakujúci sa vzorec.

Opakujúci sa vzorec pre GCD, gcd(a, b)=gcd(b, a mod b), kde a mod b je zvyšok po delení a číslom b.

Euklidov algoritmus

Príklad Nájdite najväčšieho spoločného deliteľa čísel 7920 a 594

Poďme nájsť GCD( 7920 , 594 ) pomocou Euklidovho algoritmu vypočítame zvyšok delenia pomocou kalkulačky.

GCD( 7920 , 594 )

GCD( 594 , 7920 mod 594 ) = gcd( 594 , 198 )

GCD( 198 , 594 mod 198 ) = gcd( 198 , 0 )

GCD( 198 , 0 ) = 198

• 7920 mod 594 = 7920 – 13 × 594 = 198
• 594 mod 198 = 594 - 3 × 198 = 0

V dôsledku toho dostaneme GCD( 7920 , 594 ) = 198

Najmenší spoločný násobok

Aby ste našli spoločného menovateľa pri sčítaní a odčítaní zlomkov s rôznymi menovateľmi, musíte vedieť a vedieť vypočítať najmenší spoločný násobok(NOC).

Násobok čísla „a“ je číslo, ktoré je samo deliteľné číslom „a“ bezo zvyšku.

Čísla, ktoré sú násobkami 8 (to znamená, že tieto čísla budú bezo zvyšku delené 8): sú to čísla 16, 24, 32 ...

Násobky 9: 18, 27, 36, 45…

Existuje nekonečne veľa násobkov daného čísla a, na rozdiel od deliteľov toho istého čísla. Deliče - konečné číslo.

Spoločný násobok dvoch prirodzených čísel je číslo, ktoré je rovnomerne deliteľné oboma týmito číslami..

Najmenší spoločný násobok(LCM) dvoch alebo viacerých prirodzených čísel je najmenšie prirodzené číslo, ktoré je samo deliteľné každým z týchto čísel.

Ako nájsť NOC

LCM je možné nájsť a zapísať dvoma spôsobmi.

Prvý spôsob, ako nájsť LCM

Táto metóda sa zvyčajne používa pre malé čísla.

1. Násobky pre každé z čísel zapisujeme do riadku, kým nevznikne násobok, ktorý je pre obe čísla rovnaký.
2. Násobok čísla „a“ sa označuje veľkým písmenom „K“.

Príklad. Nájdite LCM 6 a 8.

Druhý spôsob, ako nájsť LCM

Táto metóda je vhodná na nájdenie LCM pre tri alebo viac čísel.

Počet rovnakých faktorov v rozšíreniach čísel môže byť rôzny.

Pri rozšírení menšieho čísla (menších čísel) podčiarknite faktory, ktoré neboli zahrnuté do rozšírenia väčšieho čísla (v našom príklade je to 2) a tieto faktory pridajte k rozšíreniu väčšieho čísla.
LCM (24, 60) = 2 2 3 5 2

Zaznamenajte výslednú prácu ako odpoveď.
Odpoveď: LCM (24, 60) = 120

Nájdenie najmenšieho spoločného násobku (LCM) môžete formalizovať aj takto. Poďme nájsť LCM (12, 16, 24) .

24 = 2 2 2 3

Ako môžete vidieť z rozšírenia čísel, všetky faktory 12 sú zahrnuté v expanzii 24 (najväčšie z čísel), takže do LCM pridáme iba jednu 2 z rozšírenia čísla 16.

LCM (12, 16, 24) = 2 2 2 3 2 = 48

Odpoveď: LCM (12, 16, 24) = 48

Špeciálne prípady nájdenia NOC

Ak je jedno z čísel rovnomerne deliteľné ostatnými, potom sa najmenší spoločný násobok týchto čísel rovná tomuto číslu.

Napríklad LCM(60; 15) = 60
Keďže prvočísla nemajú spoločných prvočíselných deliteľov, ich najmenší spoločný násobok sa rovná súčinu týchto čísel.

Na našej stránke môžete tiež použiť špeciálnu kalkulačku na vyhľadanie najmenej spoločného násobku online na kontrolu vašich výpočtov.

Ak je prirodzené číslo deliteľné iba 1 a samo sebou, potom sa nazýva prvočíslo.

Akékoľvek prirodzené číslo je vždy deliteľné 1 a samo sebou.

Číslo 2 je najmenšie prvočíslo. Toto je jediné párne prvočíslo, ostatné prvočísla sú nepárne.

Existuje veľa prvočísel a prvé z nich je číslo 2. Neexistuje však žiadne posledné prvočíslo. V časti „Na štúdium“ si môžete stiahnuť tabuľku prvočísel do 997.

Ale mnohé prirodzené čísla sú rovnomerne deliteľné inými prirodzenými číslami.

• číslo 12 je deliteľné 1, 2, 3, 4, 6, 12;
• 36 je deliteľné 1, 2, 3, 4, 6, 12, 18, 36.

Čísla, ktorými je číslo rovnomerne deliteľné (pre 12 sú to 1, 2, 3, 4, 6 a 12), sa nazývajú deliteľmi čísla.

Deliteľ prirodzeného čísla a je také prirodzené číslo, ktoré bezo zvyšku delí dané číslo „a“.

Prirodzené číslo, ktoré má viac ako dva faktory, sa nazýva zložené číslo.

Všimnite si, že čísla 12 a 36 majú spoločných deliteľov. Sú to čísla: 1, 2, 3, 4, 6, 12. Najväčší deliteľ týchto čísel je 12.

Spoločný deliteľ dvoch daných čísel „a“ a „b“ je číslo, ktorým sa obe dané čísla „a“ a „b“ bezo zvyšku delia.

Najväčší spoločný deliteľ(GCD) dvoch daných čísel „a“ a „b“ je najväčšie číslo, ktorým sú obe čísla „a“ a „b“ deliteľné bezo zvyšku.

Stručne povedané, najväčší spoločný deliteľ čísel "a" a "b" je zapísaný nasledovne:

Príklad: gcd (12; 36) = 12 .

Deliče čísel v zázname riešenia sa označujú veľkým písmenom „D“.

Čísla 7 a 9 majú iba jedného spoločného deliteľa - číslo 1. Takéto čísla sa nazývajú coprime čísla.

Coprime čísla sú prirodzené čísla, ktoré majú iba jedného spoločného deliteľa - číslo 1. Ich GCD je 1.

Ako nájsť najväčšieho spoločného deliteľa

Na nájdenie gcd dvoch alebo viacerých prirodzených čísel potrebujete:

• rozložiť deliteľa čísel na prvočísla;

Výpočty sa pohodlne píšu pomocou zvislej čiary. Vľavo od riadku najskôr zapíšte dividendu, vpravo deliteľ. Ďalej do ľavého stĺpca zapíšeme hodnoty private.

Poďme si to hneď vysvetliť na príklade. Rozložme čísla 28 a 64 na prvočísla.

Podčiarknite rovnaké prvočísla v oboch číslach.
28 = 2 2 7

64 = 2 2 2 2 2 2
Nájdeme súčin identických prvočiniteľov a zapíšeme odpoveď;
GCD (28; 64) = 22 = 4

Odpoveď: GCD (28; 64) = 4

Umiestnenie GCD môžete usporiadať dvoma spôsobmi: v stĺpci (ako bolo uvedené vyššie) alebo „v riadku“.

Prvý spôsob zápisu GCD

Nájdite GCD 48 a 36.

GCD (48; 36) = 223 = 12

Druhý spôsob zápisu GCD

Teraz napíšme riešenie vyhľadávania GCD do riadku. Nájdite GCD 10 a 15.

Na našej informačnej stránke môžete tiež nájsť najväčšieho spoločného deliteľa online pomocou pomocného programu na kontrolu vašich výpočtov.

Hľadanie najmenšieho spoločného násobku, metódy, príklady hľadania LCM.

Nižšie uvedený materiál je logickým pokračovaním teórie z článku pod názvom LCM - Least Common Multiple, definícia, príklady, vzťah medzi LCM a GCD. Tu budeme hovoriť o nájdenie najmenšieho spoločného násobku (LCM), a venovať osobitnú pozornosť riešeniu príkladov. Najprv ukážme, ako sa vypočíta LCM dvoch čísel z hľadiska GCD týchto čísel. Ďalej zvážte nájdenie najmenšieho spoločného násobku rozkladom čísel na prvočísla. Potom sa zameriame na nájdenie LCM troch alebo viacerých čísel a venujeme pozornosť aj výpočtu LCM záporných čísel.

Navigácia na stránke.

Výpočet najmenšieho spoločného násobku (LCM) prostredníctvom gcd

Jeden spôsob, ako nájsť najmenší spoločný násobok, je založený na vzťahu medzi LCM a GCD. Existujúci vzťah medzi LCM a GCD vám umožňuje vypočítať najmenší spoločný násobok dvoch kladných celých čísel prostredníctvom známeho najväčšieho spoločného deliteľa. Zodpovedajúci vzorec má tvar LCM(a, b)=a b: GCD(a, b). Zvážte príklady nájdenia LCM podľa vyššie uvedeného vzorca.

Nájdite najmenší spoločný násobok dvoch čísel 126 a 70 .

V tomto príklade a=126, b=70. Využime spojenie LCM s GCD, ktoré je vyjadrené vzorcom LCM(a, b)=a b: GCM(a, b) . To znamená, že najprv musíme nájsť najväčšieho spoločného deliteľa čísel 70 a 126, potom môžeme vypočítať LCM týchto čísel podľa napísaného vzorca.

Nájdite gcd(126, 70) pomocou Euklidovho algoritmu: 126=70 1+56, 70=56 1+14, 56=14 4, teda gcd(126, 70)=14.

Teraz nájdeme požadovaný najmenší spoločný násobok: LCM(126, 70)=126 70:GCD(126, 70)= 126 70:14=630 .

Čo je LCM(68, 34)?

Keďže 68 je rovnomerne deliteľné 34 , potom gcd(68, 34)=34 . Teraz vypočítame najmenší spoločný násobok: LCM(68, 34)=68 34:GCD(68, 34)= 68 34:34=68 .

Všimnite si, že predchádzajúci príklad vyhovuje nasledujúcemu pravidlu na nájdenie LCM pre kladné celé čísla a a b: ak je číslo a deliteľné b , potom najmenší spoločný násobok týchto čísel je a .

Nájdenie LCM rozdelením čísel na hlavné faktory

Ďalší spôsob, ako nájsť najmenší spoločný násobok, je založený na rozklade čísel na prvočísla. Ak vytvoríme súčin všetkých prvočiniteľov týchto čísel, potom z tohto súčinu vylúčime všetky spoločné prvočísla, ktoré sú prítomné v rozšíreniach týchto čísel, potom sa výsledný súčin bude rovnať najmenšiemu spoločnému násobku týchto čísel.

Vyhlásené pravidlo pre nájdenie LCM vyplýva z rovnosti LCM(a, b)=a b: GCM(a, b) . V skutočnosti sa súčin čísel a a b rovná súčinu všetkých faktorov podieľajúcich sa na expanziách čísel a a b. Na druhej strane, gcd(a, b) sa rovná súčinu všetkých prvočísel, ktoré sú súčasne prítomné v expanziách čísel a a b (čo je popísané v časti o nájdení gcd pomocou rozkladu čísel na prvočísla ).

Vezmime si príklad. Nech vieme, že 75=3 5 5 a 210=2 3 5 7 . Zostavte súčin všetkých faktorov týchto expanzií: 2 3 3 5 5 5 7 . Teraz z tohto produktu vylúčime všetky faktory, ktoré sú prítomné tak v rozšírení čísla 75, ako aj v rozšírení čísla 210 (takými faktormi sú 3 a 5), ​​potom bude produkt mať tvar 2 3 5 5 7 . Hodnota tohto súčinu sa rovná najmenšiemu spoločnému násobku 75 a 210 , teda LCM(75, 210)= 2 3 5 5 7=1 050 .

Po rozklade čísel 441 a 700 na prvočísla nájdite najmenší spoločný násobok týchto čísel.

Rozložme čísla 441 a 700 na prvočísla:

Dostaneme 441 = 3 3 7 7 a 700 = 2 2 5 5 7 .

Teraz urobme súčin všetkých faktorov podieľajúcich sa na expanziách týchto čísel: 2 2 3 3 5 5 7 7 7 . Vylúčme z tohto produktu všetky faktory, ktoré sú súčasne prítomné v oboch expanziách (existuje len jeden taký faktor - toto je číslo 7): 2 2 3 3 5 5 7 7 . Takže LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

LCM(441, 700) = 44100.

Pravidlo na nájdenie LCM pomocou rozkladu čísel na prvočísla možno formulovať trochu inak. Ak k faktorom z rozšírenia čísla a pripočítame chýbajúce faktory z rozšírenia čísla b, potom sa hodnota výsledného súčinu bude rovnať najmenšiemu spoločnému násobku čísel a a b.

Vezmime si napríklad všetky rovnaké čísla 75 a 210, ich expanzie na prvočísla sú nasledovné: 75=3 5 5 a 210=2 3 5 7 . K faktorom 3, 5 a 5 z rozšírenia čísla 75 pripočítame chýbajúce faktory 2 a 7 z rozšírenia čísla 210, dostaneme súčin 2 3 5 5 7, ktorého hodnota je LCM(75 , 210).

Nájdite najmenší spoločný násobok 84 a 648.

Najprv získame rozklad čísel 84 a 648 na prvočísla. Vyzerajú ako 84=2 2 3 7 a 648=2 2 2 3 3 3 3 . K faktorom 2 , 2 , 3 a 7 z rozšírenia čísla 84 pripočítame chýbajúce faktory 2 , 3 , 3 a 3 z rozšírenia čísla 648 , dostaneme súčin 2 2 2 3 3 3 3 7 , čo sa rovná 4 536 . Požadovaný najmenší spoločný násobok čísel 84 a 648 je teda 4 536.

Nájdenie LCM troch alebo viacerých čísel

Najmenší spoločný násobok troch alebo viacerých čísel možno nájsť postupným nájdením LCM dvoch čísel. Pripomeňme si príslušnú vetu, ktorá umožňuje nájsť LCM troch alebo viacerých čísel.

Nech sú dané kladné celé čísla a 1 , a 2 , …, a k, najmenší spoločný násobok m k týchto čísel nájdeme v sekvenčnom výpočte m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2, a 3) , ..., mk=LCM(mk-1, ak).

Zvážte aplikáciu tejto vety na príklade hľadania najmenšieho spoločného násobku štyroch čísel.

Nájdite LCM štyroch čísel 140, 9, 54 a 250.

Najprv nájdeme m2 = LCM (a 1, a 2) = LCM (140, 9) . Aby sme to urobili, pomocou euklidovského algoritmu určíme gcd(140, 9) , máme 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , teda gcd( 140, 9) = 1, teda LCM (140, 9) = 140 9: GCD (140, 9) = 140 9:1 = 1260. To znamená, m2 = 1 260.

Teraz nájdeme m 3 = LCM (m 2, a 3) = LCM (1 260, 54) . Vypočítajme to pomocou gcd(1 260, 54) , ktorý je tiež určený Euklidovým algoritmom: 1 260=54 23+18 , 54=18 3 . Potom gcd(1260,54)=18, odkiaľ LCM(1260,54)= 1260 54:gcd(1260, 54)= 1260 54:18=3780. To znamená, m 3 \u003d 3 780.

Zostáva nájsť m4 = LCM (m3, a4) = LCM (3 780, 250). Aby sme to dosiahli, nájdeme GCD(3 780, 250) pomocou Euklidovho algoritmu: 3 780=250 15+30, 250=30 8+10, 30=10 3 . Preto gcd(3 780, 250)=10, teda LCM(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500. To znamená, m 4 \u003d 94 500.

Takže najmenší spoločný násobok pôvodných štyroch čísel je 94 500.

LCM(140, 9, 54, 250) = 94500.

V mnohých prípadoch sa najmenší spoločný násobok troch alebo viacerých čísel pohodlne nájde použitím prvočíselných rozkladov daných čísel. V tomto prípade je potrebné dodržiavať nasledujúce pravidlo. Najmenší spoločný násobok viacerých čísel sa rovná súčinu, ktorý sa skladá takto: chýbajúce činitele z rozšírenia druhého čísla sa pripočítajú ku všetkým činiteľom z rozšírenia prvého čísla, chýbajúce činitele z rozšírenia prvého čísla tretie číslo sa pripočíta k získaným faktorom atď.

Uvažujme o príklade hľadania najmenšieho spoločného násobku pomocou rozkladu čísel na prvočísla.

Nájdite najmenší spoločný násobok piatich čísel 84, 6, 48, 7, 143.

Najprv získame rozklady týchto čísel na prvočiniteľa: 84=2 2 3 7 , 6=2 3, 48=2 2 2 2 3 , 7 (7 je prvočíslo, zhoduje sa s jeho rozkladom na prvočiniteľa) a 143=1113.

Aby ste našli LCM týchto čísel, k faktorom prvého čísla 84 (sú to 2 , 2 , 3 a 7) musíte pridať chýbajúce faktory z rozšírenia druhého čísla 6 . Rozšírenie čísla 6 neobsahuje chýbajúce faktory, keďže 2 aj 3 sú už prítomné v rozšírení prvého čísla 84 . K faktorom 2 , 2 , 3 a 7 pripočítame chýbajúce faktory 2 a 2 z rozšírenia tretieho čísla 48 , dostaneme množinu faktorov 2 , 2 , 2 , 2 , 3 a 7 . V ďalšom kroku nie je potrebné pridávať faktory do tejto sady, pretože 7 je v nej už obsiahnutých. Nakoniec k faktorom 2 , 2 , 2 , 2 , 3 a 7 pridáme chýbajúce faktory 11 a 13 z rozšírenia čísla 143 . Dostaneme súčin 2 2 2 2 3 7 11 13 , čo sa rovná 48 048 .

Preto LCM(84, 6, 48, 7, 143) = 48048.

LCM(84,6,48,7,143)=48048.

Nájdenie najmenšieho spoločného násobku záporných čísel

Niekedy existujú úlohy, v ktorých musíte nájsť najmenší spoločný násobok čísel, medzi ktorými je jedno, niekoľko alebo všetky čísla záporné. V týchto prípadoch musia byť všetky záporné čísla nahradené ich opačnými číslami, po ktorých by sa malo nájsť LCM kladných čísel. Toto je spôsob, ako nájsť LCM záporných čísel. Napríklad LCM(54, -34)=LCM(54, 34) a LCM(-622, -46, -54, -888) = LCM(622, 46, 54, 888).

Môžeme to urobiť, pretože množina násobkov a je rovnaká ako množina násobkov −a (a a −a sú opačné čísla). Nech je b nejaký násobok a , potom b je deliteľné a a koncept deliteľnosti tvrdí existenciu takého celého čísla q, že b=a q . Ale bude platiť aj rovnosť b=(−a)·(−q), čo na základe rovnakého konceptu deliteľnosti znamená, že b je deliteľné −a , teda b je násobkom −a . Platí aj opačné tvrdenie: ak b je nejaký násobok −a , potom b je tiež násobok a .

Nájdite najmenší spoločný násobok záporných čísel −145 a −45.

Nahraďte záporné čísla −145 a −45 ich opačnými číslami 145 a 45 . Máme LCM(-145, -45)=LCM(145, 45) . Po určení gcd(145, 45)=5 (napríklad pomocou Euklidovho algoritmu) vypočítame LCM(145, 45)=145 45:gcd(145, 45)= 145 45:5=1 305 . Najmenší spoločný násobok záporných celých čísel −145 a −45 je teda 1 305 .

www.cleverstudents.ru

Pokračujeme v štúdiu divízie. V tejto lekcii sa pozrieme na pojmy ako napr GCD a NOC.

GCD je najväčší spoločný deliteľ.

NOC je najmenší spoločný násobok.

Téma je dosť nudná, ale je potrebné ju pochopiť. Bez pochopenia tejto témy nebudete vedieť efektívne pracovať so zlomkami, ktoré sú v matematike skutočnou prekážkou.

Najväčší spoločný deliteľ

Definícia. Najväčší spoločný deliteľ čísel a a b a a b rozdelené bezo zvyšku.

Aby sme túto definíciu dobre pochopili, dosadíme namiesto premenných a a b akékoľvek dve čísla, napríklad namiesto premennej a nahraďte číslo 12 a namiesto premennej bčíslo 9. Teraz si skúsme prečítať túto definíciu:

Najväčší spoločný deliteľ čísel 12 a 9 je najväčšie číslo, ktorým 12 a 9 rozdelené bezo zvyšku.

Z definície je zrejmé, že hovoríme o spoločnom deliteľovi čísel 12 a 9, pričom tento deliteľ je najväčší zo všetkých existujúcich deliteľov. Tento najväčší spoločný deliteľ (gcd) sa musí nájsť.

Na nájdenie najväčšieho spoločného deliteľa dvoch čísel sa používajú tri metódy. Prvý spôsob je dosť časovo náročný, ale umožňuje dobre pochopiť podstatu témy a cítiť celý jej význam.

Druhá a tretia metóda sú pomerne jednoduché a umožňujú rýchlo nájsť GCD. Zvážime všetky tri spôsoby. A čo aplikovať v praxi - vyberiete si.

Prvým spôsobom je nájsť všetkých možných deliteľov dvoch čísel a vybrať z nich najväčšie. Zoberme si túto metódu v nasledujúcom príklade: Nájdite najväčšieho spoločného deliteľa čísel 12 a 9.

Najprv nájdeme všetkých možných deliteľov čísla 12. Aby sme to urobili, rozdelíme 12 na všetkých deliteľov v rozsahu od 1 do 12. Ak nám deliteľ umožňuje bezo zvyšku deliť 12, potom ho zvýrazníme modrou farbou a v zátvorkách uveďte príslušné vysvetlenie.

12: 1 = 12
(12 delené 1 bez zvyšku, takže 1 je deliteľ 12)

12: 2 = 6
(12 delené 2 bez zvyšku, takže 2 je deliteľ 12)

12: 3 = 4
(12 delené 3 bez zvyšku, takže 3 je deliteľ 12)

12: 4 = 3
(12 delené 4 bez zvyšku, takže 4 je deliteľ 12)

12:5 = 2 (zostávajú 2)
(12 nie je delené 5 bez zvyšku, takže 5 nie je deliteľom 12)

12: 6 = 2
(12 delené 6 bez zvyšku, takže 6 je deliteľ 12)

12: 7 = 1 (zostáva 5)
(12 nie je delené 7 bez zvyšku, takže 7 nie je deliteľom 12)

12: 8 = 1 (zostávajú 4)
(12 nie je bez zvyšku delené 8, takže 8 nie je deliteľom 12)

12:9 = 1 (zostávajú 3)
(12 nie je delené 9 bez zvyšku, takže 9 nie je deliteľom 12)

12: 10 = 1 (zostávajú 2)
(12 nie je delené 10 bez zvyšku, takže 10 nie je deliteľom 12)

12:11 = 1 (zostáva 1)
(12 nie je delené 11 bez zvyšku, takže 11 nie je deliteľom 12)

12: 12 = 1
(12 delené 12 bez zvyšku, takže 12 je deliteľ 12)

Teraz nájdime deliteľa čísla 9. Ak to chcete urobiť, skontrolujte všetkých deliteľov od 1 do 9

9: 1 = 9
(9 delené 1 bez zvyšku, takže 1 je deliteľom 9)

9: 2 = 4 (zostáva 1)
(9 sa nedelí 2 bez zvyšku, takže 2 nie je deliteľom 9)

9: 3 = 3
(9 delené 3 bez zvyšku, takže 3 je deliteľ 9)

9: 4 = 2 (zostáva 1)
(9 nie je delené 4 bez zvyšku, takže 4 nie je deliteľom 9)

9:5 = 1 (zostávajú 4)
(9 nie je delené 5 bez zvyšku, takže 5 nie je deliteľom 9)

9: 6 = 1 (zostávajú 3)
(9 sa nedelí 6 bezo zvyšku, takže 6 nie je deliteľom 9)

9:7 = 1 (zostávajú 2)
(9 nie je delené 7 bez zvyšku, takže 7 nie je deliteľom 9)

9:8 = 1 (zostáva 1)
(9 sa nedelí 8 bez zvyšku, takže 8 nie je deliteľom 9)

9: 9 = 1
(9 delené 9 bez zvyšku, takže 9 je deliteľom 9)

Teraz zapíšte deliteľa oboch čísel. Čísla zvýraznené modrou farbou sú deliče. Poďme si ich vypísať:

Po zapísaní deliteľov môžete okamžite určiť, ktorý z nich je najväčší a najbežnejší.

Podľa definície je najväčší spoločný deliteľ 12 a 9 číslo, ktorým sú 12 a 9 rovnomerne deliteľné. Najväčším a spoločným deliteľom čísel 12 a 9 je číslo 3

Číslo 12 aj číslo 9 sú bezo zvyšku deliteľné tromi:

Takže gcd (12 a 9) = 3

Druhý spôsob, ako nájsť GCD

Teraz zvážte druhý spôsob, ako nájsť najväčšieho spoločného deliteľa. Podstatou tejto metódy je rozložiť obe čísla na prvočísla a vynásobiť tie spoločné.

Príklad 1. Nájdite GCD čísel 24 a 18

Najprv vynásobme obe čísla prvočíselnými faktormi:

Teraz znásobíme ich spoločné faktory. Aby nedošlo k zámene, spoločné faktory môžu byť podčiarknuté.

Pozeráme sa na rozklad čísla 24. Jeho prvým činiteľom je 2. Hľadáme rovnaký činiteľ pri rozklade čísla 18 a vidíme, že tam tiež je. Podčiarkujeme obe dve:

Opäť sa pozrieme na rozklad čísla 24. Jeho druhý faktor je tiež 2. Hľadáme rovnaký faktor pri rozklade čísla 18 a vidíme, že tam už druhýkrát nie je. Potom už nič nezvýrazňujeme.

Ďalšie dve v rozšírení čísla 24 chýbajú aj v rozšírení čísla 18.

Prejdeme k poslednému faktoru rozkladu čísla 24. Toto je faktor 3. Hľadáme rovnaký faktor pri rozklade čísla 18 a vidíme, že tam tiež je. Zdôrazňujeme obe tri:

Takže spoločné faktory čísel 24 a 18 sú faktory 2 a 3. Ak chcete získať GCD, tieto faktory sa musia vynásobiť:

Takže gcd (24 a 18) = 6

Tretí spôsob, ako nájsť GCD

Teraz zvážte tretí spôsob, ako nájsť najväčšieho spoločného deliteľa. Podstata tejto metódy spočíva v tom, že čísla, v ktorých sa má hľadať najväčší spoločný deliteľ, sa rozložia na prvočísla. Potom sa z rozkladu prvého čísla vymažú faktory, ktoré nie sú zahrnuté v rozklade druhého čísla. Zostávajúce čísla v prvom rozšírení sa vynásobia a získajú GCD.

Napríklad nájdime GCD pre čísla 28 a 16 týmto spôsobom. Najprv tieto čísla rozložíme na hlavné faktory:

Máme dve rozšírenia: a

Teraz z rozšírenia prvého čísla vymažeme faktory, ktoré nie sú zahrnuté do rozšírenia druhého čísla. Rozšírenie druhého čísla nezahŕňa sedem. Odstránime ho z prvého rozšírenia:

Teraz vynásobíme zostávajúce faktory a získame GCD:

Číslo 4 je najväčším spoločným deliteľom čísel 28 a 16. Obe tieto čísla sú bezo zvyšku deliteľné 4:

Príklad 2 Nájdite GCD čísel 100 a 40

Vypočítaním čísla 100

Vypočítaním čísla 40

Máme dve rozšírenia:

Teraz z rozšírenia prvého čísla vymažeme faktory, ktoré nie sú zahrnuté do rozšírenia druhého čísla. Rozšírenie druhého čísla nezahŕňa jednu päťku (je len jedna päťka). Vymažeme ho z prvého rozkladu

Vynásobte zostávajúce čísla:

Dostali sme odpoveď 20. Číslo 20 je teda najväčší spoločný deliteľ čísel 100 a 40. Tieto dve čísla sú bezo zvyšku deliteľné 20:

GCD (100 a 40) = 20.

Príklad 3 Nájdite gcd čísel 72 a 128

Po vylúčení čísla 72

Po vylúčení čísla 128

2×2×2×2×2×2×2

Teraz z rozšírenia prvého čísla vymažeme faktory, ktoré nie sú zahrnuté do rozšírenia druhého čísla. Rozšírenie druhého čísla nezahŕňa dve trojičky (vôbec žiadne). Odstránime ich z prvého rozšírenia:

Dostali sme odpoveď 8. Číslo 8 je teda najväčší spoločný deliteľ čísel 72 a 128. Tieto dve čísla sú bezo zvyšku deliteľné 8:

GCD (72 a 128) = 8

Hľadanie GCD pre viacero čísel

Najväčší spoločný deliteľ možno nájsť pre niekoľko čísel, nielen pre dve. Na tento účel sa čísla, v ktorých sa má hľadať najväčší spoločný deliteľ, rozložia na prvočísla a potom sa nájde súčin spoločných prvočísel týchto čísel.

Napríklad nájdime GCD pre čísla 18, 24 a 36

Zohľadnenie čísla 18

Zohľadnenie čísla 24

Zohľadnenie čísla 36

Máme tri rozšírenia:

Teraz vyberieme a podčiarkneme spoločné faktory v týchto číslach. Spoločné faktory musia byť zahrnuté vo všetkých troch číslach:

Vidíme, že spoločné faktory pre čísla 18, 24 a 36 sú faktory 2 a 3. Vynásobením týchto faktorov dostaneme GCD, ktoré hľadáme:

Dostali sme odpoveď 6. Číslo 6 je teda najväčším spoločným deliteľom čísel 18, 24 a 36. Tieto tri čísla sú bezo zvyšku deliteľné šiestimi:

GCD (18, 24 a 36) = 6

Príklad 2 Nájdite gcd pre čísla 12, 24, 36 a 42

Rozložme každé číslo na faktor. Potom nájdeme súčin spoločných faktorov týchto čísel.

Zohľadnenie čísla 12

Zohľadnenie čísla 42

Máme štyri rozšírenia:

Teraz vyberieme a podčiarkneme spoločné faktory v týchto číslach. Spoločné faktory musia byť zahrnuté vo všetkých štyroch číslach:

Vidíme, že spoločné faktory pre čísla 12, 24, 36 a 42 sú faktory 2 a 3. Vynásobením týchto faktorov dostaneme GCD, ktoré hľadáme:

Dostali sme odpoveď 6. Číslo 6 je teda najväčší spoločný deliteľ čísel 12, 24, 36 a 42. Tieto čísla sú bezo zvyšku deliteľné šiestimi:

gcd(12, 24, 36 a 42) = 6

Z predchádzajúcej lekcie vieme, že ak sa nejaké číslo vydelí druhým bezo zvyšku, nazýva sa to násobok tohto čísla.

Ukazuje sa, že násobok môže byť spoločný viacerým číslam. A teraz nás bude zaujímať násobok dvoch čísel, pričom by mal byť čo najmenší.

Definícia. Najmenší spoločný násobok (LCM) čísel a a b- a a b a a číslo b.

Definícia obsahuje dve premenné a a b. Za tieto premenné dosaďte ľubovoľné dve čísla. Napríklad namiesto premennej a nahraďte číslo 9 a namiesto premennej b dosadíme číslo 12. Teraz si skúsme prečítať definíciu:

Najmenší spoločný násobok (LCM) čísel 9 a 12 - je najmenšie číslo, ktoré je násobkom 9 a 12 . Inými slovami, je to také malé číslo, ktoré je bezo zvyšku deliteľné číslom 9 a na čísle 12 .

Z definície je zrejmé, že LCM je najmenšie číslo, ktoré je bezo zvyšku deliteľné 9 a 12. Toto LCM je potrebné nájsť.

Existujú dva spôsoby, ako nájsť najmenší spoločný násobok (LCM). Prvý spôsob je, že si môžete zapísať prvé násobky dvoch čísel a potom si z týchto násobkov vybrať také číslo, ktoré bude spoločné pre čísla aj malé. Aplikujme túto metódu.

Najprv nájdime prvé násobky čísla 9. Ak chcete nájsť násobky čísla 9, musíte túto deviatku postupne vynásobiť číslami od 1 do 9. Odpovede, ktoré dostanete, budú násobky čísla 9. Takže, Začnime. Násobky budú zvýraznené červenou farbou:

Teraz nájdeme násobky pre číslo 12. Aby sme to dosiahli, vynásobíme 12 postupne všetkými číslami 1 až 12.

Zvážte dva spôsoby, ako nájsť najväčšieho spoločného deliteľa.

Hľadanie faktoringom

Prvým spôsobom je nájsť najväčšieho spoločného deliteľa rozdelením daných čísel na prvočiniteľa.

Ak chcete nájsť GCD niekoľkých čísel, stačí ich rozložiť na prvočísla a vynásobiť medzi sebou tie, ktoré sú spoločné pre všetky dané čísla.

Príklad 1 Nájdeme GCD (84, 90).

Čísla 84 a 90 rozložíme na prvočísla:

Takže sme podčiarkli všetky spoločné prvočísla, zostáva ich medzi sebou vynásobiť: 1 2 3 = 6.

Takže gcd(84, 90) = 6.

Príklad 2 Nájdeme GCD (15, 28).

15 a 28 rozložíme na hlavné faktory:

Čísla 15 a 28 sú rovnaké, pretože ich najväčší spoločný deliteľ je jedna.

gcd (15, 28) = 1.

Euklidov algoritmus

Druhá metóda (inak nazývaná Euklidova metóda) je nájsť GCD postupným delením.

Najprv sa pozrieme na túto metódu, ako je aplikovaná iba na dve dané čísla, a potom prídeme na to, ako ju aplikovať na tri alebo viac čísel.

Ak je väčšie z dvoch daných čísel deliteľné menším, potom číslo, ktoré je menšie, bude ich najväčším spoločným deliteľom.

Príklad 1 Vezmite dve čísla 27 a 9. Keďže 27 je deliteľné 9 a 9 je deliteľné 9, potom 9 je spoločným deliteľom čísel 27 a 9. Tento deliteľ je zároveň najväčší, pretože 9 nemôže byť deliteľné žiadnym číslom, väčší ako 9. Preto gcd (27, 9) = 9.

V iných prípadoch sa na nájdenie najväčšieho spoločného deliteľa dvoch čísel používa nasledujúci postup:

1. Z dvoch daných čísel sa väčšie číslo vydelí menším.
2. Potom sa menšie číslo vydelí zvyškom, ktorý vznikne delením väčšieho čísla menším.
3. Ďalej sa prvý zvyšok delí druhým zvyškom, ktorý sa získa vydelením menšieho čísla prvým zvyškom.
4. Druhý zvyšok sa delí tretím, ktorý sa získa vydelením prvého zvyšku druhým atď.
5. Delenie teda pokračuje, kým zvyšok nie je nula. Posledný deliteľ bude najväčší spoločný deliteľ.

Príklad 2 Nájdite najväčšieho spoločného deliteľa čísel 140 a 96:

1) 140 : 96 = 1 (zvyšok 44)

2) 96:44 = 2 (zvyšok 8)

3) 44: 8 = 5 (zvyšok 4)

Posledný deliteľ je 4, čo znamená gcd(140, 96) = 4.

Sekvenčné delenie možno zapísať aj do stĺpca:

Ak chcete nájsť najväčšieho spoločného deliteľa troch alebo viacerých daných čísel, použite nasledujúci postup:

1. Najprv nájdite najväčšieho spoločného deliteľa akýchkoľvek dvoch čísel z viacerých množín údajov.
2. Potom nájdeme GCD nájdeného deliteľa a nejaké tretie dané číslo.
3. Potom nájdeme GCD posledného nájdeného deliteľa a štvrtého daného čísla atď.

Príklad 3 Nájdite najväčšieho spoločného deliteľa čísel 140, 96 a 48. GCD čísel 140 a 96 sme už našli v predchádzajúcom príklade (ide o číslo 4). Zostáva nájsť najväčšieho spoločného deliteľa čísla 4 a tretieho daného čísla - 48:

48 je deliteľné 4 bezo zvyšku. Takže gcd(140, 96, 48) = 4.

Pamätajte!

Ak je prirodzené číslo deliteľné iba 1 a samo sebou, potom sa nazýva prvočíslo.

Akékoľvek prirodzené číslo je vždy deliteľné 1 a samo sebou.

Číslo 2 je najmenšie prvočíslo. Toto je jediné párne prvočíslo, ostatné prvočísla sú nepárne.

Existuje veľa prvočísel a prvé z nich je číslo 2. Neexistuje však žiadne posledné prvočíslo. V časti „Na štúdium“ si môžete stiahnuť tabuľku prvočísel do 997.

Ale mnohé prirodzené čísla sú rovnomerne deliteľné inými prirodzenými číslami.

Napríklad:

• číslo 12 je deliteľné 1, 2, 3, 4, 6, 12;
• 36 je deliteľné 1, 2, 3, 4, 6, 12, 18, 36.

Čísla, ktorými je číslo rovnomerne deliteľné (pre 12 sú to 1, 2, 3, 4, 6 a 12), sa nazývajú deliteľmi čísla.

Pamätajte!

Deliteľ prirodzeného čísla a je také prirodzené číslo, ktoré bezo zvyšku delí dané číslo „a“.

Prirodzené číslo, ktoré má viac ako dva faktory, sa nazýva zložené číslo.

Všimnite si, že čísla 12 a 36 majú spoločných deliteľov. Sú to čísla: 1, 2, 3, 4, 6, 12. Najväčší deliteľ týchto čísel je 12.

Spoločný deliteľ dvoch daných čísel „a“ a „b“ je číslo, ktorým sa obe dané čísla „a“ a „b“ bezo zvyšku delia.

Pamätajte!

Najväčší spoločný deliteľ(GCD) dvoch daných čísel "a" a "b" - to je najväčšie číslo, ktorým sa obe čísla "a" a "b" bezo zvyšku delia.

Stručne povedané, najväčší spoločný deliteľ čísel "a" a "b" je zapísaný nasledovne:

gcd (a; b) .

Príklad: gcd (12; 36) = 12 .

Deliče čísel v zázname riešenia sa označujú veľkým písmenom „D“.

D(7) = (1, 7)

D(9) = (1, 9)

gcd (7; 9) = 1

Čísla 7 a 9 majú iba jedného spoločného deliteľa - číslo 1. Takéto čísla sa nazývajú coprime čísla.

Pamätajte!

Coprime čísla sú prirodzené čísla, ktoré majú iba jedného spoločného deliteľa - číslo 1. Ich GCD je 1.

Ako nájsť najväčšieho spoločného deliteľa

Na nájdenie gcd dvoch alebo viacerých prirodzených čísel potrebujete:

1. rozložiť deliteľa čísel na prvočísla;

Výpočty sa pohodlne píšu pomocou zvislej čiary. Vľavo od riadku najskôr zapíšte dividendu, vpravo deliteľ. Ďalej do ľavého stĺpca zapíšeme hodnoty private.

Poďme si to hneď vysvetliť na príklade. Rozložme čísla 28 a 64 na prvočísla.

1. Podčiarknite rovnaké prvočísla v oboch číslach.
   28 = 2 2 7

   64 = 2 2 2 2 2 2

2. Nájdeme súčin identických prvočiniteľov a zapíšeme odpoveď;
   GCD (28; 64) = 22 = 4

   Odpoveď: GCD (28; 64) = 4

Umiestnenie GCD môžete usporiadať dvoma spôsobmi: v stĺpci (ako bolo uvedené vyššie) alebo „v riadku“.

Teraz a v nasledujúcom budeme predpokladať, že aspoň jedno z týchto čísel sa líši od nuly. Ak sa všetky zadané čísla rovnajú nule, ich spoločným deliteľom je ľubovoľné celé číslo a keďže celých čísel je nekonečne veľa, nemôžeme hovoriť o najväčšom z nich. Preto nemožno hovoriť o najväčšom spoločnom deliteľovi čísel, z ktorých každé je rovné nule.

Teraz môžeme dať nájsť najväčšieho spoločného deliteľa dve čísla.

Definícia.

Najväčší spoločný deliteľ z dvoch celých čísel je najväčšie celé číslo, ktoré delí dve dané celé čísla.

Skratka GCD sa často používa na skrátenie najväčšieho spoločného deliteľa – Greatest Common Delitel. Tiež najväčší spoločný deliteľ dvoch čísel aab sa často označuje ako gcd(a, b) .

Poďme priniesť Príklad najväčšieho spoločného deliteľa (gcd). dve celé čísla. Najväčší spoločný deliteľ 6 a -15 je 3. Poďme to podložiť. Zapíšme si všetkých deliteľov čísla šesť: ±6, ±3, ±1 a deliče čísla −15 sú čísla ±15, ±5, ±3 a ±1. Teraz môžete nájsť všetkých spoločných deliteľov čísel 6 a −15, to sú čísla −3, −1, 1 a 3. Od −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

Definícia najväčšieho spoločného deliteľa troch alebo viacerých celých čísel je podobná definícii gcd dvoch čísel.

Definícia.

Najväčší spoločný deliteľ tri alebo viac celých čísel je najväčšie celé číslo, ktoré súčasne delí všetky dané čísla.

Najväčší spoločný deliteľ n celých čísel a 1 , a 2 , …, a n označíme ako gcd(a 1 , a 2 , …, a n) . Ak sa nájde hodnota b najväčšieho spoločného deliteľa týchto čísel, potom môžeme písať GCD(ai, a2, …, a n)=b.

Ako príklad, za predpokladu, že gcd štyroch celých čísel −8 , 52 , 16 a −12 , sa rovná 4 , teda gcd(−8, 52, 16, −12)=4 . Dá sa to skontrolovať tak, že si zapíšete všetkých deliteľov daných čísel, vyberiete z nich spoločných deliteľov a určíte najväčšieho spoločného deliteľa.

Všimnite si, že najväčší spoločný deliteľ celých čísel sa môže rovnať jednému z týchto čísel. Toto tvrdenie je pravdivé, ak sú všetky uvedené čísla deliteľné jedným z nich (dôkaz je uvedený v ďalšom odseku tohto článku). Napríklad gcd(15, 60, −45)=15 . To je pravda, pretože 15 delí 15, 60 a -45 a neexistuje spoločný deliteľ 15, 60 a -45, ktorý by bol väčší ako 15.

Obzvlášť zaujímavé sú takzvané relatívne prvočísla, - také celé čísla, ktorých najväčší spoločný deliteľ sa rovná jednej.

Najväčšie vlastnosti spoločného deliteľa, Euklidov algoritmus

Najväčší spoločný deliteľ má množstvo charakteristických výsledkov, inými slovami, množstvo vlastností. Teraz uvedieme hlavné vlastnosti najväčšieho spoločného deliteľa (gcd), sformulujeme ich vo forme viet a hneď dáme dôkazy.

Sformulujeme všetky vlastnosti najväčšieho spoločného deliteľa pre kladné celé čísla, pričom budeme uvažovať iba o kladných deliteľoch týchto čísel.

Najväčší spoločný deliteľ čísel a a b sa rovná najväčšiemu spoločnému deliteľovi čísel b a a , teda gcd(a, b)=gcd(a, b) .

Táto vlastnosť GCD vyplýva priamo z definície najväčšieho spoločného deliteľa.

Ak a je deliteľné b , potom množina spoločných deliteľov a a b je rovnaká ako množina deliteľov b , konkrétne gcd(a, b)=b .

Dôkaz.

Akýkoľvek spoločný deliteľ čísel a a b je deliteľom každého z týchto čísel vrátane čísla b. Na druhej strane, keďže a je násobkom b, potom ľubovoľný deliteľ čísla b je zároveň deliteľom čísla a, pretože deliteľnosť má vlastnosť tranzitivity, preto každý deliteľ čísla b je a spoločný deliteľ čísel a a b. To dokazuje, že ak je a deliteľné b, potom sa množina deliteľov čísel a a b zhoduje s množinou deliteľov jedného čísla b. A keďže najväčší deliteľ čísla b je samotné číslo b, potom sa najväčší spoločný deliteľ čísel a a b rovná aj b , teda gcd(a, b)=b .

Najmä, ak sú čísla a a b rovnaké, potom gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. Napríklad gcd(132, 132)=132.

Preukázaná vlastnosť najväčšieho deliteľa nám umožňuje nájsť gcd dvoch čísel, keď je jedno z nich deliteľné druhým. V tomto prípade sa GCD rovná jednému z týchto čísel, ktorým je iné číslo deliteľné. Napríklad gcd(8, 24)=8, pretože 24 je násobkom ôsmich.

Ak a=b q+c , kde a , b , c a q sú celé čísla, potom množina spoločných deliteľov čísel a a b sa zhoduje s množinou spoločných deliteľov čísel b a c , konkrétne gcd( a, b) = gcd (b, c).

Zdôvodnime túto vlastnosť GCD.

Keďže platí rovnosť a=b·q+c, potom ľubovoľný spoločný deliteľ čísel a a b delí aj c (vyplýva to z vlastností deliteľnosti). Z rovnakého dôvodu každý spoločný deliteľ b a c delí a . Preto je množina spoločných deliteľov čísel a a b rovnaká ako množina spoločných deliteľov čísel b a c. Najmä najväčší z týchto spoločných deliteľov sa musí tiež zhodovať, to znamená, že nasledujúca rovnosť musí platiť gcd(a, b)=gcd(b, c) .

Teraz sformulujeme a dokážeme vetu, ktorá je Euklidov algoritmus. Euklidov algoritmus vám umožňuje nájsť GCD dvoch čísel (pozri hľadanie GCD pomocou Euklidovho algoritmu). Navyše, Euklidov algoritmus nám umožní dokázať nasledujúce vlastnosti najväčšieho spoločného deliteľa.

Pred vyslovením vety odporúčame osviežiť si pamäť vety z časti teória, ktorá hovorí, že dividenda a môže byť vyjadrená ako b q + r, kde b je deliteľ, q je nejaké celé číslo nazývané parciálny kvocient, a r je celé číslo, ktoré spĺňa podmienku, nazývané zvyšok.

Predpokladajme teda, že pre dve nenulové kladné celé čísla a a b je séria rovnosti pravdivá

končiace, keď r k+1 = 0 (čo je nevyhnutné, pretože b>r 1 >r 2 >r 3, … je rad klesajúcich celých čísel a tento rad nemôže obsahovať viac než konečný počet kladných čísel), potom r k – je najväčší spoločný deliteľ a a b , teda r k =gcd(a, b) .

Dôkaz.

Najprv dokážme, že r k je spoločný deliteľ čísel a a b , potom ukážeme, že r k nie je len deliteľ, ale najväčší spoločný deliteľ čísel a a b .

Po zapísaných rovnosti sa budeme pohybovať zdola nahor. Z poslednej rovnosti môžeme povedať, že r k−1 je deliteľné r k . Vzhľadom na túto skutočnosť, ako aj predchádzajúcu vlastnosť GCD, predposledná rovnosť r k−2 =r k−1 q k + r k nám umožňuje tvrdiť, že r k−2 je deliteľné r k , keďže r k−1 je deliteľné r k a rk je deliteľné podľa r k . Analogicky z tretej rovnosti zdola usúdime, že r k−3 je deliteľné r k . A tak ďalej. Z druhej rovnosti dostaneme, že b je deliteľné r k a z prvej rovnosti dostaneme, že a je deliteľné r k . Preto r k je spoločným deliteľom a a b.

Zostáva dokázať, že r k =gcd(a, b) . Lebo stačí ukázať, že každý spoločný deliteľ čísel a a b (označíme ho r 0 ) delí r k .

Po počiatočných rovnosti sa budeme pohybovať zhora nadol. Na základe predchádzajúcej vlastnosti z prvej rovnosti vyplýva, že r 1 je deliteľné r 0 . Potom z druhej rovnosti dostaneme, že r 2 je deliteľné r 0 . A tak ďalej. Z poslednej rovnosti dostaneme, že r k je deliteľné r 0 . Teda rk =gcd(a, b) .

Z uvažovanej vlastnosti najväčšieho spoločného deliteľa vyplýva, že množina spoločných deliteľov čísel a a b sa zhoduje s množinou najväčšieho spoločného deliteľa týchto čísel. Tento dôsledok z Euklidovho algoritmu nám umožňuje nájsť všetkých spoločných deliteľov dvoch čísel ako deliteľov gcd týchto čísel.

Nech a a b sú celé čísla, ktoré sa nerovnajú nule súčasne, potom existujú také celé čísla u 0 a v 0 , potom platí rovnosť gcd(a, b)=a u 0 +b v 0. Posledná rovnosť je lineárne znázornenie najväčšieho spoločného deliteľa čísel a a b, táto rovnosť sa nazýva Bezoutov pomer a čísla u 0 a v 0 sú Bezoutove koeficienty.

Dôkaz.

Podľa Euklidovho algoritmu môžeme zapísať nasledujúce rovnosti



Z prvej rovnosti máme r 1 =a−b q 1 a pri označení 1=s 1 a −q 1 =t 1 má táto rovnosť tvar r 1 =s 1 a+t 1 b a čísla s 1 a ti sú celé čísla. Potom z druhej rovnosti dostaneme 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. Ak označujeme −s 1 q 2 =s 2 a 1−t 1 q 2 =t 2 , poslednú rovnosť môžeme zapísať ako r 2 =s 2 a+t 2 b a s 2 a t 2 sú celé čísla (pretože súčet rozdiel a súčin celých čísel je celé číslo). Podobne z tretej rovnosti dostaneme r 3 =s 3 ·a+t 3 ·b, zo štvrtej r 4 =s 4 ·a+t 4 ·b atď. Nakoniec rk = s k ·a+tk ·b, kde s k a tk sú celé čísla. Pretože r k =gcd(a, b) a s k =u 0 a tk =v 0 , dostaneme lineárne zobrazenie gcd požadovaného tvaru: gcd(a, b)=a u 0 +b v 0 .

Ak m je akékoľvek prirodzené číslo, potom gcd(ma, mb)=m gcd(a, b).

Zdôvodnenie tejto vlastnosti najväčšieho spoločného deliteľa je nasledovné. Ak vynásobíme obe strany každej z rovnosti Euklidovho algoritmu číslom m, dostaneme, že gcd(m a, m b)=m rk a rk je gcd(a, b) . v dôsledku toho gcd(ma, mb)=m gcd(a, b).

Táto vlastnosť najväčšieho spoločného deliteľa je základom pre metódu hľadania GCD pomocou prvočíselnej faktorizácie.

Nech p je teda ľubovoľný spoločný deliteľ čísel a a b gcd(a:p, b:p)=gcd(a, b):p, najmä ak p=gcd(a, b) máme gcd(a:gcd(a, b), b:gcd(a, b))=1, to znamená, že čísla a:gcd(a, b) a b:gcd(a, b) sú dvojčlenné.

Keďže a=p (a:p) a b=p (b:p) , a vzhľadom na predchádzajúcu vlastnosť, môžeme napísať reťazec rovnosti tvaru gcd(a, b)=gcd(p (a:p), p (b:p))= p·gcd(a:p, b:p), z čoho vyplýva rovnosť, ktorá sa má dokázať.

Najväčšia vlastnosť spoločného deliteľa sa práve ukázala ako základ.

Teraz vyslovme vlastnosť GCD, ktorá redukuje problém nájdenia najväčšieho spoločného deliteľa troch alebo viacerých čísel na postupné nájdenie GCD dvoch čísel.

Najväčší spoločný deliteľ čísel a 1 , a 2 , ..., a k sa rovná číslu d k , ktoré nájdeme pri sekvenčnom výpočte GCD(a 1 , a 2)=d 2 , GCD(d 2 , a 3) = d3, GCD (d3, a4) = d4, ..., GCD (dk-1, ak) = dk.

Dôkaz je založený na dôsledku Euklidovho algoritmu. Spoloční delitelia čísel a 1 a a 2 sú rovnakí ako delitelia d 2 . Potom sa spoloční delitelia čísel a 1 , a 2 a 3 zhodujú so spoločnými deliteľmi čísel d 2 a a 3 , teda sa zhodujú s deliteľmi d 3 . Spoločné deliče čísel a 1 , a 2 , a 3 a a 4 sú rovnaké ako spoločné deliče d 3 a a 4 , teda rovnaké ako deliče d 4 . A tak ďalej. Napokon, spoločné deliče čísel a 1 , a 2 , …, a k sa zhodujú s deliteľmi d k . A keďže najväčším deliteľom čísla d k je samotné číslo d k GCD(a1, a2, …, a k)=d k.

Týmto sa uzatvára prehľad hlavných vlastností najväčšieho spoločného deliteľa.

Bibliografia.

• Vilenkin N.Ya. atď. Matematika. 6. ročník: učebnica pre vzdelávacie inštitúcie.
• Vinogradov I.M. Základy teórie čísel.
• Mikhelovič Sh.Kh. Teória čísel.
• Kulikov L.Ya. a iné Zbierka úloh z algebry a teórie čísel: Učebnica pre študentov fiz.-mat. odbornosti pedagogických ústavov.