Faktorizácia najväčšieho spoločného deliteľa na prvočiniteľa. Hľadanie nokov pomocou prvočíselnej faktorizácie

Uvažujme o dvoch hlavných metódach na nájdenie GCD dvoma hlavnými spôsobmi: pomocou Euklidovského algoritmu a zohľadnením prvočíselných faktorov. Aplikujme obe metódy na dve, tri alebo viac čísel.

Yandex.RTB R-A-339285-1

Euklidovský algoritmus na nájdenie GCD

Euklidovský algoritmus uľahčuje výpočet najväčšieho spoločného činiteľa dvoch kladných čísel. Formulácie a dôkaz Euklidovho algoritmu sme predstavili v časti „Najväčší spoločný deliteľ: determinant, príklady“.

Podstatou algoritmu je postupne vykonávať delenie so zvyškom, počas ktorého sa získa séria rovností formulára:

a = bqi + r1, 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

Rozdelenie môžeme ukončiť, keď rk + 1 = 0, kde r k = gcd (a, b).

Príklad 1

64 A 48 .

Riešenie

Zavedme nasledujúce zápisy: a = 64, b = 48.

Na základe euklidovského algoritmu vykonáme delenie 64 na 48 .

Dostaneme 1 a zvyšok 16. Ukazuje sa, že q 1 = 1, r 1 = 16.

Druhým krokom je rozdelenie 48 do 16, dostaneme 3. Teda q2 = 3, A r2 = 0.Číslo 16 je teda najväčším spoločným deliteľom pre čísla z podmienky.

odpoveď: GCD (64, 48) = 16.

Príklad 2

Čo je GCD čísel? 111 A 432 ?

Riešenie

Delíme sa 432 na 111 . Podľa euklidovského algoritmu získame reťazec rovnosti 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Najväčší spoločný deliteľ čísel je teda 111 A 432 - toto je 3.

odpoveď: GCD (111, 432) = 3.

Príklad 3

Nájdite najväčšieho spoločného deliteľa čísel 661 a 113.

Riešenie

Poďme postupne rozdeliť čísla a získať GCD (661 , 113) = 1 . To znamená, že 661 a 113 sú relatívne prvočísla. Mohli by sme to zistiť pred začatím výpočtu, ak by sme si prezreli tabuľku prvočísel.

odpoveď: GCD (661, 113) = 1.

Nájdenie GCD rozdelením čísel na prvočísla

Aby sme pomocou metódy rozkladu našli najväčšieho spoločného deliteľa dvoch čísel, je potrebné vynásobiť všetky prvočísla, ktoré získame rozkladom týchto dvoch čísel a sú im spoločné.

Príklad 4

Ak zahrnieme čísla 220 a 600 do prvočiniteľov, dostaneme dva produkty: 220 = 2 2 5 11 A 600 = 2 2 2 3 5 5. Spoločné faktory v týchto dvoch produktoch sú 2, 2 a 5. To znamená, že GCD (220, 600) = 2 2 5 = 20.

Príklad 5

Nájdite najväčšieho spoločného deliteľa čísel 72 A 96 .

Riešenie

Nájdite všetky prvočísla čísel 72 A 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Spoločné prvočísla pre dve čísla sú 2, 2, 2 a 3. To znamená, že GCD (72, 96) = 2 2 2 3 = 24.

odpoveď: GCD (72, 96) = 24.

Pravidlo na nájdenie najväčšieho spoločného deliteľa dvoch čísel je založené na vlastnostiach najväčšieho spoločného deliteľa, podľa ktorého gcd (m a 1, mb b 1) = m gcd (a 1, b 1), kde m je ľubovoľné kladné celé číslo. .

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

Bez ohľadu na počet čísel, pre ktoré potrebujeme nájsť GCD, budeme postupovať podľa rovnakého algoritmu, ktorý pozostáva z postupného hľadania GCD dvoch čísel. Tento algoritmus je založený na aplikácii nasledujúcej vety: GCD niekoľkých čísel a 1 , a 2 , ... , k rovná sa číslu nevie, ktorý sa zistí postupným výpočtom gcd (a1, a2) = d2 GCD (d2, a3) = d3, GCD (d3, a4) = d4, ..., GCD (dk-1, ak) = dk.

Príklad 6

Nájdite najväčšieho spoločného deliteľa štyroch čísel 78, 294, 570 a 36 .

Riešenie

Zavedme zápis: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Začnime nájdením gcd čísel 78 a 294: d2 = GCD (78 , 294) = 6 .

Teraz začnime hľadať d 3 = GCD (d 2, a 3) = GCD (6, 570). Podľa Euklidovho algoritmu 570 = 6 95. Znamená to, že d3 = GCD (6 , 570) = 6 .

Nájdeme d 4 = GCD (d 3, a 4) = GCD (6, 36). 36 deliteľné 6 bezo zvyšku. To nám umožňuje získať d4 = GCD (6 , 36) = 6 .

d4 = 6, teda GCD (78 , 294 , 570 , 36) = 6 .

odpoveď:

Teraz sa pozrime na iný spôsob výpočtu GCD pre tieto a ďalšie čísla. Gcd môžeme nájsť vynásobením všetkých bežných prvočíselných čísel.

Príklad 7

Vypočítajte GCD čísel 78, 294, 570 a 36 .

Riešenie

Rozložme tieto čísla na prvočiniteľa: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.

Pre všetky štyri čísla budú spoločnými prvočíslami čísla 2 a 3.

Ukazuje sa, že GCD (78, 294, 570, 36) = 2 3 = 6.

odpoveď: GCD (78, 294, 570, 36) = 6.

Nájdenie GCD záporných čísel

Ak sa musíme vysporiadať so zápornými číslami, potom môžeme použiť moduly týchto čísel na nájdenie najväčšieho spoločného deliteľa. Môžeme to urobiť, keď poznáme vlastnosť čísel s opačnými znamienkami: čísla n A -n majú rovnakých deliteľov.

Príklad 8

Nájdite gcd záporných celých čísel − 231 A − 140 .

Riešenie

Na vykonanie výpočtov berieme moduly čísel uvedených v podmienke. Pôjde o čísla 231 a 140. Stručne si to zapíšme: GCD (− 231 , − 140) = GCD (231, 140). Teraz použijeme Euklidovský algoritmus na nájdenie prvočiniteľov dvoch čísel: 231 = 140 · 1 + 91 ; 140 = 91 1 + 49; 91 = 49. 1 + 42; 49 = 42 1 + 7 a 42 = 7 6. Dostaneme, že GCD (231, 140) = 7 .

A od GCD (− 231 , − 140) = GCD (231 , 140) , potom gcd čísel − 231 A − 140 rovná sa 7 .

odpoveď: GCD (− 231, − 140) = 7.

Príklad 9

Určte gcd troch čísel − 585, 81 a − 189 .

Riešenie

Nahraďte záporné čísla vo vyššie uvedenom zozname ich absolútnymi hodnotami, dostaneme GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Potom všetky tieto čísla zahrnieme do hlavných faktorov: 585 = 3 3 5 13, 81 = 3 3 3 3 a 189 = 3 3 3 7. Spoločné pre tri čísla sú prvočísla 3 a 3. Ukazuje sa, že GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.

odpoveď: GCD (− 585, 81, − 189) = 9.

Ak si všimnete chybu v texte, zvýraznite ju a stlačte Ctrl+Enter

Číslo tiketu 45. Najmenší spoločný násobok čísel. Jeho vlastnosti a spôsoby zisťovania. Príklady.

Výpočet najmenšieho spoločného násobku (LCM) pomocou GCD (najmenší spoločný deliteľ)

Jeden spôsob, ako nájsť najmenší spoločný násobok, je založený na vzťahu medzi LCM a GCD. Existujúce spojenie medzi LCM a GCD ná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 je LCM(a, b)=a b:GCD(a, b) . Pozrime sa na príklady nájdenia LCM pomocou daného vzorca.

Príklad.

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

Riešenie.

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

nájdeme GCD(126; 70) pomocou euklidovského 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: GCD(126, 70)=126·70:GCD(126, 70)=126·70:14=630.

odpoveď:

LCM(126,70)=630.

Príklad.

Čo sa rovná NOC(68; 34)?

Riešenie.

Pretože 68 deliteľné podľa 34 , To gcd(68,34)=34. Teraz vypočítame najmenší spoločný násobok: GCD(68; 34)=68 34:GCD(68; 34)=68 34:34=68.

odpoveď:

LCM(68,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 číslo a deleno b, potom je najmenší spoločný násobok týchto čísel a.

Nájdenie LCM rozdelením čísel na prvočísla

Ďalší spôsob, ako nájsť najmenší spoločný násobok, je založený na rozklade čísel na prvočísla. Ak poskladáte súčin zo všetkých prvočísel daných čísel a potom z tohto súčinu vylúčite všetky spoločné prvočísla prítomné v rozkladoch daných čísel, výsledný súčin sa bude rovnať najmenšiemu spoločnému násobku daných čísel .

Uvedené pravidlo pre nájdenie LCM vyplýva z rovnosti LCM(a, b)=a b:GCD(a, b). Skutočne, súčin čísel a A b rovná súčinu všetkých faktorov podieľajúcich sa na rozširovaní čísel a A b. Vo svojom poradí GCD(a, b) rovná súčinu všetkých prvočísel súčasne prítomných v expanziách čísel a A b(o čom sa píše v časti o hľadaní gcd pomocou rozkladu čísel na prvočísla).

Uveďme si príklad. Dajte nám to vedieť 75 = 3,5,5 A 210 = 2,3,5,7. Zostavme produkt zo všetkých faktorov týchto rozšírení: 2·3·3·5·5·5·7. Teraz z tohto produktu vylúčime všetky faktory prítomné pri rozširovaní čísla 75 a pri rozširovaní čísel 210 (takýmito násobiteľmi sú 3 A 5 ), potom produkt získa formu 2·3·5·5·7. Hodnota tohto súčinu sa rovná najmenšiemu spoločnému násobku čísel 75 A 210 , teda NOC(75; 210)= 2·3·5·5·7=1 050.

Príklad.

Rozoberanie čísel 441 A 700 pre prvočísla nájdite najmenší spoločný násobok týchto čísel.

Riešenie.

Poďme si čísla rozobrať 441 A 700 do hlavných faktorov:

Dostaneme 441 = 3,3,7,7 A 700 = 2 · 2 · 5 · 5 · 7.

Teraz vytvorte súčin všetkých faktorov, ktoré sa podieľajú na rozširovaní 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 rozšíreniach (existuje iba jeden taký faktor - toto číslo 7 ): 2·2·3·3·5·5·7·7. teda LCM(441; 700)=2·2·3·3·5·5·7·7=44 100.

odpoveď:

NOC(441, 700)= 44 100.

Pravidlo na nájdenie LCM pomocou rozkladu čísel na prvočísla možno formulovať trochu inak. Ak k faktorom z rozšírenia čísla a pridať 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 .

Zoberme si napríklad všetky rovnaké čísla 75 A 210 , ich rozklad na prvočiniteľ je nasledujúci: 75 = 3,5,5 A 210 = 2,3,5,7. K faktorom 3 , 5 A 5 z rozšírenia čísla 75 2 A 7 z rozšírenia čísla 210 , dostaneme produkt 2·3·5·5·7, ktorej hodnota je NOC(75; 210).

Príklad.

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

Riešenie.

Najprv získame rozklady čísel 84 A 648 do hlavných faktorov. Vyzerajú ako 84 = 2,2,3,7 A 648 = 2 · 2 · 2 · 3 · 3 · 3 · 3. K multiplikátorom 2 , 2 , 3 A 7 z rozšírenia čísla 84 doplniť chýbajúce násobiče 2 , 3 , 3 A 3 z rozšírenia čísla 648 , dostaneme produkt 2·2·2·3·3·3·3·7, čo sa rovná 4 536 . Teda požadovaný najmenší spoločný násobok čísel 84 A 648 rovná sa 4 536 .

odpoveď:

LCM(84,648)=4,536.

Reprezentácia čísla ako súčinu prvočísel sa nazýva rozpočítaním tohto čísla do prvočiniteľov.

Napríklad písanie 110 = 2 5 11 znamená, že číslo 110 sa rozdelí na prvočísla 2, 5 a 11.

Vo všeobecnosti možno ľubovoľné zložené číslo rozložiť na prvočísla a akoukoľvek metódou sa dosiahne rovnaký rozklad, ak neberiete do úvahy poradie faktorov. Preto reprezentácie čísla 110 vo forme súčinu 2 · 5 · 11 alebo súčinu 5 · 2 · 11 sú v podstate rovnakým rozkladom čísla 110 na prvočísla.

Pri rozklade čísel na prvočísla, pomocou znakov delenia 2, 3, 5 atď., si pamätajme spôsob zápisu rozkladu čísla na prvočiniteľa. Rozložme si napríklad na prvočiniteľa číslo 720. Číslo 720 je deliteľné 2. To znamená, že 2 je jedným z prvočiniteľov pri rozklade čísla 720. 720 vydelíme 2. Číslo 2 sa píše napravo od znamienka rovnosti a podiel 360 je napísaný pod číslom 720. Číslo Delíme 360 ​​2, dostaneme 180. Delíme 180 2, dostaneme 90, 90 delíme 2, dostaneme 45, delíme 45 3, dostaneme 15, 15 delíme 3, dostaneme 5. Číslo 5 je prvočíslo, keď ho vydelíme 5 dostaneme 1. Faktorizácia je dokončená.

720 = 2 2 2 2 3 3 5

Súčin identických faktorov sa zvyčajne nahrádza mocninou: 720 = 5. Toto znázornenie čísla 720 sa nazýva kanonický pohľad toto číslo.

Rozloženie čísla na prvočísla sa používa na nájdenie jeho najväčšieho spoločného deliteľa a najmenšieho spoločného násobku.

Nájdime napríklad najväčšieho spoločného deliteľa a najmenšieho spoločného násobku čísel 3600 a 288.

Predstavme si každé z týchto čísel v kanonickom tvare.

3600 = 2 · 2 · 2 · 2 · 3 · 3 · 5 · 5 = · · ; 288 = 2 2 2 2 2 3 3 =

Pri rozklade na prvočiniteľa najväčšieho spoločného deliteľa čísel 3600 a 288 musia byť zahrnuté všetky násobiť spoločné prvočísla, ktoré sú obsiahnuté v rozšíreniach týchto čísel a každé z nich treba vziať z najnižšia sadzba s ktorým vstupuje do oboch expanzií. Preto rozšírenie najväčšieho spoločného deliteľa čísel 3600 a 288 bude zahŕňať faktory a . Takže D (3600? 288) = · = 144.

Prvočíselný faktorizácia najmenšieho spoločného násobku 3600 a 288 musí zahŕňať všetky prvočísla obsiahnuté v aspoň v jednom z rozšírení čísel 3600 a 288 a každé z nich treba vziať s najvyššou sadzbou, zahrnuté v oboch rozšíreniach týchto čísel. Preto rozšírenie najmenšieho spoločného násobku 3600 a 288 bude zahŕňať faktory , , 5. To znamená

K (3600, 288) = · · 5 = 7200.

Vo všeobecnosti, ak chcete nájsť najväčšieho spoločného deliteľa daných čísel:

2) Vytvoríme súčin prvočiniteľov spoločných pre všetky dané čísla a každé z nich vezmeme s najmenším exponentom, s ktorým je zahrnuté vo všetkých rozšíreniach týchto čísel;

3) Nájdite hodnotu tohto súčinu - bude to najväčší spoločný deliteľ týchto čísel.

Ak chcete nájsť najmenší spoločný násobok daných čísel:

1) Každé dané číslo reprezentujeme v kanonickom tvare;

2) Zo všetkých prvočísel nájdených v rozšíreniach týchto čísel vytvoríme súčin a každý z nich vezmeme s najvyšším exponentom, s ktorým je zahrnutý vo všetkých rozšíreniach daných čísel;

3) Nájdite hodnotu tohto súčinu – bude to najmenší spoločný násobok týchto čísel.

Pozrime sa na dva spôsoby, ako nájsť najväčšieho spoločného deliteľa.

Zisťovanie faktorizáciou

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é všetkým daným číslam.

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

Čísla 84 a 90 započítame do prvočísel:

Takže sme zdôraznili všetky spoločné prvočísla, zostáva ich len vynásobiť: 1 · 2 · 3 = 6.

GCD (84, 90) = 6.

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

15 a 28 zohľadňujeme ako hlavné faktory:

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

GCD (15, 28) = 1.

Euklidov algoritmus

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

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

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

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

V ostatných prípadoch, ak chcete nájsť najväčšieho spoločného deliteľa dvoch čísel, použite nasledujúci postup:

1. Z dvoch daných čísel sa väčšie číslo vydelí menším číslom.
2. Potom sa menšie číslo vydelí zvyškom získaným delením väčšieho čísla menším číslom.
3. Potom sa prvý zvyšok vydelí 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 sa zvyšok nerovná nule. 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 - to znamená, že gcd (140, 96) = 4.

Postupné delenie možno zapísať aj do stĺpca:

Na nájdenie najväčšieho spoločného deliteľa troch alebo viacerých daných čísel použijeme nasledujúci postup:

1. Najprv nájdeme najväčšieho spoločného deliteľa akýchkoľvek dvoch čísel z niekoľkých ú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 (toto je čí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.