crowde.ru

Ontdek de grootste gemene deler van twee gehele getallen


De grootste gemene deler (gcd) van twee gehele getallen is het grootste gehele getal dat als een deler voor beide getallen kan dienen. Het grootste getal dat zowel 20 als 16 kan verdelen, is bijvoorbeeld 4. (Zowel 16 als 20 hebben grotere delers, maar geen grotere gemeenschappelijk Divider - 8 is b.v. een deler van 16, maar niet 20)

Op de basisschool wordt kinderen meestal geleerd dat ze de gcd kunnen vinden door "proberen en controleren". Maar er is ook een eenvoudige en systematische manier om het resultaat goed te krijgen. Deze methode wordt het "Euclidisch algoritme" genoemd.

Methode 1
1

Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 1
1
Verwijder alle negatieve tekens.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 2
    2
    Ken de wiskundige uitdrukkingen: Als je 32 bij 5 deelt, dan is dat
  • 32 het dividend
  • 5 de deler
  • 6 het quotiënt
  • 2 de rest (of modulo).
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 3
    3
    Bepaal de grootste van de twee cijfers. Dit zal het dividend zijn en des te kleiner de deler.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 4
    4
    Schrijf het algoritme op: (Dividend) = (deler) * (quotiënt) + (rest)
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 5
    5
    Zet het grotere aantal op de plaats van het dividend en het kleinere op de plaats van de deler.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 6
    6
    Bepaal hoe vaak het kleinere getal in de grotere past en schrijf het resultaat op de plaats van het quotiënt.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 7
    7
    Bereken de resterende hoeveelheid en schrijf deze op de juiste plaats in het algoritme.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 8
    8
    Schrijf het algoritme nog een keer op met de waarden, maar gebruik ditmaal A) de oude deler als een nieuw dividend en B) de rest als een nieuwe deler.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 9
    9
    Herhaal de vorige stap totdat de rest nul is.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 10
    10
    De laatste deler die wordt ontvangen, is de grootste gemene deler.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 11
    11
    Hier is een voorbeeld waarin we de gcd van 108 en 30 proberen te vinden:
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 12
    12
    Merk op hoe de 30s en 18s in de eerste regel van positie wisselen om de tweede regel te maken. Daarna worden 18 en 12 omgewisseld om de derde lijn te produceren, en op dezelfde manier worden 12 en 6 omgewisseld om de vierde regel te produceren. De waarden 3, 1, 1 en 2 geschreven na het vermenigvuldigingsteken verschijnen niet meer. Ze laten zien hoe vaak de deler in de dividenden past en daarom uniek zijn voor elke lijn.

    • Methode 2
    2

    Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 13
    1
    Verwijder alle negatieve tekens.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 14
    2
    Splits elk nummer in zijn primaire factoren en noteer het op de manier zoals in het volgende voorbeeld wordt getoond.
  • De cijfers voor ons voorbeeld 1 zijn 24 en 18:
  • 24 = 2 x 2 x 2 x 3
  • 18 = 2 x 3 x 3
  • De cijfers voor ons voorbeeld 2 zijn 50 en 35:
  • 50 = 2 x 5 x 5
  • 35 = 5x7
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Step 15
    3
    Bepaal alle gangbare priemgetallen.
  • In Voorbeeld 1:
  • 24 = 2 x 2 x 2 x 3
  • 18 = 2 X 3 x 3
  • In voorbeeld 2:
  • 50 = 2 x 5 x 5
  • 35 = 5 x 7
  • 4
    Vermenigvuldig de gemeenschappelijke priemfactoren met elkaar.
  • In voorbeeld 1 vermenigvuldigt u de twee priemfactoren 2 en 3, je ontvangt 6. Dit is het 6 de grootste gemene deler van 24 en 18.
  • In voorbeeld 2 kun je niets met elkaar vermenigvuldigen. 5 is de enige gemene deler van 50 en 35 en dus automatisch de grootste gemene deler.
  • Titel afbeelding Find the Greatest Common Divisor of Two Integers Intro
    5
    Klaar.

    • tips

    • Een mogelijke spelling is het gebruik van notatie modern = Restant, waarbij het resultaat gcd (a, b) = b is, als een mod b = 0, en anders gcd (a, b) = gcd (b, a mod b).
    • Laten we dit doen met behulp van het voorbeeld van gcd (-77,91). Eerst gebruiken we 77 in plaats van -77, dus gcd (-77.91) wordt gcd (77.91). Aangezien 77 minder is dan 91, moeten we de waarden omwisselen. Maar laten we eens kijken hoe het algoritme zich gedraagt ​​als we dat niet doen. Als we 77 mod 91 berekenen, krijgen we 77 (sinds 77 = 91 x 0 + 77). Omdat dit niet gelijk is aan nul, wisselen we (a, b) met (b, een mod b) en krijgen we: gcd (77,91) = gcd (91,77). 91 mod 77 geeft 14 (onthoud dat 14 de rest is). Aangezien dit niet gelijk is aan nul, wisselen we gcd (91.77) uit met gcd (77.14). 77 mod 14 retourneert 7, wat niet gelijk is aan nul. We wisselen gcd (77,14) uit met gcd (14,7). 14 mod 7 is hetzelfde Nul, aangezien 14 = 7 * 2 zonder rest, dus stoppen we op dit punt. En dat betekent: gcd (-77,91) = 7.
    • Deze techniek is zeer nuttig bij het verkorten van fracturen. Om bij het bovenstaande voorbeeld te blijven, kan de breuk -77/91 worden afgekapt tot -11/13 omdat 7 de grootste gemene deler is van -77 en 91.
    • Als `a` en `b` allebei nul zijn, kunnen beide getallen gedeeld worden door elk getal dat niet nul is, dus in dat geval is er feitelijk geen grootste gemene deler. Wiskundigen zeggen in dit geval dat de grootste gemene deler in dit geval ook nul is en dat is ook het resultaat van dit algoritme.
    Delen op sociale netwerken:

    Verwant