Diofantische vergelijking ax + by = c oplossen met stappen

Vul de coëfficiënten van de lineaire diofantische vergelijking ax + by = c in. De vergelijking hieronder is gekoppeld aan de invoervelden, dus je kunt de getallen er ook rechtstreeks in aanpassen. Verander “Gewenste oplossingen” om alleen de positieve geheeltallige oplossingen te bewaren.

Coëfficiënt a van x

Coëfficiënt b van y

Constante c rechts

Gewenste oplossingen

Vul alleen gehele getallen in (geen kommagetallen of breuken). Negatieve getallen mogen wel. Is er geen x- of y-term, vul dan 0 in als coëfficiënt.

Resultaat en grafiek

Vul links de coëfficiënten a, b en c in en klik op “Berekenen”. De geheeltallige oplossingen en een grafiek verschijnen hier.

Inhoudsopgave

[ SLUITEN ]

Wat je op deze pagina kunt doen
Waarvoor is deze berekening handig?
Zo werkt het
Formules en grafieken
Symbolen en begrippen
- Symbolen
- Begrippen
Handig om vooraf te weten
Berekenen met Excel
Berekenen met Google Spreadsheets
Berekenen met Python
De formule in LaTeX en andere wiskundenotaties (om te kopiëren)
Zo laat je ChatGPT de berekening doen
Kenmerken van DataChef
Gerelateerde functies
Alle rekenmachines van NumberChef

Wat je op deze pagina kunt doen

Vul de gehele coëfficiënten \(a,\ b,\ c\) in en je krijgt de paren gehele getallen \(x,\ y\) die voldoen aan \(ax + by = c\) (de geheeltallige oplossingen)
Is \(c\) geen veelvoud van de grootste gemene deler van \(a\) en \(b\), dan zijn er geen geheeltallige oplossingen. De pagina controleert dit en laat ook zien waarom
Je kunt de tabel met delingen van het algoritme van Euclides volgen en de tabel die terug rekent via de resten om een particuliere oplossing te maken, rij voor rij
Het antwoord is niet maar één paar: je krijgt de algemene oplossing \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (waarbij \(t\) een geheel getal is) en een tabel met oplossingen voor verschillende waarden van \(t\)
Je kunt alleen de positieve oplossingen bewaren of alleen de niet-negatieve. Zo los je vraagstukken op als “hoeveel kaartjes van € 50 en € 80 zijn samen precies € 1.000?” rechtstreeks op

Je kunt alleen gehele getallen als coëfficiënten gebruiken (geen kommagetallen of breuken). Elke coëfficiënt mag maximaal 15 cijfers hebben, en \(a\) en \(b\) mogen niet allebei 0 zijn.

Waarvoor is deze berekening handig?

Combinaties vinden die precies een bedrag of aantal opleveren

Alleen kaartjes van € 50 en € 80 kopen voor precies € 1.000, iets wegen met maar twee soorten gewichten, of een exacte lengte maken van stukken van vaste lengte: vraagstukken als deze, “combineer dingen van vaste grootte om precies een doel te halen”, zijn precies het probleem van het vinden van geheeltallige oplossingen van \(ax + by = c\).
Je kunt geen negatief aantal kaartjes kopen, dus in de praktijk krijg je het antwoord pas als je beperkt tot de positieve geheeltallige oplossingen.

Zien welke bestelgroottes precies kunnen worden ingepakt

Heb je alleen dozen van 6 en dozen van 10, dan hangt het van \(6x + 10y = c\) af of je een bestelling van precies \(c\) stuks kunt inpakken: er moet een oplossing zijn met gehele getallen van 0 of meer. De ggd van 6 en 10 is 2, dus een bestelling van een oneven aantal stuks kun je nooit precies inpakken, hoe je de dozen ook combineert.
Bij het inpakken van eten of onderdelen weet je met zo’n berekening welke aantallen kunnen en dus welke bestellingen je kunt aannemen en welke dozen je moet hebben.

Een exacte hoeveelheid afmeten met kannen zonder maatverdeling

Het bekende raadsel om precies 4 liter af te meten met alleen een kan van 5 liter en een kan van 3 liter komt overeen met de geheeltallige oplossingen van \(5x + 3y = 4\) (\(x\) en \(y\) tellen, met een teken, hoe vaak je elke kan vult of leegschenkt). Omdat \(\gcd(5,\ 3) = 1\), vertelt de vergelijking je van tevoren dat deze twee kannen elk geheel aantal liters kunnen afmeten.
Het is dezelfde wiskunde als in een laboratorium of keuken wanneer je vraagt: “Kan ik de hoeveelheid die ik nodig heb afmeten met alleen het gereedschap dat ik heb?”

Sleutels maken voor RSA-versleuteling op internet

RSA-versleuteling, die internetbankieren en online winkelen beveiligt, maakt de waarde \(d\) van de privésleutel uit de waarde \(e\) van de publieke sleutel door de lineaire diofantische vergelijking \(e d + \varphi k = 1\) op te lossen (\(\varphi\) is een geheel getal dat van de sleutel afhangt). Het gereedschap daarvoor is hetzelfde uitgebreid algoritme van Euclides als op deze pagina.
Deze procedure lost het ook voor getallen van honderden cijfers meteen op, en dat is een van de dingen die de versleuteling praktisch maken.

Productieplanning die al het materiaal opmaakt

Stel dat product A \(a\) kg materiaal per stuk gebruikt en product B \(b\) kg, en je wilt precies de \(c\) kg opmaken die je hebt. Dit plan is het probleem van het vinden van oplossingen van \(ax + by = c\) in gehele getallen van 0 of meer. Je kunt geen half product maken, dus het antwoord moet een geheel getal zijn.
Het vakgebied dat planningsproblemen behandelt waarvan de antwoorden gehele getallen moeten zijn, heet geheeltallig programmeren. Het wordt gebruikt voor productieplanning, personeelsroosters, bezorgplanning en meer.

Formules en grafieken

Wanneer er geheeltallige oplossingen zijn

Grafiek

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(c\) \(=\) \(\gcd(a,\ b)\) \(\times\) \(m\)

In woorden (symbolen vervangen door woorden)

③ \(c\): constante rechts \(=\) ① \(g\): ggd van \(a\) en \(b\) \(\times\) ② \(m\): een geheel getal

De formule in woorden

① Vermenigvuldig de \(g\): ggd van \(a\) en \(b\)

② met \(m\): een geheel getal

③ Kan dit product precies gelijk zijn aan de \(c\): constante rechts (dat wil zeggen als \(c\) een veelvoud van \(g\) is), dan zijn er geheeltallige oplossingen. Zo niet, dan zijn die er niet

Een eenvoudig voorbeeld

\(2x + 4y = 6\) heeft geheeltallige oplossingen, maar \(2x + 4y = 5\) heeft er helemaal geen (bij beide is \(\gcd(2,\ 4) = 2\))

constante rechts (6) \(=\) ggd (2) \(\times\) geheel getal (3)

\(\gcd(2,\ 4) = 2\)

\(6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6\)

\(5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5\)

Het belangrijkste idee

Waarom moet \(c\) een veelvoud van \(g\) zijn? Zowel \(a\) als \(b\) zijn veelvouden van \(g\), dus je kunt \(a = g a'\) en \(b = g b'\) schrijven. Dan wordt het linkerlid \(ax + by = g(a'x + b'y)\) Zolang \(x\) en \(y\) gehele getallen zijn, is het linkerlid altijd een veelvoud van \(g\) en niets anders. Is \(c\) rechts dus geen veelvoud van \(g\), dan kunnen geen ingevulde gehele getallen beide kanten aan elkaar gelijk maken. Is \(c\) daarentegen wel een veelvoud van \(g\), dan bestaat er altijd een oplossing (de identiteit van Bézout, de volgende formule, garandeert dat). In de grafiek is het verschil of de lijn \(ax + by = c\) door roosterpunten gaat (punten waarvan de \(x\)- en \(y\)-coördinaat allebei gehele getallen zijn) of tussen ze door glipt.

Identiteit van Bézout (één paar gehele getallen uit het algoritme van Euclides)

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(a x_1\) \(+\) \(b y_1\) \(=\) \(\gcd(a,\ b)\)

In woorden (symbolen vervangen door woorden)

① \(a x_1\): \(a\) maal het gehele getal \(x_1\) uit het algoritme van Euclides \(+\) ② \(b y_1\): \(b\) maal het gehele getal \(y_1\) uit het algoritme van Euclides \(=\) ③ \(g\): ggd van \(a\) en \(b\)

De formule in woorden

① Tel de term \(a x_1\): \(a\) maal het gehele getal \(x_1\) uit het algoritme van Euclides

② en de term \(b y_1\): \(b\) maal het gehele getal \(y_1\) uit het algoritme van Euclides

③ op, dan kan de som gelijk worden gemaakt aan de \(g\): ggd van \(a\) en \(b\) . Zulke gehele getallen \(x_1,\ y_1\) bestaan altijd, en je vindt ze door het algoritme van Euclides terug te lopen

Een eenvoudig voorbeeld

Voer het algoritme van Euclides uit op \(7\) en \(5\) en werk terug via de resten (\(\gcd(7,\ 5) = 1\))

\(7\) maal het gehele getal \(-2\) \(+\) \(5\) maal het gehele getal \(3\) \(=\) ggd (1)

\(7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1\)

\(1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7\)

\(7 \times (-2) + 5 \times 3 = -14 + 15 = 1\)

Het belangrijkste idee

Elke rest in het algoritme van Euclides kun je schrijven als som van gehele veelvouden van de twee oorspronkelijke getallen. Inderdaad, \(2 = 7 - 5\), en vul je dit in voor de \(2\) in de volgende stap, \(1 = 5 - 2 \times 2\), dan wordt \(1\) een som van gehele veelvouden van \(7\) en \(5\). Het uitgebreid algoritme van Euclides doet dit stap voor stap voor elk tweetal getallen. Het paar \(x_1,\ y_1\) dat je vindt, maakt van de ggd \(g\), niet \(c\), dus het is nog geen oplossing van jouw vergelijking. Vermenigvuldig beide kanten met \(\dfrac{c}{g}\) en je krijgt één oplossing van de gewenste vergelijking. \(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\) Bijvoorbeeld voor \(7x + 5y = 3\): vermenigvuldig de vergelijking hierboven met 3 om \(7 \times (-6) + 5 \times 9 = 3\) te krijgen, dus \((x_0,\ y_0) = (-6,\ 9)\) is één oplossing. Deze rekenmachine verschuift de gevonden oplossing naar kleinere, makkelijker te lezen getallen voordat ze die toont (met welk paar je ook begint, de algemene oplossing hieronder geeft dezelfde verzameling oplossingen).

Alle geheeltallige oplossingen (algemene oplossing)

Grafiek

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(x\) \(=\) \(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\)

\(y\) \(=\) \(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\)

In woorden (symbolen vervangen door woorden)

\(x\): geheeltallige oplossing \(=\) ① \(x_0\): particuliere oplossing \(+\) ② \(\dfrac{b}{g}\): stapgrootte van \(x\) ③ \(t\): een willekeurig geheel getal

\(y\): geheeltallige oplossing \(=\) ④ \(y_0\): particuliere oplossing \(-\) ⑤ \(\dfrac{a}{g}\): stapgrootte van \(y\) \(t\): een willekeurig geheel getal

De formule in woorden

① Begin bij de \(x_0\): particuliere oplossing

② en tel erbij de \(\dfrac{b}{g}\): stapgrootte van \(x\)

③ maal \(t\): een willekeurig geheel getal . Dit geeft de geheeltallige oplossing \(x\)

④ Begin tegelijk bij de \(y_0\): particuliere oplossing

⑤ en trek er de \(\dfrac{a}{g}\): stapgrootte van \(y\) maal dezelfde \(t\) van af. Dit geeft de geheeltallige oplossing \(y\). Elk geheel getal dat je voor \(t\) invult, geeft weer een oplossing, en samen zijn het alle geheeltallige oplossingen

Een eenvoudig voorbeeld

Bij \(3x + 4y = 10\) is één oplossing \((x_0,\ y_0) = (2,\ 1)\), en \(\gcd(3,\ 4) = 1\), dus

\(x\): geheeltallige oplossing \(=\) particuliere oplossing (2) \(+\) stapgrootte (4) geheel getal \(t\)

\(y\): geheeltallige oplossing \(=\) particuliere oplossing (1) \(-\) stapgrootte (3) geheel getal \(t\)

\(3 \times 2 + 4 \times 1 = 10\)

\(x = 2 + 4t, \quad y = 1 - 3t\)

\(t = 1 \ \Rightarrow \ (x,\ y) = (6,\ -2), \quad 3 \times 6 + 4 \times (-2) = 10\)

\(t = -1 \ \Rightarrow \ (x,\ y) = (-2,\ 4), \quad 3 \times (-2) + 4 \times 4 = 10\)

Het belangrijkste idee

Waarom verspringt \(x\) alleen in stappen van \(\dfrac{b}{g}\) en \(y\) alleen in stappen van \(\dfrac{a}{g}\)? Als \((x,\ y)\) en \((x_0,\ y_0)\) allebei oplossingen zijn, geeft het aftrekken van de ene vergelijking van de andere \(a(x - x_0) = -b(y - y_0)\) Deel beide kanten door \(g\) en je krijgt \(\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)\). Hier zijn \(\dfrac{a}{g}\) en \(\dfrac{b}{g}\) relatief priem (hun enige gemeenschappelijke deler is 1). Het linkerlid moet dus een veelvoud van \(\dfrac{b}{g}\) zijn. Omdat \(\dfrac{a}{g}\) geen deler met \(\dfrac{b}{g}\) gemeen heeft, moet \(x - x_0\) zelf een veelvoud van \(\dfrac{b}{g}\) zijn. Dat wil zeggen \(x - x_0 = \dfrac{b}{g}t\), en de formule voor \(y\) volgt daaruit. In de grafiek liggen de roosterpunten op de lijn \(ax + by = c\) op gelijke afstanden van elkaar: \(\dfrac{b}{g}\) opzij en \(\dfrac{a}{g}\) omhoog of omlaag.

Beperken tot positieve geheeltallige oplossingen

Grafiek

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\) \(\geq 1\)

\(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\) \(\geq 1\)

In woorden (symbolen vervangen door woorden)

① \(x_0\): particuliere oplossing \(+\) ② \(\dfrac{b}{g}\): stapgrootte van \(x\) ③ \(t\): een willekeurig geheel getal \(\geq 1\)

④ \(y_0\): particuliere oplossing \(-\) ⑤ \(\dfrac{a}{g}\): stapgrootte van \(y\) \(t\): een willekeurig geheel getal \(\geq 1\)

De formule in woorden

① De \(x_0\): particuliere oplossing

② plus de \(\dfrac{b}{g}\): stapgrootte van \(x\)

③ maal \(t\): een willekeurig geheel getal (dat is de geheeltallige oplossing \(x\)) moet minstens 1 zijn, en

④ de \(y_0\): particuliere oplossing

⑤ min de \(\dfrac{a}{g}\): stapgrootte van \(y\) maal dezelfde \(t\) (dat is de geheeltallige oplossing \(y\)) moet ook minstens 1 zijn. Zoek het bereik van \(t\) dat aan beide voldoet en je hebt alle positieve geheeltallige oplossingen

Een eenvoudig voorbeeld

Om precies 47 stuks te krijgen met alleen verpakkingen van 3 en van 5 (\(3x + 5y = 47\), \((x_0,\ y_0) = (4,\ 7)\)):

particuliere oplossing (4) \(+\) stapgrootte (5) geheel getal \(t\) \(\geq 1\)

particuliere oplossing (7) \(-\) stapgrootte (3) geheel getal \(t\) \(\geq 1\)

\(3 \times 4 + 5 \times 7 = 47\)

\(4 + 5t \geq 1 \ \Leftrightarrow \ t \geq -\dfrac{3}{5} \ \Leftrightarrow \ t \geq 0\)

\(7 - 3t \geq 1 \ \Leftrightarrow \ t \leq 2\)

\(0 \leq t \leq 2 \ \Rightarrow \ (x,\ y) = (4,\ 7),\ (9,\ 4),\ (14,\ 1)\)

Het belangrijkste idee

Bij vraagstukken waarin je kaartjes, stuks of mensen telt, moet het antwoord een positief geheel getal zijn (of een geheel getal van 0 of meer). Zet je de algemene oplossing in ongelijkheden en zoek je het bereik van \(t\), dan houd je alleen de oplossingen over die passen. Omdat \(t\) een geheel getal is, kun je, ook als een grens een breuk is zoals \(t \geq -\dfrac{3}{5}\), die aanscherpen tot het dichtstbijzijnde gehele getal erbinnen (hier \(t \geq 0\)). Dat is de sleutelstap. Hebben \(a\) en \(b\) hetzelfde teken (bijvoorbeeld allebei positief), dan geeft de ene ongelijkheid een ondergrens en de andere een bovengrens, dus er zijn altijd eindig veel oplossingen. Zijn de tekens verschillend (bijvoorbeeld \(3x - 5y = 1\)), dan wijzen beide grenzen dezelfde kant op en zijn er oneindig veel positieve geheeltallige oplossingen. Is een coëfficiënt 0 (bijvoorbeeld \(0x + 5y = 10\)), dan heeft de andere variabele precies één waarde en kan de variabele met de coëfficiënt 0 alles zijn. Voldoet die ene waarde aan de voorwaarde, dan zijn er oneindig veel oplossingen; zo niet, dan zijn er geen. Het kan ook gebeuren dat geen enkele \(t\) aan de voorwaarde voldoet. Dan is het antwoord “er is geen combinatie die werkt”.

De lineaire diofantische vergelijking \(ax + by = c\) heeft alleen geheeltallige oplossingen als \(c\) een veelvoud is van \(g\), de grootste gemene deler van \(a\) en \(b\). Is dat zo, werk dan terug via het algoritme van Euclides om één particuliere oplossing \((x_0,\ y_0)\) te maken. Dan is elke andere oplossing \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (waarbij \(t\) een geheel getal is).

Symbolen en begrippen

Symbolen

\(a,\ b\)	a, b	De coëfficiënten die \(x\) en \(y\) vermenigvuldigen. Letters aan het begin van het alfabet, \(a,\ b,\ c\), worden van oudsher voor vaste getallen gebruikt. Op deze pagina zijn beide gehele getallen.
\(c\)	c	De constante rechts van de vergelijking. Het is het totaal dat je wilt bereiken, en of het een veelvoud van de ggd is, bepaalt of er oplossingen zijn.
\(x,\ y\)	x, y	De onbekenden die je oplost. Het gebruik van letters aan het eind van het alfabet voor onbekenden is een gewoonte die door Descartes zou zijn verspreid. Op deze pagina tellen alleen gehele waarden als antwoord.
\(\gcd(a,\ b)\)	ggd van a en b	De grootste gemene deler van \(a\) en \(b\). In Nederlandse schoolboeken schrijf je dit meestal als ggd(a, b); de internationale afkorting gcd komt van “greatest common divisor”. In boeken over getaltheorie wordt het soms afgekort tot \((a,\ b)\).
\(g\)	g	Een korte naam voor de grootste gemene deler \(\gcd(a,\ b)\). Zo blijven formules kort, zoals \(\dfrac{b}{g}\) en \(\dfrac{a}{g}\) in de algemene oplossing.
\(x_0,\ y_0\)	x nul, y nul	De particuliere oplossing, dus de eerste geheeltallige oplossing die je vindt. De kleine 0 geeft aan dat het het beginpunt is, “oplossing nummer 0”. Elke geheeltallige oplossing wordt vanaf hier opgeschreven.
\(x_1,\ y_1\)	x met index 1, y met index 1	Het paar gehele getallen dat je vindt door het algoritme van Euclides terug te lopen. Het voldoet aan \(a x_1 + b y_1 = g\). Vermenigvuldig het met \(\dfrac{c}{g}\) om de particuliere oplossing \((x_0,\ y_0)\) te krijgen.
\(t\)	t	Een variabele die elk geheel getal mag zijn (een parameter). Zo kan één formule alle geheeltallige oplossingen in één keer beschrijven. Elk geheel getal dat je voor \(t\) invult, geeft weer een geheeltallige oplossing.
\(m\)	m	Het gehele getal dat zegt hoeveel keer \(g\) in \(c\) past. Letters als \(m\), \(n\) en \(k\) worden vaak voor gehele getallen gebruikt. Geheeltallige oplossingen bestaan als je \(c = g \times m\) kunt schrijven, en alleen dan.
\(q\)	q	Het quotiënt van een deling. In de tabel van het algoritme van Euclides is het de \(2\) in \(13 = 5 \times 2 + 3\).
\(r\)	r	De rest van een deling. In de tabel van het algoritme van Euclides is het de \(3\) in \(13 = 5 \times 2 + 3\). Het algoritme stopt als deze rest 0 wordt.
\(\geq\)	is groter dan of gelijk aan	Het teken van de ongelijkheid voor “het linkerlid is groter dan of gelijk aan het rechterlid”. \(x \geq 1\) zegt dat \(x\) minstens 1 is. Het tegenovergestelde \(\leq\) zegt “kleiner dan of gelijk aan”.

Begrippen

lineaire diofantische vergelijking	De eenvoudigste soort diofantische vergelijking: een lineaire vergelijking met twee onbekenden maar één vergelijking, zoals \(ax + by = c\). Bij reële getallen is elk punt op de lijn een oplossing, dus de oplossing is niet uniek. Ook als je alleen geheeltallige oplossingen bewaart, zijn het er meestal oneindig veel.
diofantische vergelijking	De naam voor vergelijkingen waarvan de antwoorden gehele getallen moeten zijn. De naam komt van Diofantos, een wiskundige uit het oude Griekenland. De lineaire diofantische vergelijking op deze pagina is de eenvoudigste soort.
geheeltallige oplossing	Een oplossing van de vergelijking waarbij zowel \(x\) als \(y\) gehele getallen zijn. Bij vraagstukken over hoeveelheden die je niet kunt splitsen, zoals aantallen kaartjes, stuks of mensen, hebben alleen geheeltallige oplossingen betekenis.
particuliere oplossing	Het eerste paar dat je vindt onder de oneindig veel geheeltallige oplossingen. Elk paar is goed. Vanaf dit paar beschrijft de algemene oplossing alle oplossingen.
algemene oplossing	Alle geheeltallige oplossingen opgeschreven als één formule met een geheel getal \(t\). Elk geheel getal dat je voor \(t\) invult, geeft weer een oplossing.
grootste gemene deler (ggd)	Het grootste positieve gehele getal dat elk van twee of meer gehele getallen deelt. In het Engels heet het de greatest common divisor (gcd). Bij een lineaire diofantische vergelijking bepaalt deze waarde zowel of er oplossingen zijn als hoe ver ze uit elkaar liggen.
algoritme van Euclides	Een manier om de grootste gemene deler te vinden door steeds het grotere getal door het kleinere te delen en het paar te vervangen door de deler en de rest. De deler op het moment dat de rest 0 wordt, is de ggd. Het staat in de “Elementen” van Euclides uit de 3e eeuw v.Chr. en wordt vaak het oudste algoritme ter wereld genoemd.
uitgebreid algoritme van Euclides	Een manier om de grootste gemene deler te schrijven in de vorm \(a x_1 + b y_1\) door de vergelijkingen van het algoritme van Euclides van onderaf weer in te vullen. Je gebruikt het om een particuliere oplossing van een lineaire diofantische vergelijking te maken.
identiteit van Bézout	De stelling dat er altijd gehele getallen \(x_1,\ y_1\) bestaan met \(a x_1 + b y_1 = \gcd(a,\ b)\). Ze is genoemd naar de Franse wiskundige Bézout. Het is de reden dat een lineaire diofantische vergelijking kan worden opgelost.
relatief priem	Twee gehele getallen zijn relatief priem (ook wel onderling ondeelbaar) als hun grootste gemene deler 1 is. 3 en 4 zijn bijvoorbeeld relatief priem. \(\dfrac{a}{g}\) en \(\dfrac{b}{g}\) zijn altijd relatief priem, en daarom liggen de oplossingen op gelijke afstanden.
veelvoud	Een getal dat je krijgt door een geheel getal met een ander geheel getal te vermenigvuldigen. De veelvouden van \(10\) zijn \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\). Ook 0 en negatieve getallen tellen mee.
rest	Wat er overblijft als een deling met gehele getallen niet precies uitkomt. \(13 \div 5\) heeft quotiënt \(2\) en rest \(3\). Het algoritme van Euclides werkt alleen met deze resten.
quotiënt	Bij een deling met gehele getallen het hele aantal keren dat de deler past. In \(13 = 5 \times 2 + 3\) is het quotiënt \(2\).
roosterpunt	Een punt in het coördinatenvlak waarvan de \(x\)- en \(y\)-coördinaat allebei gehele getallen zijn, zoals de hoekpunten van de hokjes op ruitjespapier. De geheeltallige oplossingen van een lineaire diofantische vergelijking zijn precies de roosterpunten op de lijn \(ax + by = c\).
parameter	Een variabele die je vrij mag veranderen en die je gebruikt om een hele verzameling oplossingen als één formule te schrijven. Op deze pagina is \(t\) de parameter.
coëfficiënt	Het getal voor een letter. In \(3x\) is de coëfficiënt \(3\). Staat er geen getal, zoals bij \(x\), dan is de coëfficiënt 1.
ongelijkheid	Een bewering die de grootte van twee waarden vergelijkt, zoals \(t \geq 0\). Je gebruikt het om te beperken tot de positieve geheeltallige oplossingen.

Handig om vooraf te weten

Dit helpt je om de berekening op deze pagina echt te begrijpen, en niet alleen op de knop te drukken.
Kom je er niet uit, dan is het terugkeren naar deze onderwerpen de snelste weg vooruit.

Delen met rest (groep 5-8, 8-12 jaar)	Weten dat \(13 \div 5\) “quotiënt \(2\), rest \(3\)” is, en dit kunnen herschrijven als één vergelijking, \(13 = 5 \times 2 + 3\) Weten dat de rest altijd kleiner is dan de deler (minstens \(0\) en kleiner dan de deler)
Delers, veelvouden en de ggd (klas 1, 12-13 jaar)	“\(6\) is een veelvoud van \(3\)” en “\(3\) is een deler van \(6\)” in elkaar kunnen omzetten Kunnen vinden dat de grootste gemene deler van \(12\) en \(18\) gelijk is aan \(6\) (ontbinden in priemfactoren mag ook) Weten dat twee getallen met ggd \(1\) “relatief priem” heten
Termen en lineaire vergelijkingen (klas 1-2, 12-14 jaar)	Weten dat in een uitdrukking als \(ax + by\) \(a\) en \(b\) coëfficiënten zijn en \(x\) en \(y\) onbekenden Een vergelijking als \(3 \times 2 + 5y = 1\) kunnen oplossen voor \(y\) Een gemeenschappelijk getal kunnen buiten haakjes halen, zoals in \(4x + 6y = 2(2x + 3y)\)
Lineaire vergelijkingen met twee variabelen en hun grafieken (klas 2-3, 13-15 jaar)	Weten dat \(ax + by = c\) een rechte lijn in het coördinatenvlak is Weten dat er met twee onbekenden en maar één vergelijking niet één antwoord is, en dat elk punt op de lijn een oplossing is
Ongelijkheden (klas 2-3, 13-15 jaar)	Kunnen herschrijven van \(5t \geq 1\) naar \(t \geq \dfrac{1}{5}\) Weten dat delen van beide kanten door een negatief getal de richting van de ongelijkheid omdraait Weten dat als \(t \leq \dfrac{5}{3}\) en \(t\) een geheel getal is, je dit kunt aanscherpen tot \(t \leq 1\)
Rekenen met breuken (groep 6-8, 9-12 jaar)	Een breuk als \(\dfrac{80}{10} = 8\) kunnen vereenvoudigen Negatieve breuken zoals \(-\dfrac{3}{8}\) op een getallenlijn kunnen vergelijken

Berekenen met Excel

Kopieer de hele tabel hieronder en plak die in cel A1 van Excel. Het werkt direct.

Tabel om te controleren of er geheeltallige oplossingen zijn

Coëfficiënt a van x	50
Coëfficiënt b van y	80
Constante c rechts	1000
Ggd g	=GGD(B1;B2)
Rest van c ÷ g	=REST(B3;B4)
Geheeltallige oplossingen?	=ALS(B5=0;"Er zijn oplossingen";"Geen oplossingen")

Tabel om de identiteit van Bézout te controleren

Coëfficiënt a van x	50
Coëfficiënt b van y	80
x1 uit het algoritme van Euclides	-3
y1 uit het algoritme van Euclides	2
a×x1 + b×y1	=B1B3+B2B4
Ggd g	=GGD(B1;B2)

Tabel om oplossingen uit de algemene oplossing te halen

Coëfficiënt a van x	50
Coëfficiënt b van y	80
Constante c rechts	1000
Ggd g	=GGD(B1;B2)
Particuliere oplossing x0	4
Particuliere oplossing y0	10
Geheel getal t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Controle a×x + b×y	=B1B8+B2B9

Tabel om te beperken tot positieve geheeltallige oplossingen

Coëfficiënt a van x	50
Coëfficiënt b van y	80
Ggd g	=GGD(B1;B2)
Particuliere oplossing x0	4
Particuliere oplossing y0	10
Ondergrens van t (uit x ≥ 1)	=-INTEGER((B4-1)/(B2/B3))
Bovengrens van t (uit y ≥ 1)	=INTEGER((B5-1)/(B1/B3))
Aantal positieve geheeltallige oplossingen	=MAX(0;B7-B6+1)

Na het plakken zijn de bovenste rijen (de coëfficiënten en de particuliere oplossing) de invoer en worden de onderste rijen automatisch berekend. GGD geeft de grootste gemene deler, REST geeft de rest van een deling en INTEGER laat het deel achter de komma weg (naar beneden afronden).
De eerste tabel gebruikt het voorbeeld 50x + 80y = 1000. De ggd is 10 en 1000 ÷ 10 geeft rest 0, dus er staat “Er zijn oplossingen”. Verander 1000 in 1001 en het wordt “Geen oplossingen”.
De tweede tabel controleert dat x1 = −3 en y1 = 2, gevonden door het algoritme van Euclides terug te lopen, echt voldoen aan de identiteit van Bézout. 50×(−3) + 80×2 = 10, en dat komt overeen met de ggd.
De derde tabel haalt één oplossing uit de algemene oplossing. Vul 1 in voor t en je krijgt x = 12 en y = 5, en de controlerij komt weer uit op 1000. Probeer ook andere gehele getallen voor t.
De vierde tabel beperkt tot de positieve geheeltallige oplossingen. De ondergrens van t is 0 en de bovengrens is 1, dus er zijn 2 positieve geheeltallige oplossingen (t = 0 en t = 1). Deze twee formules zijn voor het geval dat a en b allebei positief zijn. Bij een negatieve coëfficiënt draait de richting van de ongelijkheid om, dus pas op.

Berekenen met Google Spreadsheets

Kopieer de hele tabel hieronder en plak die in cel A1 van Google Spreadsheets. Het werkt direct.

Tabel om te controleren of er geheeltallige oplossingen zijn

Coëfficiënt a van x	50
Coëfficiënt b van y	80
Constante c rechts	1000
Ggd g	=GGD(B1;B2)
Rest van c ÷ g	=REST(B3;B4)
Geheeltallige oplossingen?	=ALS(B5=0;"Er zijn oplossingen";"Geen oplossingen")

Tabel om de identiteit van Bézout te controleren

Coëfficiënt a van x	50
Coëfficiënt b van y	80
x1 uit het algoritme van Euclides	-3
y1 uit het algoritme van Euclides	2
a×x1 + b×y1	=B1B3+B2B4
Ggd g	=GGD(B1;B2)

Tabel om oplossingen uit de algemene oplossing te halen

Coëfficiënt a van x	50
Coëfficiënt b van y	80
Constante c rechts	1000
Ggd g	=GGD(B1;B2)
Particuliere oplossing x0	4
Particuliere oplossing y0	10
Geheel getal t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Controle a×x + b×y	=B1B8+B2B9

Tabel om te beperken tot positieve geheeltallige oplossingen

Coëfficiënt a van x	50
Coëfficiënt b van y	80
Ggd g	=GGD(B1;B2)
Particuliere oplossing x0	4
Particuliere oplossing y0	10
Ondergrens van t (uit x ≥ 1)	=-INTEGER((B4-1)/(B2/B3))
Bovengrens van t (uit y ≥ 1)	=INTEGER((B5-1)/(B1/B3))
Aantal positieve geheeltallige oplossingen	=MAX(0;B7-B6+1)

Dezelfde formules als in Excel werken ook hier (GGD, REST, INTEGER, MAX en ALS hebben in de Nederlandse versie dezelfde namen en doen hetzelfde). Kopieer de hele tabel, plak die in cel A1 en vervang de coëfficiënten door je eigen getallen.

Berekenen met Python

from math import gcd

# coëfficiënten van ax + by = c (gehele getallen)
a, b, c = 50, 80, 1000

def extended_gcd(x, y):
    # uitgebreid algoritme van Euclides: geeft gcd en s, t met x*s + y*t = gcd
    if y == 0:
        return x, 1, 0
    g, s, t = extended_gcd(y, x % y)
    return g, t, s - (x // y) * t

g = gcd(a, b)
if c % g != 0:
    print(f"{c} is geen veelvoud van {g}, dus er zijn geen geheeltallige oplossingen")
else:
    _, s, t = extended_gcd(a, b)
    x0, y0 = s * (c // g), t * (c // g)   # particuliere oplossing (één geheeltallige oplossing)
    step_x, step_y = b // g, a // g       # stapgrootte van x en stapgrootte van y
    # verschuif tot x de kleinste waarde is die 0 of meer is, voor een makkelijker te lezen oplossing
    n = x0 // step_x
    x0, y0 = x0 - n * step_x, y0 + n * step_y
    print(f"Particuliere oplossing: (x, y) = ({x0}, {y0})")
    print(f"Algemene oplossing: x = {x0} + {step_x}t, y = {y0} - {step_y}t (t is een geheel getal)")
    for k in range(-2, 3):
        print(f"  t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
    # bewaar alleen de positieve geheeltallige oplossingen (x >= 1 en y >= 1)
    t_low = -((1 - x0) // -step_x)
    t_high = (y0 - 1) // step_y
    print("Positieve geheeltallige oplossingen:", [(x0 + step_x * k, y0 - step_y * k)
                                        for k in range(t_low, t_high + 1)])

Je hebt alleen math.gcd uit de standaardbibliotheek nodig en een recursief uitgebreid algoritme van Euclides. Dit voorbeeld is 50x + 80y = 1000. Uitvoeren toont de particuliere oplossing (4, 10), de algemene oplossing x = 4 + 8t, y = 10 − 5t en de positieve geheeltallige oplossingen [(4, 10), (12, 5)]. Verander de coëfficiënten en probeer het (het laatste deel, voor positieve geheeltallige oplossingen, is geschreven voor het geval dat a en b allebei positief zijn).

De formule in LaTeX en andere wiskundenotaties (om te kopiëren)

Wanneer er geheeltallige oplossingen zijn

c = gcd(a, b) × m

c = \gcd(a, b) \times m

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>c</mi>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>m</mi>
  </mrow>
</math>

c = gcd(a, b) * m

Mod[c, GCD[a, b]] == 0

irem(c, igcd(a, b)) = 0;

mod(c, gcd(a, b)) == 0

c = gcd(a,b) × m

Identiteit van Bézout (één paar gehele getallen uit het algoritme van Euclides)

a·x₁ + b·y₁ = gcd(a, b)

a x_1 + b y_1 = \gcd(a, b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
    <mo>+</mo>
    <mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
  </mrow>
</math>

a*x_1 + b*y_1 = gcd(a, b)

ExtendedGCD[a, b]

igcdex(a, b, x1, y1);

[g, x1, y1] = gcd(a, b);

a x_1 + b y_1 = gcd(a,b)

Alle geheeltallige oplossingen (algemene oplossing)

x = x₀ + (b/g)t, y = y₀ − (a/g)t

x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>,</mo><mspace width="1em"/>
    <mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
  </mrow>
</math>

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Solve[a x + b y == c, {x, y}, Integers]

isolve(a*x + b*y = c);

S = solve(a*x + b*y == c, [x y], 'Integer', true);

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Beperken tot positieve geheeltallige oplossingen

x₀ + (b/g)t ≥ 1 en y₀ − (a/g)t ≥ 1

x_0 + \frac{b}{g} t \geq 1, \quad y_0 - \frac{a}{g} t \geq 1

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
    <mo>,</mo><mspace width="1em"/>
    <msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
  </mrow>
</math>

x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1

Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]

isolve({a*x + b*y = c, x >= 1, y >= 1});

S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);

x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1

Zo laat je ChatGPT de berekening doen

Je bent een rekenassistent voor getaltheorie (eigenschappen van gehele getallen). Voer de volgende berekening uit door daadwerkelijk Python-code uit te voeren en baseer je antwoord alleen op de getallen uit het resultaat van de uitvoering (geef geen antwoord op basis van hoofdrekenen of gokken).

Bepaal de gehele oplossingen van de lineaire diofantische vergelijking 50x + 80y = 1000.
Laat elk van de volgende zien:
1. De grootste gemene deler van 50 en 80, en of 1000 daar een veelvoud van is
2. De stappen van het algoritme van Euclides (tot de rest 0 is), en de x1, y1 met 50×x1 + 80×y1 = ggd, gevonden door terug te werken
3. Een particuliere oplossing (x0, y0) en de algemene oplossing x = x0 + (b/g)t, y = y0 − (a/g)t
4. Alle gehele oplossingen waarbij zowel x als y 1 of meer is

Gebruik in Python math.gcd en het uitgebreide algoritme van Euclides om exact te rekenen, en laat de formules zien die je hebt gebruikt en de getallen uit het resultaat van de uitvoering.

Zo werkt het

1

Vul je getallen in

Typ de getallen waarmee je wilt rekenen in de invoervelden
2

Bereken

Klik op de knop “Berekenen”
3

Bekijk het resultaat

Het resultaat verschijnt meteen. Op dezelfde pagina vind je ook de uitwerking van de berekening en de uitleg van de formule