Indhold

• Trin
• Metode 1 af 2: Opdelingsalgoritme
• Metode 2 af 2: Prime Factors
• Tips

The Greatest Common Divisor (GCD) af to heltal er det største heltal, der deler hvert af disse tal. For eksempel er gcd for 20 og 16 4 (både 16 og 20 har store divisorer, men de er ikke almindelige - for eksempel er 8 en divisor på 16, men ikke en divisor på 20). Der er en enkel og systematisk metode til at finde GCD, kaldet "Euclids algoritme". Denne artikel viser dig, hvordan du finder den største fælles divisor af to heltal.

Trin

Metode 1 af 2: Opdelingsalgoritme

1. 1 Undlad alle minustegn.
2. 2 Lær terminologien: når man deler 32 med 5,
   • 32 - udbytte
   • 5 - divisor
   • 6 - privat
   • 2 - resten
3. 3 Bestem det største af tallene. Det vil være deleligt, og det mindre antal vil være divisoren.
4. 4 Skriv følgende algoritme ned: (udbytte) = (divisor) * (kvotient) + (resten)
5. 5 Sæt et større tal i stedet for udbyttet og et mindre tal i stedet for deleren.
6. 6 Find, hvor mange gange det større tal divideres med det mindste, og skriv resultatet i stedet for kvotienten.
7. 7 Find resten, og skriv det i den passende position i algoritmen.
8. 8 Skriv algoritmen igen, men (A) skriv den tidligere divisor som et nyt udbytte, og (B) den foregående rest som en ny divisor.
9. 9 Gentag det foregående trin, indtil resten er 0.
10. 10 Den sidste divisor vil være den største fælles divisor (GCD).
11. 11 Lad os f.eks. Finde GCD for 108 og 30:
12. 12 Læg mærke til, hvordan tallene 30 og 18 fra den første linje danner den anden linje. Så danner 18 og 12 den tredje række, og 12 og 6 danner den fjerde række. Multipler af 3, 1, 1 og 2 bruges ikke. De repræsenterer antallet af gange, udbyttet kan deles af divisoren og er derfor unikt for hver række.

Metode 2 af 2: Prime Factors

1. 1 Undlad alle minustegn.
2. 2 Find primære faktorer i tal. Præsenter dem som vist på billedet.
   • For eksempel for 24 og 18:
     • 24- 2 x 2 x 2 x 3
     • 18-2 x 3 x 3
   • For eksempel for 50 og 35:
     • 50-2 x 5 x 5
     • 35-5 x 7
3. 3 Find fælles primære faktorer.
   • For eksempel for 24 og 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • For eksempel for 50 og 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Gang de almindelige primfaktorer.
   • For 24 og 18 multipliceres 2 og 3 og få 6... 6 er den største fællesnævner af 24 og 18.
   • Der er ikke noget at gange med 50 og 35. 5 Er den eneste fælles primfaktor, og det er GCD.
5. 5 Lavet!

Tips

• En måde at skrive dette på er: dividende> mod divider> = rest; GCD (a, b) = b hvis mod b = 0 og gcd (a, b) = gcd (b, a mod b) ellers.
• Lad os som et eksempel finde GCD (-77,91). Brug først 77 i stedet for -77: GCD (-77.91) konverterer til GCD (77.91). 77 er mindre end 91, så vi er nødt til at bytte dem, men overvej, hvordan algoritmen fungerer, hvis vi ikke gør det. Ved beregning af 77 mod 91 får vi 77 (77 = 91 x 0 + 77). Da dette ikke er nul, overvejer vi situationen (b, a mod b), det vil sige GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 er resten). Det er ikke nul, så GCD (91,77) bliver til GCD (77,14). 77 mod 14 = 7. Dette er ikke nul, så GCD (77.14) bliver GCD (14.7). 14 mod 7 = 0 (siden 14/7 = 2 uden rest). Svar: GCD (-77,91) = 7.
• Den beskrevne metode er meget nyttig til forenkling af fraktioner. I eksemplet ovenfor: -77/91 = -11/13, da 7 er den største fællesnævner for -77 og 91.
• Hvis a og b er lig med nul, er ethvert ikke -nul tal deres divisor, så i dette tilfælde er der ingen GCD (matematikere mener simpelthen, at den største fælles divisor på 0 og 0 er 0).