GGD- en KGV-rekenmachine

Grootste gemene deler en kleinste gemene veelvoud

De grootste gemene deler, kortweg GGD, van een verzameling gehele getallen is het grootste gehele getal dat elk van hen zonder rest deelt. Het kleinste gemene veelvoud, kortweg KGV, is het kleinste positieve gehele getal waar elk van hen precies in past. Deze twee begrippen komen voortdurend voor bij het vereenvoudigen van breuken, het zoeken naar gemeenschappelijke noemers, het plannen van terugkerende gebeurtenissen en het redeneren over deelbaarheid. Deze rekenmachine accepteert een hele lijst gehele getallen en geeft beide waarden tegelijk terug, samen met de stappen die eraan voorafgingen, zodat het resultaat gemakkelijk te vertrouwen is en er iets van te leren valt.

De GGD wordt gevonden met het algoritme van Euclides, dat herhaaldelijk het grotere getal vervangt door de rest van de deling door het kleinere, tot de rest nul wordt. De laatste waarde die niet nul is, is de GGD. Bij een lijst van meer dan twee getallen past de rekenmachine de bewerking toe over de hele lijst, waarbij steeds de GGD van het tussenresultaat met het volgende getal wordt genomen. Dezelfde aanpak bouwt het KGV op, met de regel dat voor elk paar geldt: KGV = a × b ÷ GGD. Zo blijven de tussenresultaten klein en wordt overflow voorkomen.

Waarom het verband werkt

Elk geheel getal is te ontbinden in priemfactoren; de GGD neemt de laagste macht van elk gedeeld priemgetal, terwijl het KGV de hoogste macht van elk voorkomend priemgetal neemt. Daarom levert het product van GGD en KGV van twee getallen hun product op: samen tellen ze elk priemgetal precies het juiste aantal keren mee. Wie dit begrijpt, ziet ook waarom het KGV nooit kleiner is dan de grootste invoer en de GGD nooit groter dan de kleinste invoer, een handige controle op elk antwoord.

Opmerkingen over invoer en privacy

Voer getallen in gescheiden door spaties, komma's of nieuwe regels; mintekens worden genegeerd omdat deelbaarheid alleen van de grootte afhangt, en nullen worden overgeslagen bij het bepalen van het KGV. De resultaten gebruiken exacte gehele rekenkunde voor gangbare invoer, al kunnen extreem grote producten de precisie van veilige gehele getallen overschrijden, controleer enorme waarden dus zelfstandig. Alle berekeningen gebeuren in je browser met mathjs en niets wat je typt wordt geüpload, opgeslagen of gedeeld.