QuickCalculators kör Euklides algoritm på två icke-negativa heltal och skriver ut varje kvot och rest tills SGD syns som den sista nollskilda resten. Ange paret i vilken ordning som helst; stegtabellen visar divisionsformen så att varje rad kan kontrolleras för hand.
Hitta SGD genom upprepad division
Euklides algoritm hittar den största gemensamma faktorn genom att dividera det större talet med det mindre och ersätta det större med resten, och sedan upprepa. När en rest på noll syns är divisoren från det steget SGD. Euklides algoritm registrerar varje division så att kedjan är granskningsbar.
För 816 och 2260, börja med 2260 ÷ 816. Kvoten är 2 och resten är 628. Nästa, 816 ÷ 628 lämnar resten 188. Fortsätt tills en nollrest stoppar kedjan. Den sista nollskilda resten är SGD för det ursprungliga paret.
Läs stegtabellen
Stegtabellen listar dividend, divisor, kvot och rest för varje runda. Att läsa ner restkolumnen visar den krympande följden som slutar vid noll. QuickCalculators justerar de kolumnerna så att en anteckningsbokskopia kan verifiera att a × b + r är lika med den föregående dividenden på varje rad.
En kompakt skiss för 48 och 18:
| Dividend | Divisor | Kvot | Rest |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
Den sista nollskilda resten är 6, så SGD(48, 18) = 6.
Undvik det här vanliga misstaget
Subtraktionsformen och divisionsformen är samma algoritm. Division är upprepad subtraktion komprimerad till en kvot. Elever behandlar dem ibland som rivaliserande metoder med olika svar. Båda avslutas vid samma SGD när de tillämpas korrekt. Att subtrahera 18 från 48 två gånger når 12, vilket är exakt vad kvot 2 kodar på en rad.
Att föredra division sparar skrivande utan att ändra den matematiska vägen Euklides beskrev.
Förstå varför algoritmen alltid avslutas
Varje rest är ett icke-negativt heltal strikt mindre än den föregående divisoren, så restföljden kan inte sjunka för alltid. Ändlig nedstigning tvingar en nollrest efter ändligt många steg. Den garantin gäller för alla icke-negativa heltalsindata sidan accepterar.
Värsta-fall-par relaterade till Fibonaccital behöver fler steg än typiska klassrumsexempel, men avslutas ändå. Stegantalet växer ungefär med logaritmen av indata för vanliga slumpmässiga par, vilket är varför Euklides metod skalar förbi listning av faktorer.
Vanliga frågor
Vad är Euklides algoritm?
Euklides algoritm är en metod för att hitta den största gemensamma faktorn av två icke-negativa heltal genom upprepad division med rest. Den sista nollskilda resten är SGD. Kalkylatorn skriver ut var och en av de divisionsstegen.
Hur hittar Euklides algoritm SGD?
Euklides algoritm hittar SGD genom att ersätta det större talet med resten efter division med det mindre talet, och upprepa tills resten är noll. Divisoren som används i det sista nollskilda-rest-steget är SGD.
Vad är SGD av 816 och 2260?
SGD av 816 och 2260 hittas genom att köra Euklides algoritm på det paret och läsa den sista nollskilda resten från stegtabellen. Ange båda heltalen på den här sidan för att se varje kvot och rest i ordning.
Varför fungerar Euklides algoritm?
Euklides algoritm fungerar eftersom varje gemensam delare av a och b också är en gemensam delare av b och a mod b. Att ersätta paret med det mindre talet och resten bevarar SGD tills resten når noll.
Hur många steg tar Euklides algoritm?
Antalet steg Euklides algoritm tar beror på indata; varje rest är mindre än den föregående divisoren, så processen är ändlig. Fibonacci-liknande par behöver fler steg än genomsnittet, men typiska klassrumstal avslutas snabbt.
Vad är skillnaden mellan subtraktions- och divisionsformerna?
Subtraktionsformen subtraherar upprepade gånger det mindre från det större; divisionsformen subtraherar i bulk med en kvot. Båda formerna beräknar samma SGD. Division är bara upprepad subtraktion skriven kompakt.
Sammanfattning
Euklides algoritm hittar en SGD genom upprepad division och visar varje kvot och rest i en stegtabell. Par som 48 och 18 slutar vid resten 6, vilket matchar SGD(48, 18). Subtraktions- och divisionsformerna är samma algoritm på olika komprimeringsnivåer. Rester minskar strikt, så processen avslutas alltid för icke-negativa heltal.