Knikken en knikken van drie of meer cijfers. Knikken en knikken van getallen - grootste gemene deler en kleinste gemene veelvoud van verschillende getallen. Voorbeelden van het vinden van knikken en knikken

Grootste gemene deler

Definitie 2

Als een natuurlijk getal a deelbaar is door een natuurlijk getal $b$, dan wordt $b$ een deler van $a$ genoemd, en wordt $a$ een veelvoud van $b$ genoemd.

Laat $a$ en $b$ natuurlijke getallen zijn. Het getal $c$ wordt de gemeenschappelijke deler van zowel $a$ als $b$ genoemd.

De verzameling gemeenschappelijke delers van de getallen $a$ en $b$ is eindig, aangezien geen van deze delers groter kan zijn dan $a$. Dit betekent dat er onder deze delers een grootste is, die de grootste gemene deler van de getallen $a$ en $b$ wordt genoemd en wordt aangegeven met de volgende notatie:

$GCD\(a;b)\ of \D\(a;b)$

Om de grootste gemene deler van twee getallen te vinden, heb je nodig:

Zoek het product van de getallen gevonden in stap 2. Het resulterende getal zal de gewenste grootste gemene deler zijn.

voorbeeld 1

Zoek de ggd van de getallen $121$ en $132.$

$242=2\cdot 11\cdot 11$

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

Kies de getallen die zijn opgenomen in de uitbreiding van deze getallen

$242=2\cdot 11\cdot 11$

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

Zoek het product van de getallen gevonden in stap 2. Het resulterende getal zal de gewenste grootste gemene deler zijn.

$GCD=2\cdot 11=22$

Voorbeeld 2

Zoek de ggd van de monomialen $63$ en $81$.

We zullen vinden volgens het gepresenteerde algoritme. Voor deze:

Laten we de getallen omzetten in priemfactoren

$63=3\cdot 3\cdot 7$

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

Wij kiezen de getallen die worden meegenomen in de uitbreiding van deze getallen

$63=3\cdot 3\cdot 7$

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

Laten we het product vinden van de getallen uit stap 2. Het resulterende getal zal de gewenste grootste gemene deler zijn.

$GCD=3\cdot 3=9$

Je kunt de ggd van twee getallen op een andere manier vinden, met behulp van een reeks delers van getallen.

Voorbeeld 3

Zoek de ggd van de getallen $48$ en $60$.

Oplossing:

Laten we de verzameling delers van het getal $48$ vinden: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Laten we nu de verzameling delers van het getal $60$ vinden:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$ $

Laten we het snijpunt van deze sets vinden: $\left$(\rm 1,2,3,4,6,12)\right$$ - deze set bepaalt de set gemene delers van de getallen $48$ en $60 $. Het grootste element in deze set is het getal $12$. Dit betekent dat de grootste gemene deler van de getallen $48$ en $60$ $12$ is.

Definitie van NPL

Definitie 3

Gemeenschappelijke veelvouden van natuurlijke getallen$a$ en $b$ is een natuurlijk getal dat een veelvoud is van zowel $a$ als $b$.

Gemeenschappelijke veelvouden van getallen zijn getallen die deelbaar zijn door de oorspronkelijke getallen, zonder rest. Voor de getallen $25$ en $50$ zijn de gemeenschappelijke veelvouden bijvoorbeeld de getallen $50.100.150.200$, enz.

Het kleinste gemene veelvoud wordt het kleinste gemene veelvoud genoemd en wordt aangeduid met LCM$(a;b)$ of K$(a;b).$

Om de LCM van twee getallen te vinden, moet je:

Factor getallen in priemfactoren
Schrijf de factoren op die deel uitmaken van het eerste getal en tel daar de factoren bij op die deel uitmaken van het tweede getal en die geen deel uitmaken van het eerste getal

Voorbeeld 4

Zoek de LCM van de getallen $99$ en $77$.

We zullen vinden volgens het gepresenteerde algoritme. Voor deze

Factor getallen in priemfactoren

$99=3\cdot 3\cdot 11$

Schrijf de factoren op die in de eerste zijn opgenomen

voeg daar vermenigvuldigers aan toe die deel uitmaken van de tweede en niet van de eerste

Zoek het product van de getallen gevonden in stap 2. Het resulterende getal zal het gewenste kleinste gemene veelvoud zijn

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

Het samenstellen van lijsten met delers van getallen is vaak een zeer arbeidsintensieve taak. Er is een manier om GCD te vinden, het Euclidische algoritme.

Uitspraken waarop het Euclidische algoritme is gebaseerd:

Als $a$ en $b$ natuurlijke getallen zijn, en $a\vdots b$, dan is $D(a;b)=b$

Als $a$ en $b$ natuurlijke getallen zijn zodat $b

Met behulp van $D(a;b)= D(a-b;b)$ kunnen we de beschouwde getallen achtereenvolgens verkleinen totdat we een paar getallen bereiken, zodat het ene getal deelbaar is door het andere. Dan zal het kleinste van deze getallen de gewenste grootste gemene deler zijn voor de getallen $a$ en $b$.

Eigenschappen van GCD en LCM

Elk gemeenschappelijk veelvoud van $a$ en $b$ is deelbaar door K$(a;b)$
Als $a\vdots b$ is, dan is К$(a;b)=a$

Als K$(a;b)=k$ en $m$ een natuurlijk getal is, dan is K$(am;bm)=km$

Als $d$ een gemene deler is voor $a$ en $b$, dan is K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Als $a\vdots c$ en $b\vdots c$ , dan is $\frac(ab)(c)$ het gemeenschappelijke veelvoud van $a$ en $b$

Voor alle natuurlijke getallen $a$ en $b$ geldt de gelijkheid

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

Elke gemeenschappelijke deler van de getallen $a$ en $b$ is een deler van het getal $D(a;b)$

Dit artikel is gewijd aan de kwestie van het vinden van de grootste gemene deler. Eerst zullen we uitleggen wat het is en verschillende voorbeelden geven, definities introduceren van de grootste gemene deler van 2, 3 of meer getallen, waarna we zullen stilstaan bij de algemene eigenschappen van dit concept en deze zullen bewijzen.

Wat zijn gemeenschappelijke delers

Om te begrijpen wat de grootste gemene deler is, formuleren we eerst wat een gemeenschappelijke deler voor gehele getallen in het algemeen is.

In het artikel over veelvouden en delers zeiden we dat een geheel getal altijd meerdere delers heeft. Hier zijn we geïnteresseerd in de delers van een bepaald aantal gehele getallen tegelijk, vooral in de getallen die voor iedereen gemeenschappelijk (identiek) zijn. Laten we de hoofddefinitie opschrijven.

Definitie 1

De gemeenschappelijke deler van meerdere gehele getallen is een getal dat een deler kan zijn van elk getal uit de opgegeven verzameling.

voorbeeld 1

Hier zijn voorbeelden van zo'n deler: drie zal een gemeenschappelijke deler zijn voor de getallen - 12 en 9, aangezien de gelijkheden 9 = 3 · 3 en − 12 = 3 · (− 4) waar zijn. De getallen 3 en - 12 hebben nog andere gemeenschappelijke factoren, zoals 1, − 1 en − 3. Laten we nog een voorbeeld nemen. De vier gehele getallen 3, − 11, − 8 en 19 hebben twee gemeenschappelijke factoren: 1 en - 1.

Als we de eigenschappen van deelbaarheid kennen, kunnen we zeggen dat elk geheel getal kan worden gedeeld door één en min één, wat betekent dat elke reeks gehele getallen al minstens twee gemeenschappelijke delers heeft.

Merk ook op dat als we een gemeenschappelijke deler b hebben voor meerdere getallen, dezelfde getallen gedeeld kunnen worden door het tegenovergestelde getal, dat wil zeggen door - b. We kunnen in principe alleen positieve delers nemen, dan zijn alle gemene delers ook groter dan 0. Deze aanpak kan ook worden gebruikt, maar negatieve getallen mogen niet volledig worden genegeerd.

Wat is de grootste gemene deler (GCD)

Volgens de eigenschappen van deelbaarheid, als b een deler is van een geheel getal a dat niet gelijk is aan 0, dan kan de modulus van b niet groter zijn dan de modulus van a. Daarom heeft elk getal dat niet gelijk is aan 0 een eindig aantal delers. Dit betekent dat het aantal gemene delers van verschillende gehele getallen, waarvan er minstens één verschillend is van nul, ook eindig zal zijn, en uit hun hele verzameling kunnen we altijd het grootste aantal selecteren (we hebben het al gehad over het concept van de grootste en kleinste gehele getal, wij raden u aan dit materiaal te herhalen).

In verdere discussies zullen we aannemen dat ten minste één van de reeks getallen waarvoor we de grootste gemene deler moeten vinden, verschillend zal zijn van 0. Als ze allemaal gelijk zijn aan 0, kan hun deler elk geheel getal zijn, en aangezien er oneindig veel zijn, kunnen we niet de grootste kiezen. Met andere woorden: het is onmogelijk om de grootste gemene deler te vinden voor een reeks getallen gelijk aan 0.

Laten we verder gaan met het formuleren van de hoofddefinitie.

Definitie 2

De grootste gemene deler van meerdere getallen is het grootste gehele getal dat al die getallen deelt.

Schriftelijk wordt de grootste gemene deler meestal aangeduid met de afkorting GCD. Voor twee getallen kan het geschreven worden als ggd (a, b).

Voorbeeld 2

Wat is een voorbeeld van een ggd voor twee gehele getallen? Voor 6 en - 15 zou dit bijvoorbeeld 3 zijn. Laten we dit rechtvaardigen. Eerst noteren we alle delers van zes: ± 6, ± 3, ± 1, en daarna alle delers van vijftien: ± 15, ± 5, ± 3 en ± 1. Daarna kiezen we de meest voorkomende: dit zijn − 3, − 1, 1 en 3. Hiervan moet u het grootste aantal kiezen. Dit zullen er 3 zijn.

Voor drie of meer getallen zal het bepalen van de grootste gemene deler vrijwel hetzelfde zijn.

Definitie 3

De grootste gemene deler van drie of meer getallen is het grootste gehele getal dat al deze getallen tegelijkertijd deelt.

Voor getallen a 1, a 2, …, a n is het handig om de deler aan te duiden als GCD (a 1, a 2, …, a n). De waarde van de deler zelf wordt geschreven als GCD (a 1, a 2, ..., a n) = b.

Voorbeeld 3

Hier zijn voorbeelden van de grootste gemene deler van verschillende gehele getallen: 12, - 8, 52, 16. Het zal gelijk zijn aan vier, wat betekent dat we kunnen schrijven dat GCD (12, - 8, 52, 16) = 4.

Je kunt de juistheid van deze bewering controleren door alle delers van deze getallen op te schrijven en vervolgens de grootste te kiezen.

In de praktijk zijn er vaak gevallen waarin de grootste gemene deler gelijk is aan een van de getallen. Dit gebeurt wanneer alle andere getallen kunnen worden gedeeld door een bepaald getal (in de eerste paragraaf van het artikel hebben we een bewijs van deze bewering geleverd).

Voorbeeld 4

De grootste gemene deler van de getallen 60, 15 en - 45 is dus 15, aangezien vijftien niet alleen deelbaar is door 60 en - 45, maar ook door zichzelf, en er is geen grotere deler voor al deze getallen.

Een speciaal geval bestaat uit coprime-nummers. Het zijn gehele getallen met als grootste gemene deler 1.

Basiseigenschappen van GCD en Euclidisch algoritme

De grootste gemene deler heeft enkele karakteristieke eigenschappen. Laten we ze formuleren in de vorm van stellingen en ze allemaal bewijzen.

Merk op dat deze eigenschappen zijn geformuleerd voor gehele getallen groter dan nul, en we zullen alleen positieve delers beschouwen.

Definitie 4

De getallen a en b hebben een grootste gemene deler gelijk aan ggd voor b en a, dat wil zeggen ggd (a, b) = ggd (b, a). Het omkeren van getallen heeft geen invloed op het eindresultaat.

Deze eigenschap volgt uit de definitie van GCD en behoeft geen bewijs.

Definitie 5

Als het getal a kan worden gedeeld door het getal b, dan zal de reeks gemeenschappelijke delers van deze twee getallen vergelijkbaar zijn met de reeks delers van het getal b, dat wil zeggen: ggd (a, b) = b.

Laten we deze bewering bewijzen.

Bewijs 1

Als de getallen a en b gemeenschappelijke delers hebben, kan elk van beide door hen worden gedeeld. Tegelijkertijd, als a een veelvoud is van b, zal elke deler van b ook een deler van a zijn, aangezien deelbaarheid een eigenschap heeft als transitiviteit. Dit betekent dat elke deler b gemeenschappelijk zal zijn voor de getallen a en b. Dit bewijst dat als we a door b kunnen delen, de verzameling van alle delers van beide getallen zal samenvallen met de verzameling van delers van één getal b. En aangezien de grootste deler van elk getal dit getal zelf is, zal de grootste gemene deler van de getallen a en b ook gelijk zijn aan b, d.w.z. GCD (a, b) = b. Als a = b, dan ggd (a, b) = ggd (a, a) = ggd (b, b) = a = b, bijvoorbeeld ggd (132, 132) = 132.

Met behulp van deze eigenschap kunnen we de grootste gemene deler van twee getallen vinden als het ene door het andere kan worden gedeeld. Deze deler is gelijk aan één van deze twee getallen waardoor het tweede getal gedeeld kan worden. Bijvoorbeeld: ggd (8, 24) = 8, aangezien 24 een veelvoud van acht is.

Definitie 6 Bewijs 2

Laten we proberen deze eigenschap te bewijzen. We hebben aanvankelijk de gelijkheid a = b q + c, en elke gemeenschappelijke deler van a en b zal ook c delen, wat wordt verklaard door de overeenkomstige deelbaarheidseigenschap. Daarom zal elke gemeenschappelijke deler van b en c a delen. Dit betekent dat de verzameling gemeenschappelijke delers a en b zal samenvallen met de verzameling gemeenschappelijke delers b en c, inclusief de grootste daarvan, wat betekent dat de gelijkheid ggd (a, b) = ggd (b, c) waar is.

Definitie 7

De volgende eigenschap wordt het Euclidische algoritme genoemd. Met zijn hulp kun je de grootste gemene deler van twee getallen berekenen en andere eigenschappen van GCD bewijzen.

Voordat we de eigenschap formuleren, raden we je aan de stelling te herhalen die we hebben bewezen in het artikel over delen met een rest. Volgens dit kan het deelbare getal a worden weergegeven als b · q + r, waarbij b hier een deler is, q een geheel getal is (ook wel een onvolledig quotiënt genoemd), en r een rest is die voldoet aan de voorwaarde 0 ≤ r ≤ B.

Laten we zeggen dat we twee gehele getallen groter dan 0 hebben, waarvoor de volgende gelijkheden gelden:

een = 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

Deze gelijkheden eindigen wanneer rk + 1 gelijk wordt aan 0. Dit zal zeker gebeuren, aangezien de reeks b > r 1 > r 2 > r 3, ... een reeks afnemende gehele getallen is, die slechts een eindig aantal daarvan kan bevatten. Dit betekent dat rk de grootste gemene deler is van a en b, dat wil zeggen: rk = ggd (a, b).

Allereerst moeten we bewijzen dat rk de gemeenschappelijke deler is van de getallen a en b, en daarna dat rk niet alleen een deler is, maar eerder de grootste gemene deler van twee gegeven getallen.

Laten we naar de lijst met gelijkheden hierboven kijken, van onder naar boven. Volgens de laatste gelijkheid,
rk − 1 kan worden gedeeld door rk . Op basis van dit feit, evenals de eerder bewezen eigenschap van de grootste gemene deler, kan worden beargumenteerd dat rk − 2 gedeeld kan worden door rk , aangezien
rk − 1 wordt gedeeld door rk en rk wordt gedeeld door rk .

De derde gelijkheid van onderaf stelt ons in staat te concluderen dat rk − 3 gedeeld kan worden door rk , enz. De tweede van onderen is dat b deelbaar is door rk, en de eerste is dat a deelbaar is door rk. Uit dit alles concluderen we dat rk de gemeenschappelijke deler is van a en b.

Laten we nu bewijzen dat rk = GCD (a , b) . Wat moet ik doen? Laat zien dat elke gemeenschappelijke deler van a en b r k zal delen. Laten we het r 0 noemen.

Laten we naar dezelfde lijst met gelijkheden kijken, maar dan van boven naar beneden. Op basis van de voorgaande eigenschap kunnen we concluderen dat r 1 deelbaar is door r 0, wat betekent dat r 2 volgens de tweede gelijkheid gedeeld wordt door r 0. We gaan alle gelijkheden op een rij zetten en vanaf de laatste concluderen we dat rk deelbaar is door r 0 . Daarom is rk = ggd (a, b) .

Nadat we deze eigenschap hebben overwogen, concluderen we dat de set gemeenschappelijke delers a en b vergelijkbaar is met de set GCD-delers van deze getallen. Deze verklaring, die een gevolg is van het algoritme van Euclidische, zal ons in staat stellen alle gemene delers van twee gegeven getallen te berekenen.

Laten we verder gaan met andere eigendommen.

Definitie 8

Als a en b gehele getallen zijn die niet gelijk zijn aan 0, dan moeten er twee andere gehele getallen u 0 en v 0 zijn waarvoor de gelijkheid GCD (a, b) = a · u 0 + b · v 0 geldig zal zijn.

De gelijkheid die in de eigenschapsverklaring wordt gegeven, is een lineaire weergave van de grootste gemene deler van a en b. Het wordt de Bezout-relatie genoemd, en de getallen u 0 en v 0 worden de Bezout-coëfficiënten genoemd.

Bewijs 3

Laten we deze eigenschap bewijzen. Laten we de reeks gelijkheden opschrijven met behulp van het Euclidische algoritme:

De eerste gelijkheid vertelt ons dat r 1 = a − b · q 1 . Laten we 1 = s 1 en − q 1 = t 1 aanduiden en deze gelijkheid herschrijven in de vorm r 1 = s 1 · a + t 1 · b. Hier zijn de getallen s 1 en t 1 gehele getallen. De tweede gelijkheid stelt ons in staat te concluderen dat r 2 = b − r 1 · q 2 = b − (s 1 · a + t 1 · b) · q 2 = − s 1 · q 2 · a + (1 − t 1 · vraag 2) b . Laten we − s 1 · q 2 = s 2 en 1 − t 1 · q 2 = t 2 aanduiden en de gelijkheid herschrijven als r 2 = s 2 · a + t 2 · b, waarbij s 2 en t 2 ook zullen zijn gehele getallen. Dit komt omdat de som van gehele getallen, hun product en verschil ook gehele getallen zijn. Op precies dezelfde manier verkrijgen we uit de derde gelijkheid r 3 = s 3 · a + t 3 · b, uit de volgende r 4 = s 4 · a + t 4 · b, enz. Uiteindelijk concluderen we dat rk = s k · a + t k · b voor gehele getallen sk en t k . Omdat rk = GCD (a, b), duiden we s k = u 0 en t k = v 0 aan. Als resultaat kunnen we een lineaire weergave van GCD in de vereiste vorm verkrijgen: GCD (a, b) = a · u 0 + b · v 0.

Definitie 9

GCD (m a, m b) = m GCD (a, b) voor elke natuurlijke waarde van m.

Bewijs 4

Deze eigenschap kan als volgt worden gerechtvaardigd. Laten we beide zijden van elke gelijkheid in het Euclidische algoritme vermenigvuldigen met het getal m en zo krijgen dat GCD (m · a, m · b) = m · rk, en rk is GCD (a, b). Dit betekent ggd (m a, m b) = m ggd (a, b). Het is deze eigenschap van de grootste gemene deler die wordt gebruikt bij het vinden van de GCD met behulp van de factorisatiemethode.

Definitie 10

Als de getallen a en b een gemeenschappelijke deler p hebben, dan is ggd (a: p, b: p) = ggd (a, b): p. In het geval dat p = GCD (a, b) verkrijgen we GCD (a: GCD (a, b), b: GCD (a, b) = 1, daarom de getallen a: GCD (a, b) en b : GCD (a, b) zijn relatief priem.

Omdat a = p (a: p) en b = p (b: p), kunnen we op basis van de vorige eigenschap gelijkheden creëren van de vorm ggd (a, b) = ggd (p (a: p), p · (b: p)) = p · GCD (a: p , b: p) , waaronder een bewijs van deze eigenschap. We gebruiken deze verklaring wanneer we gewone breuken reduceren tot een onherleidbare vorm.

Definitie 11

De grootste gemene deler van a 1, a 2, …, a k is het getal d k, dat kan worden gevonden door opeenvolgend GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3 te berekenen , GCD (d 3 , een 4) = d 4 , ... , GCD (d k - 1 , een k) = d k .

Deze eigenschap is handig bij het vinden van de grootste gemene deler van drie of meer getallen. Hiermee kunt u deze actie reduceren tot bewerkingen met twee cijfers. De basis ervan is een uitvloeisel van het Euclidische algoritme: als de verzameling gemene delers a 1, a 2 en a 3 samenvalt met de verzameling d 2 en a 3, dan zal deze ook samenvallen met de delers d 3. De delers van de getallen a 1, a 2, a 3 en a 4 zullen samenvallen met de delers van d 3, wat betekent dat ze ook zullen samenvallen met de delers van d 4, enz. Uiteindelijk krijgen we dat de gemeenschappelijke delers van de getallen a 1, a 2, ..., a k zullen samenvallen met de delers d k, en aangezien de grootste deler van het getal d k dit getal zelf zal zijn, dan is GCD (a 1, een 2, ..., een k) = dk.

Dat is alles wat we u willen vertellen over de eigenschappen van de grootste gemene deler.

Als u een fout in de tekst opmerkt, markeer deze dan en druk op Ctrl+Enter

Laten we het probleem oplossen. We hebben twee soorten cookies. Sommige zijn van chocolade en andere zijn puur. Er zijn 48 chocoladekoekjes en 36 gewone. Je moet het maximaal mogelijke aantal geschenken uit deze koekjes halen, en je moet ze allemaal gebruiken.

Laten we eerst alle delers van elk van deze twee getallen opschrijven, aangezien beide getallen deelbaar moeten zijn door het aantal geschenken.

We krijgen

48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Laten we een van de gemeenschappelijke delers vinden die zowel het eerste als het tweede getal hebben.

Gemeenschappelijke factoren zijn: 1, 2, 3, 4, 6, 12.

De grootste gemene deler van allemaal is het getal 12. Dit getal wordt de grootste gemene deler van de getallen 36 en 48 genoemd.

Op basis van de verkregen resultaten kunnen we concluderen dat er met alle koekjes 12 cadeaus gemaakt kunnen worden. Eén zo'n geschenk bevat 4 chocoladekoekjes en 3 gewone koekjes.

Het vinden van de grootste gemene deler

Het grootste natuurlijke getal dat twee getallen a en b deelt zonder rest, wordt de grootste gemene deler van deze getallen genoemd.

Soms wordt de afkorting GCD gebruikt om de vermelding in te korten.

Sommige getallenparen hebben één als grootste gemene deler. Dergelijke nummers worden gebeld onderling priemgetallen. De getallen 24 en 35 hebben bijvoorbeeld GCD =1.

Hoe de grootste gemene deler te vinden

Om de grootste gemene deler te vinden, is het niet nodig om alle delers van de gegeven getallen op te schrijven.

Je kunt het anders doen. Factoreer eerst beide getallen in priemfactoren.

48 = 2*2*2*2*3,
36 = 2*2*3*3.

Nu zullen we van de factoren die zijn opgenomen in de uitbreiding van het eerste getal, alle factoren schrappen die niet zijn opgenomen in de uitbreiding van het tweede getal. In ons geval zijn dit twee tweeën.

48 = 2*2*2*2*3 ,
36 = 2*2*3 *3.

De resterende factoren zijn 2, 2 en 3. Hun product is 12. Dit getal zal de grootste gemene deler zijn van de getallen 48 en 36.

Deze regel kan worden uitgebreid tot het geval van drie, vier, enz. cijfers.

Algemeen schema voor het vinden van de grootste gemene deler

1. Verdeel getallen in priemfactoren.
2. Van de factoren die zijn opgenomen in de uitbreiding van een van deze getallen, schrapt u de factoren die niet zijn opgenomen in de uitbreiding van andere getallen.
3. Bereken het product van de overige factoren.

Hoofdstuk 1. Natuurlijke getallen

1.6. Grootste gemene deler en kleinste gemene veelvoud

Eerder noemden we de delers van getallen. Laten we nu proberen samengestelde getallen in priemfactoren te ontbinden.

Definitie

Een getal ontbinden in priemfactoren betekent dat je het voorstelt als een gelijk product van priemgetallen.

De ontleding in priemfactoren van getallen ziet er als volgt uit:
; .
De ontbinding in priemfactoren van getallen , , kan in een andere vorm worden weergegeven:

198	2	2574	2	255	3
	3	1287	3		5
	3		3		17
	11		11
			13

Nu zal ik dit op een regel opschrijven
.

Erg goed! Je bent gewoon een genie.

Ik begrijp nog steeds niet hoe je zo snel hebt geraden dat het getal deelbaar is door ?

En het is eenvoudig. Ik heb de test van deelbaarheid door gebruikt. Laten we er op letten dat in de werken die u zojuist hebt opgenomen, het nummer wordt herhaald.

Definitie

Het getal waardoor elk van deze getallen wordt gedeeld, wordt de gemeenschappelijke deler van deze getallen genoemd.

Die. in ons geval is het getal de gemene deler?

Ja, dat is wat ik wilde zeggen. En als je de getallen en neemt, dan hebben ze, zoals je kunt zien, drie gemeenschappelijke delers: , en (de ) niet meegerekend.

Ik begrijp het niet?...

Definitie

De grootste gemene deler van deze getallen wordt hun grootste gemene deler genoemd en wordt afgekort als GCD.

Je moet niet vergeten dat GCD een grote rol speelt in de wiskunde.

Ik zie nu al dat in de wiskunde alle concepten een grote rol spelen. En hoe onthoud je ze allemaal? Hoe vind je deze GCD?

Maak je geen zorgen, ze zullen na verloop van tijd gedenkwaardig worden als je ze regelmatig gebruikt.
Dus laten we doorgaan. Vinden GCD verschillende getallen, je kunt ze ontbinden in priemfactoren, hun gemeenschappelijke priemfactoren opschrijven en vermenigvuldigen.

Dit is goed. Maar er zijn getallen die geen andere gemeenschappelijke deler hebben dan één! Bijvoorbeeld, en, en .

Ja, dat heb je goed opgemerkt.

Definitie

Getallen die geen gemeenschappelijke delers hebben (behalve één), worden relatief priemgetallen genoemd.

Wat betekent dit: alle priemgetallen zullen ook relatief priemgetallen zijn?

En in dit geval heb je gelijk! We moeten een dergelijk concept echter nog steeds beschouwen als het kleinste gemene veelvoud van de LCM.

Definitie

Het getal dat deelbaar is door elk van deze getallen wordt het gemeenschappelijke veelvoud van deze getallen genoemd.

Dus voor getallen en het gemene veelvoud zijn elk van de getallen: , , , , LCM.

Goed gedaan. Wat denk je dat de LCM van coprime-nummers zal zijn?

Ik zal het nu uitzoeken. Ze hebben geen andere delers dan eenheid, en daarom is hun product hun LCM!

Dit is gewoon geweldig! Wat een geweldige conclusie.
En aan het einde van ons onderzoek wil ik je vertellen hoe je de LOC kunt vinden als deze niet duidelijk is.

In dit geval worden deze getallen opgesplitst in priemfactoren. Vervolgens worden alle factoren uitgeschreven vanaf het grootste getal en worden de ontbrekende factoren uit de uitbreidingen van de resterende getallen eraan toegevoegd.

Ja, ik ben tevreden, ik vond het leuk.

Dit artikel gaat over het vinden van de grootste gemene deler (GCD) twee of meer cijfers. Laten we eerst eens kijken naar het Euclid-algoritme; hiermee kun je de ggd van twee getallen vinden. Hierna zullen we ons concentreren op een methode waarmee we de ggd van getallen kunnen berekenen als het product van hun gemeenschappelijke priemfactoren. Vervolgens gaan we kijken naar het vinden van de grootste gemene deler van drie of meer getallen, en geven we ook voorbeelden van het berekenen van de ggd van negatieve getallen.

Paginanavigatie.

Euclidisch algoritme voor het vinden van GCD

Merk op dat als we vanaf het allereerste begin naar de tabel met priemgetallen hadden gekeken, we erachter zouden zijn gekomen dat de getallen 661 en 113 priemgetallen zijn, waaruit we meteen zouden kunnen zeggen dat hun grootste gemene deler 1 is.

Antwoord:

GCD(661, 113)=1.

GCD vinden door getallen in priemfactoren te ontbinden

Laten we een andere manier overwegen om GCD te vinden. De grootste gemene deler kan worden gevonden door getallen in priemfactoren te ontbinden. Laten we een regel formuleren: De ggd van twee positieve gehele getallen a en b is gelijk aan het product van alle gemeenschappelijke priemfactoren gevonden in de priemfactorisaties van de getallen a en b.

Laten we een voorbeeld geven om de regel voor het vinden van GCD uit te leggen. Laat ons de ontbindingen van de getallen 220 en 600 in priemfactoren weten, ze hebben de vorm 220=2·2·5·11 en 600=2·2·2·3·5·5. De gemeenschappelijke priemfactoren die betrokken zijn bij het ontbinden van de getallen 220 en 600 zijn 2, 2 en 5. Daarom is ggd(220, 600)=2·2·5=20.

Dus als we de getallen a en b in priemfactoren ontbinden en het product van al hun gemeenschappelijke factoren vinden, dan vinden we de grootste gemene deler van de getallen a en b.

Laten we een voorbeeld bekijken van het vinden van GCD volgens de gestelde regel.

Voorbeeld.

Zoek de grootste gemene deler van de getallen 72 en 96.

Oplossing.

Laten we de getallen 72 en 96 ontbinden in priemfactoren:

Dat wil zeggen, 72=2·2·2·3·3 en 96=2·2·2·2·2·3. Veel voorkomende priemfactoren zijn 2, 2, 2 en 3. Dus GCD(72, 96)=2·2·2·3=24.

Antwoord:

GCD(72, 96)=24.

Ter afsluiting van deze paragraaf merken we op dat de geldigheid van de bovenstaande regel voor het vinden van GCD volgt uit de eigenschap van de grootste gemene deler, die stelt dat GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), waarbij m een positief geheel getal is.

Het vinden van de ggd van drie of meer getallen

Het vinden van de grootste gemene deler van drie of meer getallen kan worden teruggebracht tot het opeenvolgend vinden van de ggd van twee getallen. We hebben dit vermeld bij het bestuderen van de eigenschappen van GCD. Daar formuleerden en bewezen we de stelling: de grootste gemene deler van meerdere getallen a 1, a 2, ..., a k is gelijk aan het getal d k, dat wordt gevonden door opeenvolgend GCD(a 1, a 2)=d 2 te berekenen , GCD(d 2, een 3) =d 3, GCD(d 3, een 4)=d 4,..., GCD(d k-1, een k)=d k.

Laten we eens kijken hoe het proces van het vinden van de ggd van verschillende getallen eruit ziet door naar de oplossing van het voorbeeld te kijken.

Voorbeeld.

Vind de grootste gemene deler van de vier getallen 78, 294, 570 en 36.

Oplossing.

In dit voorbeeld is een 1 =78, een 2 =294, een 3 =570, een 4 =36.

Eerst bepalen we met behulp van het Euclidische algoritme de grootste gemene deler d 2 van de eerste twee getallen 78 en 294. Bij het delen verkrijgen we de gelijkheden 294 = 78 3 + 60 ; 78=60·1+18 ; 60=18·3+6 en 18=6·3. Dus d2=GCD(78, 294)=6.

Laten we nu berekenen d 3 =GGD(d 2, a 3)=GGD(6, 570). Laten we het Euclidische algoritme opnieuw toepassen: 570=6·95, dus d 3 = GCD(6, 570)=6.

Het blijft om te berekenen d 4 =GGD(d 3, a 4)=GGD(6, 36). Omdat 36 deelbaar is door 6, geldt d 4 = GCD(6, 36) = 6.

De grootste gemene deler van de vier gegeven getallen is dus d 4 =6, dat wil zeggen ggd(78, 294, 570, 36)=6.

Antwoord:

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

Door getallen in priemfactoren te ontbinden, kunt u ook de ggd van drie of meer getallen berekenen. In dit geval wordt de grootste gemene deler gevonden als het product van alle gemeenschappelijke priemfactoren van de gegeven getallen.

Voorbeeld.

Bereken de ggd van de getallen uit het vorige voorbeeld met behulp van hun priemfactorisaties.

Oplossing.

Laten we de getallen 78, 294, 570 en 36 ontbinden in priemfactoren, we krijgen 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2 ·3· 3. De gemeenschappelijke priemfactoren van al deze vier getallen zijn de getallen 2 en 3. Vandaar, GCD(78, 294, 570, 36)=2·3=6.