Den största gemensamma nämnaren (GCD) av två heltal, även kallad den största gemensamma faktorn (GCF) och den största gemensamma faktor (HCF) är det största heltal som är en divisor (faktor) för dem båda. Till exempel är det största antalet som delar både 20 och 16 4. (Både 16 och 20 har större faktorer, men inga större * vanliga * faktorer - exempelvis 8 är en faktor av 16, men det är inte en faktor 20.)
I grundskolan är de flesta människor lära sig en "gissning-och-check" metod att hitta den GCD. I stället finns det ett enkelt och systematiskt sätt att göra detta som alltid hittar det rätta svaret. Metoden kallas "Euklides algoritm."
Låt oss kalla de två siffror 'a' och 'b'.
Steg
Metod 1
- 1Släpp alla negativa tecken.
- 2Känn ditt ordförråd: när du delar 32 med 5,
- 32 är utdelningen
- 5 är divisorn
- 6 är kvoten
- 2 är resten (eller modulo).
- 3Identifiera den större av de två numren. Det blir utdelningen, och mindre divisorn.
- 4Skriv ut denna algoritm: (utdelning) = (divisorn) * (kvoten) + (resten)
- 5Sätt större antal i stället för utdelning, och det mindre antal som divisor.
- 6Bestäm hur många gånger mindre antal kommer att dela in i större antal, och släpp den i algoritmen som kvoten.
- 7Beräkna resten, och ersätta det i rätt plats i algoritmen.
- 8Skriv ut algoritmen igen, men denna gång A) använda den gamla divisor som ny utdelning och B) använder resten som ny divisor.
- 9Upprepa föregående steg tills resten är noll.
- 10Den sista divisorn är den största gemensamma nämnaren.
- 11Här är ett exempel, där vi försöker hitta GCD av 108 och 30:
- 12Lägg märke till hur den 30 och 18 i de första positionerna rad Skift för att skapa den andra raden. Därefter, den 18 och 12 skift för att skapa den tredje raden, och 12 och 6 skift skapar den fjärde raden. Den 3, 1, 1, och 2 som följer multiplikationssymbolen återuppstår inte. De representerar hur många gånger nämnaren går i utdelningen, så de är unika för varje rad.
Metod 2
- 1Släpp alla negativa tecken.
- 2Hitta den främsta faktorisering av numren, och listar dem som visas.
- Använda 24 och 18 som exempel siffror:
- 24-2 x 2 x 2 x 3
- 18-2 x 3 x 3
- Använda 50 och 35 som exempel siffror:
- 50-2 x 5 x 5
- 35-5 x 7
- Använda 24 och 18 som exempel siffror:
- 3Identifiera alla vanliga primtalsfaktorer.
- Använda 24 och 18 som exempel siffror:
- 24 - 2 x 2 x 2 x 32>
- 18 - 2 x 32> x 3
- Använda 50 och 35 som exempel siffror:
- 50-2 x 5 x 5
- 35 - 5 x 7
- Använda 24 och 18 som exempel siffror:
- 4Multiplicera de gemensamma faktorer tillsammans.
- I fallet med 24 och 18, multiplicera 2 och 32> tillsammans för att få 6. Sex är den största gemensamma faktorn 24 och 18.
- I fallet med 50 och 35, det finns ingenting att föröka sig. 5 är den enda gemensamma faktorn, och därmed den största.
- 5Färdigt.
Tips
- Ett sätt att skriva detta, med hjälp av notation <dividend> mod <divisor> = resten är att GCD (a, b) = b om a mod b = 0, och GCD (a, b) = SGD (b, a mod b) på annat sätt.
- Denna teknik är mycket användbar när minska bråk. Genom ovanstående exempel reducerar den fraktion -77/91 till -11/13 eftersom 7 är den största gemensamma delaren av -77 och 91.
- Om 'a' och 'b' båda är noll, då alla utom noll skiljer dem båda, så det är tekniskt inget största gemensamma nämnaren i detta fall. Matematiker ofta bara säga att den största gemensamma nämnaren för 0 och 0 är 0, och det är svaret här metoden ger.
- Som ett exempel, låt oss hitta GCD (-77,91). Först använder 77 i stället för -77, så GCD (-77,91) blir GCD (77,91). Nu är 77 mindre än 91, så vi ska byta dem, men låt oss se hur algoritmen tar hand om att om vi inte gör det. När vi beräknar 77 mod 91, får vi 77 (sedan 77 = 91 x 0 + 77). Eftersom det är inte noll, vi switch (a, b) för (b, a mod b) och det ger oss: GCD (77,91) = SGD (91,77). 91 mod 77 ger 14 (kom ihåg, det betyder 14 är resten). Eftersom det är inte noll, byta GCD (91,77) för GCD (77,14). 77 mod 14 ger 7 som inte är noll, så byta GCD (77,14) för GCD (14,7). 14 mod 7 är noll, eftersom 14 = 7 * 2 utan resten, så vi stannar. Och det betyder: GCD (-77,91) = 7.