Innehåll

• Steg
• Metod 1 av 2: Delningsalgoritm
• Metod 2 av 2: Prime Factors
• Tips

The Greatest Common Divisor (GCD) för två heltal är det största heltalet som delar vart och ett av dessa tal. Till exempel är gcd för 20 och 16 4 (både 16 och 20 har stora avdelare, men de är inte vanliga - till exempel är 8 en delare på 16, men inte en delare på 20). Det finns en enkel och systematisk metod för att hitta GCD, kallad "Euklids algoritm". Den här artikeln visar dig hur du hittar den största gemensamma delaren av två heltal.

Steg

Metod 1 av 2: Delningsalgoritm

1. 1 Utelämna alla minustecken.
2. 2 Lär dig terminologin: när man delar 32 med 5,
   • 32 - utdelning
   • 5 - delare
   • 6 - privat
   • 2 - resten
3. 3 Bestäm den största av siffrorna. Det kommer att vara delbart, och det mindre antalet kommer att vara delaren.
4. 4 Skriv ner följande algoritm: (utdelning) = (delare) * (kvot) + (resten)
5. 5 Sätt ett större antal i stället för utdelningen och ett mindre antal i stället för avdelaren.
6. 6 Hitta hur många gånger det större antalet divideras med det mindre, och skriv resultatet istället för kvoten.
7. 7 Hitta resten och skriv det i lämplig position i algoritmen.
8. 8 Skriv algoritmen igen, men (A) skriv den föregående avdelaren som en ny utdelning, och (B) den föregående återstoden som en ny delare.
9. 9 Upprepa föregående steg tills resten är 0.
10. 10 Den sista delaren kommer att vara den största gemensamma delaren (GCD).
11. 11 Låt oss till exempel hitta GCD för 108 och 30:
12. 12 Lägg märke till hur siffrorna 30 och 18 från första raden utgör den andra raden. Sedan bildar 18 och 12 den tredje raden, och 12 och 6 bildar den fjärde raden. Multiplar av 3, 1, 1 och 2 används inte. De representerar antalet gånger utdelningen är delbar med delaren och är därför unik för varje rad.

Metod 2 av 2: Prime Factors

1. 1 Utelämna alla minustecken.
2. 2 Hitta talfaktorer. Presentera dem som visas på bilden.
   • Till exempel för 24 och 18:
     • 24- 2 x 2 x 2 x 3
     • 18-2 x 3 x 3
   • Till exempel för 50 och 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 Hitta vanliga främsta faktorer.
   • Till exempel för 24 och 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Till exempel för 50 och 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Multiplicera de vanliga primfaktorerna.
   • För 24 och 18, multiplicera 2 och 3 och få 6... 6 är den största gemensamma nämnaren för 24 och 18.
   • Det finns inget att multiplicera för 50 och 35. 5 Är den enda vanliga primfaktorn, och det är GCD.
5. 5 Gjord!

Tips

• Ett sätt att skriva detta är: utdelning> mod divider> = resten; GCD (a, b) = b om mod b = 0 och gcd (a, b) = gcd (b, a mod b) annars.
• Som ett exempel, låt oss hitta GCD (-77,91). Använd först 77 istället för -77: GCD (-77.91) konverterar till GCD (77.91). 77 är mindre än 91, så vi måste byta dem, men överväga hur algoritmen fungerar om vi inte gör det. Vid beräkning av 77 mod 91 får vi 77 (77 = 91 x 0 + 77). Eftersom detta inte är noll betraktar vi situationen (b, en mod b), det vill säga GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 är resten). Det är inte noll, så GCD (91,77) blir GCD (77,14). 77 mod 14 = 7. Detta är inte noll, så GCD (77.14) blir GCD (14.7). 14 mod 7 = 0 (sedan 14/7 = 2 utan rester). Svar: GCD (-77,91) = 7.
• Den beskrivna metoden är mycket användbar för att förenkla fraktioner. I exemplet ovan: -77/91 = -11/13, eftersom 7 är den största gemensamma nämnaren för -77 och 91.
• Om a och b är lika med noll är alla icke -nolltal deras divisor, så i detta fall finns det ingen GCD (matematiker tror helt enkelt att den största gemensamma divisorn 0 och 0 är 0).