Wkono

Hvordan finne den største felles divisor av to heltall


Den største felles divisor (GCD) av to hele tall, også kalt den største felles faktor (GCF) og Største felles faktor (HCF), er den største hele tall som er en divisor (faktor) av dem begge. For eksempel er det største tallet som deler både 20 og 16 4. (Både 16 og 20 har større faktorer, men ingen større * vanlige * faktorer - for eksempel, åtte er en faktor på 16, men det er ikke en faktor på 20).

I grunnskolen, de fleste er lært en "gjett-og-sjekk"-metoden for å finne GCD. I stedet er det en enkel og systematisk måte å gjøre dette på som alltid finner det riktige svaret. Metoden kalles "Euklids algoritme."

La oss kalle de to tallene 'a' og 'b'.

Trinn

Hvordan finne den største felles divisor av to heltall. Slippe alle negative tegn.
Hvordan finne den største felles divisor av to heltall. Slippe alle negative tegn.

Metode 1

  1. 1
    Slippe alle negative tegn.
  2. 2
    Kjenn din vokabular: når du deler 32 med 5,
      • 32 er utbytte
      • 5 er divisoren
      • 6 er kvotienten
      • 2 er resten (eller modulo).
  3. 3
    Identifisere den største av de to tallene. Det vil være utbytte, og jo mindre divisor.
  4. 4
    Skriv ut denne algoritmen: (utbytte) = (divisor) * (kvotient) + (rest)
  5. 5
    Sette større antall i stedet for utbytte, og mindre antall som divisor.
  6. 6
    Bestemme hvor mange ganger mindre antall vil dele inn i større antall, og slipp den inn i algoritmen som kvotienten.
  7. 7
    Beregne resten, og erstatte det i det riktige sted i algoritmen.
  8. 8
    Skriv ut algoritmen igjen, men denne gangen A) bruke den gamle divisor som ny utbytte og B) bruke resten som det nye divisor.
  9. 9
    Gjenta forrige trinn til resten er null.
  10. 10
    Den siste divisor er det største felles divisor.
  11. 11
    Her er et eksempel, hvor vi prøver å finne GCD av 108 og 30:
  12. 12
    Legg merke til hvordan den 30 og 18 i første linje skift posisjoner for å skape den andre linjen. Deretter til 18 og 12 dreining for å skape den tredje linje, og den 12 og seks skift skape den fjerde linje. 3, 1, 1 og 2 som følger multiplikasjonstegn ikke igjen. De representerer hvor mange ganger divisor går inn i utbytte, så de er unike for hver linje.

Metode 2

  1. 1
    Slippe alle negative tegn.
  2. 2
    Finn den prime faktorisering av tallene, og skriv dem ut som vist.
    • Ved hjelp av 24 og 18 som eksempel tall:
      • 24-2 x 2 x 2 x 3
      • 18-2 x 3 x 3
    • Ved hjelp av 50 og 35 som eksempelnumrene:
      • 50-2 x 5 x 5
      • 35-5 x 7
  3. 3
    Identifiser alle vanlige primfaktorer.
    • Ved hjelp av 24 og 18 som eksempel tall:
      • 24 - 2 x 2 x 2 x 32>
      • 18 - 2 x 32> x 3
    • Ved hjelp av 50 og 35 som eksempelnumrene:
      • 50-2 x 5 x 5
      • 35 - 5 x 7
  4. 4
    Multipliser de vanligste faktorene sammen.
    • I tilfellet med 24 og 18, multipliseres 2 og 32> sammen for å få 6. Seks er den største felles faktor på 24 og 18 år.
    • I tilfellet med 50 og 35, er det ingenting å formere seg. 5 er den eneste felles faktor, og derfor den største.
  5. 5
    Ferdige.

Tips

  • En måte å skrive dette, ved hjelp av notasjon <dividend> mod <divisor> = resten er at GCD (a, b) = b hvis en mod b = 0, og GCD (a, b) = GCD (b, a mod b) på annen måte.
  • Denne teknikken er veldig nyttig når redusere fraksjoner. Av eksempelet ovenfor, reduserer brøkdel -77/91 til -11/13 fordi 7 er den største felles divisor av -77 og 91.
  • Hvis 'a' og 'b' er både null, så alle ikke-null nummer skiller dem begge, så det er teknisk sett ingen største felles divisor i dette tilfellet. Matematikere ofte bare si at den største felles divisor av 0 og 0 er 0, og det er svaret denne metoden gir.
  • Som et eksempel, la oss finne GCD (-77,91). Først bruker 77 istedenfor -77, så GCD (-77,91) blir GCD (77,91). Nå er 77 mindre enn 91, så vi bør bytte dem, men la oss se hvordan algoritmen tar seg av det hvis vi ikke gjør det. Når vi beregner 77 mod 91, får vi 77 (siden 77 = 91 x 0 + 77). Siden det ikke er null, vi bryter (a, b) for (b, a mod b) og som gir oss: GCD (77,91) = GCD (91,77). 91 mod 77 gir 14 (husk, det betyr at 14 er resten). Siden det ikke er null, bytte GCD (91,77) for GCD (77,14). 77 mod 14 gir syv som ikke er null, så bytte GCD (77,14) for GCD (14,7). 14 mod 7 er null, siden 14 = 7 * 2 uten rest, så vi stoppe. Og det betyr: GCD (-77,91) = 7.