Zaujímavé spôsoby, ako nájsť uzly a uzly. Nod a nok čísel - najväčší spoločný deliteľ a najmenší spoločný násobok viacerých čísel

Veľa deliteľov

Zamyslite sa nad nasledujúcim problémom: nájdite deliteľa čísla 140. Je zrejmé, že číslo 140 nemá jedného, ale niekoľko deliteľov. V takýchto prípadoch sa hovorí, že úloha má kopa riešenia. Poďme ich všetky nájsť. Najprv toto číslo rozložíme na hlavné faktory:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Teraz môžeme ľahko vypísať všetkých deliteľov. Začnime jednoduchými deliteľmi, teda tými, ktoré sú prítomné vo vyššie uvedenej expanzii:

Potom vypíšeme tie, ktoré získame párovým násobením prvočíselných deliteľov:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

Potom - tie, ktoré obsahujú tri jednoduché deliče:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

Na záver nezabudnime na jednotku a samotné rozložiteľné číslo:

Všetky nami nájdené deliče tvoria kopa deliče čísla 140, ktoré sa píše pomocou zložených zátvoriek:

Množina deliteľov čísla 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Pre uľahčenie vnímania sme tu zapísali deliteľa ( nastaviť prvky) vo vzostupnom poradí, ale vo všeobecnosti to nie je potrebné. Okrem toho uvádzame skratku. Namiesto "Množina deliteľov čísla 140" napíšeme "D (140)". Touto cestou,

Podobne je možné nájsť množinu deliteľov pre akékoľvek iné prirodzené číslo. Napríklad z expanzie

105 = 3 ∙ 5 ∙ 7

dostaneme:

D(105) = (1, 3, 5, 7, 15, 21, 35, 105).

Od množiny všetkých deliteľov je potrebné odlíšiť množinu prvočíselných deliteľov, ktoré sú pre čísla 140 a 105 rovnaké:

PD(140) = (2, 5, 7).

PD(105) = (3, 5, 7).

Treba zdôrazniť, že pri rozklade čísla 140 na prvočiniteľa je dvojka prítomná dvakrát, kým v množine PD(140) len jedna. Množina PD(140) sú v podstate všetky odpovede na problém: „Nájdite prvočíslo číslo 140“. Je jasné, že rovnaká odpoveď by sa nemala opakovať viackrát.

Zníženie frakcií. Najväčší spoločný deliteľ

Zvážte zlomok

Vieme, že tento zlomok možno zmenšiť o číslo, ktoré je deliteľom čitateľa (105) aj deliteľom menovateľa (140). Pozrime sa na množiny D(105) a D(140) a zapíšme si ich spoločné prvky.

D(105) = (1, 3, 5, 7, 15, 21, 35, 105);

D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).

Spoločné prvky množín D(105) a D(140) =

Posledná rovnosť môže byť napísaná kratšie, a to:

D(105) ∩ D(140) = (1, 5, 7, 35).

Špeciálna ikona "∩" ("taška s otvorom dole") len naznačuje, že z dvoch sád napísaných na jej opačných stranách by sa mali vybrať iba spoločné prvky. Záznam "D (105) ∩ D (140)" znie " križovatka sady Te od 105 a Te od 140.

[Všimnite si, že s množinami môžete vykonávať rôzne binárne operácie, takmer ako s číslami. Ďalšou bežnou binárnou operáciou je združenie, ktorá je označená ikonou "∪" ("taška s otvorom hore"). Spojenie dvoch množín zahŕňa všetky prvky oboch množín:

PD(105) = (3, 5, 7);

PD(140) = (2, 5, 7);

PD(105) ∪ PD(140) = (2, 3, 5, 7). ]

Takže sme zistili, že zlomok

možno zmenšiť na ktorékoľvek z čísel patriacich k súprave

D(105) ∩ D(140) = (1, 5, 7, 35)

a nemožno ho zmenšiť žiadnym iným prirodzeným číslom. Tu sú všetky možné spôsoby zníženia (okrem nezaujímavého zníženia o jeden):

Je zrejmé, že najpraktickejšie je zlomok zmenšiť o číslo, ak je to možné, väčšie. V tomto prípade ide o číslo 35, o ktorom sa hovorí najväčší spoločný deliteľ (GCD) čísla 105 a 140. Toto sa píše ako

gcd(105, 140) = 35.

V praxi však platí, že ak dostaneme dve čísla a potrebujeme nájsť ich najväčšieho spoločného deliteľa, nemusíme zostavovať vôbec žiadne množiny. Stačí jednoducho rozdeliť obe čísla na prvočísla a podčiarknuť tie z týchto faktorov, ktoré sú spoločné pre obe faktorizácie, napríklad:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Vynásobením podčiarknutých čísel (v ktoromkoľvek z rozšírení) dostaneme:

gcd(105, 140) = 5 ∙ 7 = 35.

Samozrejme, je možné, že podčiarknuté faktory sú viac ako dva:

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

Odtiaľto je jasné, že

gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.

Osobitnú zmienku si zaslúži situácia, keď neexistujú žiadne spoločné faktory a nie je čo zdôrazňovať, napríklad:

42 = 2 ∙ 3 ∙ 7;

V tomto prípade,

gcd(42, 55) = 1.

Vyvolajú sa dve prirodzené čísla, pre ktoré sa gcd rovná jednej nesúdeliteľné. Ak z takýchto čísel urobíte zlomok, napr.

potom taký zlomok je neredukovateľné.

Vo všeobecnosti možno pravidlo pre redukciu zlomkov napísať takto:

		a/ gcd( a, b)
		b/ gcd( a, b)

Tu sa predpokladá, že a a b sú prirodzené čísla a všetky zlomky sú kladné. Ak teraz obom stranám tejto rovnosti priradíme znamienko mínus, dostaneme zodpovedajúce pravidlo pre záporné zlomky.

Sčítanie a odčítanie zlomkov. Najmenší spoločný násobok

Predpokladajme, že chcete vypočítať súčet dvoch zlomkov:

Už vieme, ako sa menovatelia rozkladajú na hlavné faktory:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Z tohto rozkladu hneď vyplýva, že na to, aby sa zlomky dostali na spoločného menovateľa, stačí vynásobiť čitateľa a menovateľa prvého zlomku číslom 2 ∙ 2 (súčin neprízvučných prvočiniteľov druhého menovateľa) a čitateľa a menovateľa druhého zlomku o 3 („súčin“ nepodčiarknuté prvočísla prvého menovateľa). V dôsledku toho sa menovatelia oboch zlomkov budú rovnať číslu, ktoré možno znázorniť takto:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Je ľahké vidieť, že obidva pôvodné menovatele (105 aj 140) sú deliteľmi čísla 420 a číslo 420 je zasa násobkom oboch menovateľov – a nie iba násobkom, najmenší spoločný násobok (NOC) čísla 105 a 140. Toto je napísané takto:

LCM(105,140) = 420.

Pri bližšom pohľade na rozšírenie čísel 105 a 140 to vidíme

105 ∙ 140 = LCM(105, 140) ∙ GCD(105, 140).

Podobne pre ľubovoľné prirodzené čísla b a d:

b ∙ d= LCM( b, d) ∙ GCD( b, d).

Teraz dokončíme súčet našich zlomkov:


3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5

Poznámka. Ak chcete vyriešiť niektoré problémy, musíte vedieť, čo je druhá mocnina čísla. Číselný štvorec a zavolal na číslo a vynásobený sám sebou, tzn a∙a. (Ako vidíte, rovná sa ploche štvorca so stranou a).

Najväčší spoločný deliteľ a najmenší spoločný násobok sú kľúčové aritmetické pojmy, ktoré vám umožňujú jednoducho pracovať s obyčajnými zlomkami. LCM a sa najčastejšie používajú na nájdenie spoločného menovateľa viacerých zlomkov.

Základné pojmy

Deliteľ celého čísla X je ďalšie celé číslo Y, ktorým je X deliteľné bezo zvyšku. Napríklad deliteľ čísla 4 je 2 a 36 je 4, 6, 9. Násobkom celého čísla X je číslo Y, ktoré je deliteľné X bezo zvyšku. Napríklad 3 je násobok 15 a 6 je násobok 12.

Pre každú dvojicu čísel môžeme nájsť ich spoločných deliteľov a násobkov. Napríklad pre 6 a 9 je spoločný násobok 18 a spoločný deliteľ je 3. Je zrejmé, že páry môžu mať niekoľko deliteľov a násobkov, takže pri výpočtoch sa používa najväčší deliteľ GCD a najmenší násobok LCM. .

Najmenší deliteľ nedáva zmysel, pretože pre každé číslo je vždy jedna. Najväčší násobok je tiež nezmyselný, pretože postupnosť násobkov má tendenciu k nekonečnu.

Nájdenie GCD

Existuje mnoho metód na nájdenie najväčšieho spoločného deliteľa, z ktorých najznámejšie sú:

postupné vyčíslenie deliteľov, výber spoločných pre pár a hľadanie najväčšieho z nich;
rozklad čísel na nedeliteľné faktory;
Euklidov algoritmus;
binárny algoritmus.

Dnes sú vo vzdelávacích inštitúciách najobľúbenejšie metódy rozkladu na hlavné faktory a euklidovský algoritmus. Ten sa zase používa pri riešení diofantických rovníc: hľadanie GCD je potrebné na kontrolu rovnice, či je možné ju vyriešiť v celých číslach.

Nájdenie NOC

Najmenší spoločný násobok je tiež presne určený iteratívnym sčítaním alebo rozkladom na nedeliteľné faktory. Okrem toho je ľahké nájsť LCM, ak už bol určený najväčší deliteľ. Pre čísla X a Y sú LCM a GCD spojené nasledujúcim vzťahom:

LCM(X,Y) = X x Y/GCM(X,Y).

Napríklad, ak gcd(15,18) = 3, potom LCM(15,18) = 15 × 18 / 3 = 90. Najzrejmejším použitím LCM je nájsť spoločného menovateľa, ktorým je najmenší spoločný násobok dané zlomky.

Coprime čísla

Ak dvojica čísel nemá spoločných deliteľov, potom sa takáto dvojica nazýva koprimá. GCM pre takéto páry sa vždy rovná jednej a na základe spojenia deliteľov a násobkov sa GCM pre coprime rovná ich súčinu. Napríklad čísla 25 a 28 sú koprimé, pretože nemajú spoločných deliteľov, a LCM(25, 28) = 700, čo zodpovedá ich súčinu. Akékoľvek dve nedeliteľné čísla budú vždy rovnaké.

Spoločný deliteľ a viacnásobná kalkulačka

Pomocou našej kalkulačky môžete vypočítať GCD a LCM pre ľubovoľný počet čísel, z ktorých si môžete vybrať. Úlohy na výpočet spoločných deliteľov a násobkov sa nachádzajú v aritmetike ročníkov 5 a 6, avšak GCD a LCM sú kľúčové pojmy matematiky a používajú sa v teórii čísel, planimetrii a komunikačnej algebre.

Príklady zo života

Spoločný menovateľ zlomkov

Najmenší spoločný násobok sa používa pri hľadaní spoločného menovateľa viacerých zlomkov. Predpokladajme, že v aritmetickej úlohe je potrebné sčítať 5 zlomkov:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Ak chcete pridať zlomky, výraz sa musí zredukovať na spoločného menovateľa, čím sa zníži problém s nájdením LCM. Ak to chcete urobiť, vyberte 5 čísel v kalkulačke a zadajte hodnoty menovateľa do príslušných buniek. Program vypočíta LCM (8, 9, 12, 15, 18) = 360. Teraz musíte pre každý zlomok vypočítať ďalšie faktory, ktoré sú definované ako pomer LCM k menovateľovi. Dodatočné multiplikátory by teda vyzerali takto:

360/8 = 45
360/9 = 40
360/12 = 30
360/15 = 24
360/18 = 20.

Potom vynásobíme všetky zlomky zodpovedajúcim dodatočným faktorom a dostaneme:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Takéto zlomky môžeme jednoducho sčítať a dostaneme výsledok v tvare 159/360. Zlomok znížime o 3 a uvidíme konečnú odpoveď - 53/120.

Riešenie lineárnych diofantínových rovníc

Lineárne diofantické rovnice sú vyjadrením tvaru ax + by = d. Ak je pomer d / gcd(a, b) celé číslo, potom je rovnica riešiteľná v celých číslach. Pozrime sa na niekoľko rovníc na možnosť celočíselného riešenia. Najprv skontrolujte rovnicu 150x + 8y = 37. Pomocou kalkulačky zistíme gcd (150,8) = 2. Vydelte 37/2 = 18,5. Číslo nie je celé číslo, preto rovnica nemá celé korene.

Skontrolujeme rovnicu 1320x + 1760y = 10120. Pomocou kalkulačky nájdite gcd(1320, 1760) = 440. Vydeľte 10120/440 = 23. Výsledkom je celé číslo, takže diofantínová rovnica v koeficiente je riešiteľná v .

Záver

GCD a LCM zohrávajú dôležitú úlohu v teórii čísel a samotné pojmy sú široko používané v rôznych oblastiach matematiky. Použite našu kalkulačku na výpočet najväčších deliteľov a najmenších násobkov ľubovoľného počtu čísel.

Najväčší spoločný deliteľ

Definícia 2

Ak je prirodzené číslo a deliteľné prirodzeným číslom $b$, potom $b$ sa nazýva deliteľ $a$ a číslo $a$ sa nazýva násobok $b$.

Nech $a$ a $b$ sú prirodzené čísla. Číslo $c$ sa nazýva spoločný deliteľ pre $a$ aj $b$.

Množina spoločných deliteľov čísel $a$ a $b$ je konečná, pretože žiadny z týchto deliteľov nemôže byť väčší ako $a$. To znamená, že medzi týmito deliteľmi je ten najväčší, ktorý sa nazýva najväčší spoločný deliteľ čísel $a$ a $b$ a na jeho označenie sa používa zápis:

$gcd \ (a;b) \ alebo \ D \ (a;b) $

Ak chcete nájsť najväčšieho spoločného deliteľa dvoch čísel:

Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najväčší spoločný deliteľ.

Príklad 1

Nájdite gcd čísel $ 121 $ a $ 132, $

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Vyberte čísla, ktoré sú zahrnuté v rozšírení týchto čísel

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najväčší spoločný deliteľ.

$gcd=2\cdot 11=22$

Príklad 2

Nájdite GCD monomiálov 63 $ a 81 $.

Nájdeme podľa prezentovaného algoritmu. Pre to:

Rozložme čísla na prvočísla

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Vyberáme čísla, ktoré sú zahrnuté do rozšírenia týchto čísel

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude želaným najväčším spoločným deliteľom.

$gcd=3\cdot 3=9$

GCD dvoch čísel môžete nájsť iným spôsobom, pomocou množiny deliteľov čísel.

Príklad 3

Nájdite gcd čísel $ 48 $ a $ 60 $.

Riešenie:

Nájdite množinu deliteľov $48$: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Teraz nájdime množinu deliteľov $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$$

Nájdeme priesečník týchto množín: $\left$(\rm 1,2,3,4,6,12)\right$$ - táto množina určí množinu spoločných deliteľov čísel $48$ a $60 $. Najväčší prvok v tejto sade bude číslo $12$. Takže najväčší spoločný deliteľ 48 $ a 60 $ je 12 $.

Definícia NOC

Definícia 3

spoločný násobok prirodzených čísel$a$ a $b$ je prirodzené číslo, ktoré je násobkom $a$ aj $b$.

Spoločné násobky čísel sú čísla, ktoré sú bezo zvyšku deliteľné originálom. Napríklad pre čísla $25$ a $50$ budú spoločnými násobkami čísla $50,100,150,200 $ atď.

Najmenší spoločný násobok sa bude nazývať najmenší spoločný násobok a označí sa LCM$(a;b)$ alebo K$(a;b).$

Ak chcete nájsť LCM dvoch čísel, potrebujete:

Rozložte čísla na prvočísla
Vypíšte faktory, ktoré sú súčasťou prvého čísla, a pridajte k nim faktory, ktoré sú súčasťou druhého čísla a nepokračujte k prvému

Príklad 4

Nájdite LCM čísel 99 $ a 77 $.

Nájdeme podľa prezentovaného algoritmu. Pre to

Rozložte čísla na prvočísla

$99=3\cdot 3\cdot 11$

Zapíšte si faktory zahrnuté v prvom

pridajte k nim faktory, ktoré sú súčasťou druhého a nejdú do prvého

Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najmenší spoločný násobok

$LCC=3\cdot 3\cdot 11\cdot 7=693$

Zostavovanie zoznamov deliteľov čísel je často časovo veľmi náročné. Existuje spôsob, ako nájsť GCD nazývaný Euklidov algoritmus.

Vyhlásenia, na ktorých je založený Euklidov algoritmus:

Ak $a$ a $b$ sú prirodzené čísla a $a\vbodky b$, potom $D(a;b)=b$

Ak $a$ a $b$ sú prirodzené čísla také, že $b

Pomocou $D(a;b)= D(a-b;b)$ môžeme postupne znižovať uvažované čísla, až kým nedosiahneme dvojicu čísel tak, že jedno z nich je deliteľné druhým. Potom menšie z týchto čísel bude požadovaným najväčším spoločným deliteľom pre čísla $a$ a $b$.

Vlastnosti GCD a LCM

Každý spoločný násobok $a$ a $b$ je deliteľný K$(a;b)$
Ak $a\vdots b$ , potom K$(a;b)=a$

Ak K$(a;b)=k$ a $m$-prirodzené číslo, potom K$(am;bm)=km$

Ak $d$ je spoločný deliteľ pre $a$ a $b$, potom K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Ak $a\vdots c$ a $b\vdots c$ , potom $\frac(ab)(c)$ je spoločný násobok $a$ a $b$

Pre všetky prirodzené čísla $a$ a $b$ je rovnosť

$D(a;b)\cdot K(a;b)=ab$

Každý spoločný deliteľ $a$ a $b$ je deliteľ $D(a;b)$

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;

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

Čísla, ktorými je číslo deliteľné (pre 12 je to 1, 2, 3, 4, 6 a 12), sa nazývajú deliteľmi čísel. Deliteľ prirodzeného čísla a je prirodzené číslo, ktoré delí dané číslo a bez stopy. Prirodzené číslo, ktoré má viac ako dva faktory, sa nazýva zložený. 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 sú obe dané čísla bezo zvyšku deliteľné a a b. Spoločný deliteľ viacerých čísel (GCD) je číslo, ktoré slúži ako deliteľ každého z nich.

Stručne povedané, najväčší spoločný deliteľ čísel a a b sú napísané takto:

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

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

Príklad:

gcd (7; 9) = 1

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

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

Najväčší spoločný deliteľ (GCD), vlastnosti.

Hlavná vlastnosť: najväčší spoločný deliteľ m a n je deliteľné akýmkoľvek spoločným deliteľom týchto čísel. Príklad: pre čísla 12 a 18 je najväčší spoločný deliteľ 6; je deliteľné všetkými spoločnými deliteľmi týchto čísel: 1, 2, 3, 6.
Dôsledok 1: množina spoločných deliteľov m a n sa zhoduje s množinou deliteľov gcd( m, n).
Dôsledok 2: množina spoločných násobkov m a n sa zhoduje so súborom viacerých LCM ( m, n).

To znamená najmä to, že na zmenšenie zlomku na neredukovateľnú formu je potrebné vydeliť jeho čitateľa a menovateľa ich gcd.

Najväčší spoločný deliteľ čísel m a n možno definovať ako najmenší kladný prvok množiny všetkých ich lineárnych kombinácií:

a preto predstavujú lineárnu kombináciu čísel m a n:

Tento pomer sa nazýva Bezoutov pomer a koeficienty u a v — bezoutové koeficienty. Bézoutove koeficienty sú efektívne vypočítané rozšíreným Euklidovým algoritmom. Toto tvrdenie je zovšeobecnené na množiny prirodzených čísel – jeho význam je taký, že podskupina skupiny vygenerovaná množinou je cyklická a je generovaná jedným prvkom: gcd ( a 1 , a 2 , … , a n).

Výpočet najväčšieho spoločného deliteľa (gcd).

Efektívne spôsoby výpočtu gcd dvoch čísel sú Euklidov algoritmus a binárnealgoritmus. Okrem toho hodnota GCD ( m,n) možno ľahko vypočítať, ak je známa kanonická expanzia čísel m a n pre hlavné faktory:

kde sú odlišné prvočísla a a sú nezáporné celé čísla (môžu byť nulové, ak zodpovedajúce prvočíslo nie je v expanzii). Potom gcd ( m,n) a LCM ( m,n) sú vyjadrené vzorcami:

Ak existujú viac ako dve čísla: , ich GCD sa nájde podľa nasledujúceho algoritmu:

- toto je požadované GCD.

Tiež s cieľom nájsť najväčší spoločný deliteľ, môžete každé z daných čísel rozložiť na prvočísla. Potom samostatne vypíšte len tie faktory, ktoré sú zahrnuté vo všetkých uvedených číslach. Potom vynásobíme čísla napísané medzi sebou - výsledkom násobenia je najväčší spoločný deliteľ .

Poďme analyzovať výpočet najväčšieho spoločného deliteľa krok za krokom:

1. Rozložte deliteľa čísel na prvočiniteľa:

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.

2. V oboch číslach podčiarkneme rovnaké prvočísla:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Nájdeme súčin identických prvočiniteľov a zapíšeme odpoveď:

GCD (28; 64) = 2. 2 = 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) = 2 u. 2. 3 = 12

Druhý spôsob zápisu GCD:

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

D(10) = (1, 2, 5, 10)

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

D(10; 15) = (1; 5)

Tento článok je venovaný takej otázke, ako je hľadanie najväčšieho spoločného deliteľa. Najprv vysvetlíme, čo to je, a uvedieme niekoľko príkladov, predstavíme definície najväčšieho spoločného deliteľa 2, 3 alebo viacerých čísel, potom sa budeme zaoberať všeobecnými vlastnosťami tohto pojmu a dokážeme ich.

Yandex.RTB R-A-339285-1

Aké sú spoločné deliče

Aby sme pochopili, čo je najväčší spoločný deliteľ, najprv sformulujeme, čo je spoločný deliteľ pre celé čísla.

V článku o násobkoch a deliteľoch sme si povedali, že celé číslo má vždy viacerých deliteľov. Tu nás zaujímajú delitele určitého počtu celých čísel naraz, najmä spoločné (identické) pre všetky. Napíšme si hlavnú definíciu.

Definícia 1

Spoločným deliteľom niekoľkých celých čísel bude číslo, ktoré môže byť deliteľom každého čísla zo zadanej množiny.

Príklad 1

Tu sú príklady takéhoto deliteľa: trojka bude spoločným deliteľom pre čísla - 12 a 9, pretože rovnosti 9 = 3 · 3 a − 12 = 3 · (− 4) sú pravdivé. Čísla 3 a -12 majú ďalších spoločných deliteľov, ako napríklad 1 , -1 a -3 . Uveďme si ďalší príklad. Štyri celé čísla 3 , − 11 , − 8 a 19 budú mať dvoch spoločných deliteľov: 1 a - 1 .

Keď poznáme vlastnosti deliteľnosti, môžeme povedať, že každé celé číslo možno deliť jednou a mínus jedna, čo znamená, že každá množina celých čísel už bude mať aspoň dvoch spoločných deliteľov.

Všimnite si tiež, že ak máme spoločného deliteľa pre niekoľko čísel b, potom tie isté čísla možno deliť opačným číslom, teda - b. V zásade môžeme brať len kladných deliteľov, potom budú aj všetky spoločné deliče väčšie ako 0 . Tento prístup je tiež možné použiť, ale záporné čísla by sa nemali úplne ignorovať.

Aký je najväčší spoločný deliteľ (gcd)

Podľa vlastností deliteľnosti, ak b je deliteľ celého čísla a, ktoré sa nerovná 0, potom modul b nemôže byť väčší ako modul a, preto každé číslo, ktoré sa nerovná 0, má konečný počet deliteľov. . To znamená, že počet spoločných deliteľov viacerých celých čísel, z ktorých aspoň jedno sa líši od nuly, bude tiež konečný a z celej ich množiny môžeme vybrať vždy najväčšie číslo (už sme hovorili o pojme najväčšieho resp. najmenšie celé čísla, odporúčame vám zopakovať daný materiál).

V ďalšom uvažovaní budeme predpokladať, že aspoň jedno z množiny čísel, pre ktoré potrebujete nájsť najväčšieho spoločného deliteľa, sa bude líšiť od 0 . Ak sa všetky rovnajú 0, potom ich deliteľ môže byť ľubovoľné celé číslo a keďže ich je nekonečne veľa, nemôžeme vybrať najväčšieho. Inými slovami, nie je možné nájsť najväčšieho spoločného deliteľa pre množinu čísel rovných 0 .

Prejdeme k formulácii hlavnej definície.

Definícia 2

Najväčší spoločný deliteľ viacerých čísel je najväčšie celé číslo, ktoré delí všetky tieto čísla.

Písomne sa najväčší spoločný deliteľ najčastejšie označuje skratkou GCD. Pre dve čísla to môže byť napísané ako gcd (a, b) .

Príklad 2

Aký je príklad GCD pre dve celé čísla? Napríklad pre 6 a - 15 by to bolo 3 . Poďme to podložiť. Najprv si zapíšeme všetkých deliteľov šiestich: ± 6, ± 3, ± 1 a potom všetkých deliteľov pätnástich: ± 15, ± 5, ± 3 a ± 1. Potom vyberieme bežné: sú to − 3 , − 1 , 1 a 3 . Z nich musíte vybrať najväčší počet. Toto bude 3.

Pre tri alebo viac čísel bude definícia najväčšieho spoločného deliteľa takmer rovnaká.

Definícia 3

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

Pre čísla a 1 , a 2 , ... , a n sa deliteľ bežne označuje ako GCD (a 1 , a 2 , ... , an) . Samotná hodnota deliteľa sa zapíše ako GCD (a 1 , a 2 , … , a n) = b .

Príklad 3

Tu sú príklady najväčšieho spoločného deliteľa niekoľkých celých čísel: 12 , - 8 , 52 , 16 . Bude sa rovnať štyrom, čo znamená, že môžeme napísať, že gcd (12, - 8, 52, 16) = 4.

Správnosť tohto tvrdenia môžete skontrolovať tak, že si zapíšete všetkých deliteľov týchto čísel a potom vyberiete najväčšieho z nich.

V praxi sa často vyskytujú prípady, keď sa najväčší spoločný deliteľ rovná jednému z čísel. To sa stane, keď všetky ostatné čísla možno vydeliť daným číslom (v prvom odseku článku sme uviedli dôkaz tohto tvrdenia).

Príklad 4

Takže najväčší spoločný deliteľ čísel 60, 15 a - 45 je 15, pretože pätnásť je deliteľné nielen 60 a - 45, ale aj samo sebou a pre všetky tieto čísla neexistuje väčší deliteľ.

Coprime čísla sú špeciálnym prípadom. Sú to celé čísla s najväčším spoločným deliteľom 1.

Hlavné vlastnosti GCD a Euklidovho algoritmu

Najväčší spoločný deliteľ má niektoré charakteristické vlastnosti. Formulujeme ich vo forme viet a každú z nich dokážeme.

Všimnite si, že tieto vlastnosti sú formulované pre celé čísla väčšie ako nula a berieme do úvahy iba kladné deliče.

Definícia 4

Čísla a a b majú najväčšieho spoločného deliteľa rovného gcd pre b a a , teda gcd (a , b) = gcd (b , a) . Zmena miesta čísel nemá vplyv na konečný výsledok.

Táto vlastnosť vyplýva zo samotnej definície GCD a nepotrebuje dôkaz.

Definícia 5

Ak číslo a možno deliť číslom b, potom množina spoločných deliteľov týchto dvoch čísel bude podobná množine deliteľov čísla b, teda gcd (a, b) = b.

Dokážme toto tvrdenie.

Dôkaz 1

Ak čísla a a b majú spoločných deliteľov, potom nimi možno deliť ktorékoľvek z nich. Zároveň, ak a je násobkom b, potom každý deliteľ b bude tiež deliteľom a, pretože deliteľnosť má takú vlastnosť ako tranzitivita. Akýkoľvek deliteľ b bude teda spoločný pre čísla a a b. To dokazuje, že ak môžeme deliť a b , potom sa množina všetkých deliteľov oboch čísel zhoduje s množinou deliteľov jedného čísla b . A keďže najväčším deliteľom akéhokoľvek čísla je samotné číslo, potom sa najväčší spoločný deliteľ čísel a a b bude rovnať aj b, t.j. gcd(a, b) = b. Ak a = b , potom gcd (a, b) = gcd (a, a) = gcd (b, b) = a = b, napríklad gcd (132, 132) = 132.

Pomocou tejto vlastnosti môžeme nájsť najväčšieho spoločného deliteľa dvoch čísel, ak jedno z nich možno deliť druhým. Takýto deliteľ sa rovná jednému z týchto dvoch čísel, ktorým možno deliť druhé číslo. Napríklad gcd (8, 24) = 8, pretože 24 je násobkom ôsmich.

Definícia 6 Dôkaz 2

Skúsme túto vlastnosť dokázať. Na začiatku máme rovnosť a = b q + c a každý spoločný deliteľ a a b bude deliť aj c , čo je vysvetlené zodpovedajúcou vlastnosťou deliteľnosti. Preto každý spoločný deliteľ b a c bude deliť a . To znamená, že množina spoločných deliteľov a a b sa bude zhodovať s množinou deliteľov b a c, vrátane najväčšieho z nich, čo znamená, že rovnosť gcd (a, b) = gcd (b, c) platí.

Definícia 7

Nasledujúca vlastnosť sa nazýva Euklidov algoritmus. S ním môžete vypočítať najväčšieho spoločného deliteľa dvoch čísel, ako aj dokázať ďalšie vlastnosti GCD.

Pred formulovaním vlastnosti vám odporúčame zopakovať vetu, ktorú sme dokázali v článku o delení zvyškom. Deliteľné číslo a možno podľa nej znázorniť ako bq + r, pričom b je deliteľ, q je nejaké celé číslo (nazýva sa aj neúplný kvocient) a r je zvyšok, ktorý spĺňa podmienku 0 ≤ r ≤ b.

Povedzme, že máme dve celé čísla väčšie ako 0, pre ktoré budú platiť nasledujúce rovnosti:

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

Tieto rovnosti končia, keď sa rk + 1 rovná 0. To sa určite stane, pretože postupnosť b > r 1 > r 2 > r 3 , ... je rad klesajúcich celých čísel, ktoré môžu obsahovať len konečný počet. Preto rk je najväčší spoločný deliteľ aab, teda rk = gcd (a, b) .

Najprv musíme dokázať, že r k je spoločný deliteľ čísel a a b, a potom, že r k nie je len deliteľ, ale najväčší spoločný deliteľ dvoch daných čísel.

Pozrime sa na zoznam rovnosti vyššie, zdola nahor. Podľa poslednej rovnosti,
r k − 1 možno deliť rk . Na základe tejto skutočnosti, ako aj predchádzajúcej preukázanej vlastnosti najväčšieho spoločného deliteľa, možno tvrdiť, že r k − 2 možno deliť r k , keďže
r k − 1 je deliteľné rk a rk je deliteľné rk .

Tretia rovnosť zdola nám umožňuje dospieť k záveru, že r k − 3 možno deliť rk atď. Druhé zdola je, že b je deliteľné rk a prvé je, že a je deliteľné rk. Z toho všetkého usudzujeme, že r k je spoločným deliteľom a a b .

Teraz dokážme, že r k = gcd (a , b) . Čo mám urobiť? Ukážte, že každý spoločný deliteľ aab bude deliť r k . Označme to r 0 .

Pozrime sa na rovnaký zoznam rovnosti, ale zhora nadol. Na základe predchádzajúcej vlastnosti môžeme usúdiť, že r 1 je deliteľné r 0 , čo znamená, že podľa druhej rovnosti je r 2 deliteľné r 0 . Prejdeme cez všetky rovnosti az poslednej z nich usúdime, že r k je deliteľné r 0 . Preto rk = gcd (a, b) .

Po zvážení tejto vlastnosti sme dospeli k záveru, že množina spoločných deliteľov aab je podobná množine deliteľov gcd týchto čísel. Toto tvrdenie, ktoré je dôsledkom Euklidovho algoritmu, nám umožní vypočítať všetkých spoločných deliteľov dvoch daných čísel.

Prejdime k ďalším vlastnostiam.

Definícia 8

Ak a a b sú celé čísla, ktoré sa nerovnajú 0, potom musia existovať ďalšie dve celé čísla u 0 a v 0, pre ktoré bude platiť rovnosť gcd (a , b) = a · u 0 + b · v 0.

Rovnosť uvedená vo výkaze vlastností je lineárnou reprezentáciou najväčšieho spoločného deliteľa aab. Nazýva sa Bezoutov pomer a čísla u 0 a v 0 sa nazývajú Bezoutove koeficienty.

Dôkaz 3

Dokážme túto vlastnosť. Postupnosť rovnosti zapíšeme podľa Euklidovho algoritmu:

Prvá rovnosť nám hovorí, že r 1 = a − b · q 1 . Označte 1 = s 1 a − q 1 = t 1 a prepíšte túto rovnosť ako r 1 = s 1 · a + t 1 · b . Tu budú čísla s 1 a t 1 celé čísla. Druhá rovnosť nám umožňuje dospieť k záveru, že 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 . Označte − s 1 q 2 = s 2 a 1 − t 1 q 2 = t 2 a prepíšte rovnosť ako r 2 = s 2 a + t 2 b , kde s 2 a t 2 budú tiež celé čísla. Je to preto, že súčet celých čísel, ich súčin a rozdiel sú tiež celé čísla. Presne rovnakým spôsobom získame z tretej rovnosti r 3 = s 3 · a + t 3 · b , z nasledujúceho r 4 = s 4 · a + t 4 · b atď. Nakoniec sme dospeli k záveru, že r k = s k a + t k b pre celé čísla s k a tk . Od rk \u003d GCD (a, b) označujeme sk \u003d u 0 a tk \u003d v 0. V dôsledku toho môžeme získať lineárne znázornenie GCD v požadovanom tvare: GCD (a, b) \u003d au 0 + bv 0.

Definícia 9

gcd (m a, m b) = m gcd (a, b) pre akúkoľvek prirodzenú hodnotu m.

Dôkaz 4

Túto vlastnosť možno zdôvodniť nasledovne. Vynásobíme číslom m obe strany každej rovnosti v Euklidovom algoritme a dostaneme, že gcd (m a , m b) = m rk a rk je gcd (a, b) . Preto gcd (ma, mb) = m gcd (a, b). Práve táto vlastnosť najväčšieho spoločného deliteľa sa využíva pri hľadaní GCD metódou faktorizácie.

Definícia 10

Ak čísla a a b majú spoločného deliteľa p , potom gcd (a: p , b: p) = gcd (a , b) : p . V prípade, že p = gcd (a, b) dostaneme gcd (a: gcd (a, b), b: gcd (a, b) = 1, teda čísla a: gcd (a, b) a b : gcd (a, b) sú koprimé.

Keďže a = p (a: p) a b = p (b: p) , potom na základe predchádzajúcej vlastnosti môžeme vytvárať rovnosti v tvare gcd (a , b) = gcd (p (a: p) , p · (b: p)) = p · GCD (a: p , b: p) , medzi ktorými bude dôkaz tejto vlastnosti. Toto tvrdenie používame, keď obyčajné zlomky redukujeme na neredukovateľnú formu.

Definícia 11

Najväčším spoločným deliteľom a 1 , a 2 , ... , ak bude číslo dk , ktoré nájdeme postupným výpočtom gcd (a 1 , a 2) = d 2 , gcd (d 2 , a 3) = d 3, gcd (d 3, a 4) = d 4, …, gcd (dk - 1, ak) = dk .

Táto vlastnosť je užitočná pri hľadaní najväčšieho spoločného deliteľa troch alebo viacerých čísel. Pomocou neho môžete túto akciu zredukovať na operácie s dvomi číslami. Jeho základom je dôsledok Euklidovského algoritmu: ak sa množina spoločných deliteľov a 1 , a 2 a a 3 zhoduje s množinou d 2 a a 3 , potom sa zhoduje aj s deliteľmi d 3 . Deliče čísel a 1 , a 2 , a 3 a a 4 sa budú zhodovať s deliteľmi d 3 , čo znamená, že sa budú zhodovať aj s deliteľmi d 4 atď. Nakoniec dostaneme, že spoloční delitelia čísel a 1 , a 2 , … , ak sa budú zhodovať s deliteľmi dk , a keďže samotné číslo bude najväčším deliteľom čísla dk , potom gcd (a 1 , a 2 , … , ak) = dk .

To je všetko, čo by sme chceli povedať o vlastnostiach najväčšieho spoločného deliteľa.

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