The Greatest Common Divisor (PTS) av to heltall, også kalt Greatest Common Factor (GCF), er det største heltallet som er divisor (faktor) for begge tallene. For eksempel er det største tallet som kan dele både 20 og 16 4. (Både 16 og 20 har større faktorer, men ingen større lik faktor - for eksempel er 8 en faktor på 16, men ikke en faktor på 20.) I barneskolen, blir de fleste lært gjett-og-sjekk-metoden for å finne GCF. Imidlertid er det en enklere og mer systematisk måte å gjøre dette på som alltid gir det riktige svaret. Denne metoden kalles Euklides algoritme. Hvis du virkelig vil vite hvordan du finner den største fellesfaktoren for to heltall, kan du ta en titt på trinn 1 for å komme i gang.
Steg
Metode 1 av 2: Bruke divisoralgoritmen
Trinn 1. Fjern alle negative tegn
Trinn 2. Kjenn ditt ordforråd:
når du deler 32 med 5,
-
- 32 er et tall som er delt på
- 5 er deler av
- 6 er kvoten
- 2 er resten (eller modulo).
Trinn 3. Identifiser tallet som er større enn de to tallene
Det større tallet vil være tallet som er delt, og det mindre vil være divisoren.
Trinn 4. Skriv ned denne algoritmen:
(delt nummer) = (divisor) * (sitat) + (resten)
Trinn 5. Sett det større tallet på stedet for tallet som skal deles, og det mindre tallet som divisoren
Trinn 6. Bestem hva som er resultatet av å dele det større tallet med det mindre tallet, og skriv inn resultatet som kvotienten
Trinn 7. Beregn resten, og skriv den inn på riktig sted i algoritmen
Trinn 8. Skriv om algoritmen, men denne gangen A) bruker du den gamle divisoren som deler og B) bruker resten som deler
Trinn 9. Gjenta forrige trinn til resten er null
Trinn 10. Den siste deleren er den samme største deleren
Trinn 11. Her er et eksempel, hvor vi prøver å finne GCF på 108 og 30:
Trinn 12. Legg merke til hvordan 30 og 18 i den første raden bytter posisjoner for å lage den andre raden
Deretter bytter 18 og 12 posisjoner for å lage den tredje raden, og 12 og 6 bytter posisjoner for å lage den fjerde raden. 3, 1, 1 og 2 etter multiplikasjonstegnet dukker ikke opp igjen. Dette tallet representerer resultatet av å dele tallet dividert med divisoren, slik at hver rad er forskjellig.
Metode 2 av 2: Bruke Prime Factors
Trinn 1. Eliminer eventuelle negative tegn
Trinn 2. Finn primfaktoriseringen av tallene, og skriv listen som vist nedenfor
-
Bruk 24 og 18 som eksempler på tall:
- 24- 2 x 2 x 2 x 3
- 18-2 x 3 x 3
-
Bruker 50 og 35 som et eksempelnummer:
- 50-2 x 5 x 5
- 35-5 x 7
Trinn 3. Identifiser alle hovedfaktorene som er like
-
Bruk 24 og 18 som eksempler på tall:
-
24-
Steg 2. x 2 x 2
Trinn 3.
-
18-
Steg 2
Trinn 3. x 3
-
-
Bruker 50 og 35 som et eksempelnummer:
-
50-2 x
Trinn 5. x 5
-
35-
Trinn 5. x 7
-
Trinn 4. Multipliser faktorene med det samme
-
I spørsmål 24 og 18, multipliser
Steg 2. da
Trinn 3. å få
Trinn 6.. Seks er den største fellesfaktoren på 24 og 18.
-
I eksemplene 50 og 35 kan ingen av tallene multipliseres.
Trinn 5. er den eneste faktoren til felles, og som sådan er den største faktoren.
Trinn 5. Ferdig
Tips
- En måte å skrive dette på, ved å bruke notasjonen mod = rest, er GCF (a, b) = b, hvis a mod b = 0, og GCF (a, b) = GCF (b, a mod b) ellers.
- Finn for eksempel GCF (-77, 91). Først bruker vi 77 i stedet for -77, så GCF (-77, 91) blir GCF (77, 91). Nå er 77 mindre enn 91, så vi må bytte dem, men la oss se hvordan algoritmen kommer rundt disse tingene hvis vi ikke kan. Når vi beregner 77 mod 91, får vi 77 (fordi 77 = 91 x 0 + 77). Siden resultatet ikke er null, bytter vi (a, b) til (b, en mod b), og resultatet er: GCF (77, 91) = GCF (91, 77). 91 mod 77 gir 14 (husk, det betyr at 14 er ubrukelig). Siden resten ikke er null, konverter GCF (91, 88) til GCF (77, 14). 77 mod 14 returnerer 7, som ikke er null, så bytt GCF (77, 14) til GCF (14, 7). 14 mod 7 er null, så 14 = 7 * 2 uten rest, så vi stopper. Og det betyr: GCF (-77, 91) = 7.
- Denne teknikken er spesielt nyttig når du forenkler brøk. Fra eksemplet ovenfor forenkler fraksjonen -77/91 til -11/13 fordi 7 er den største like divisoren til -77 og 91.
- Hvis 'a' og 'b' er null, deler ingen null tall dem, så teknisk sett er ingen største divisor det samme i problemet. Matematikere sier ofte at den største fellesdeleren til 0 og 0 er 0, og det er svaret de får på denne måten.
