diophantische vergelijkingen


Diophantische Vergelijkingen.	© h.hofstede (h.hofstede@hogeland.nl)

Diophantische vergelijkingen zien er uit als: ax + by = c en dan zijn we ook nog alleen geïnteresseerd in de gehele oplossingen voor x en y.

Zo'n Diophantische vergelijking heeft alleen een oplossing als GGD(a, b) een deler is van c.
Toon dat zelf maar aan.

Het oplossen van zo'n Diophantische vergelijking gaat in drie stappen.

Stap 1: ax + by = GGD(a,b)

Deze vergelijkingen hebben we al uitgebreid besproken aan het eind van de les over het Euclidisch algoritme.
Neem die les eerst door als je er niets van weet. Voor wie het nog wél ongeveer weet is hier nog een geheugenopfrissertje.

Voorbeeld: Los op: 178x + 312y = GGD(178, 312)

Die GGD vond je als volgt:

312 = 1 • 178 + 134
178 = 1 • 134 + 44
134 = 3 • 44 + 2
44 = 22 • 2 + 0 dus GGD is gelijk aan 2.

Draai de zaak om en je krijgt een oplossing van de vergelijking:

2 = 134 - 3 • 44
2 = 134 - 3 • (178 - 1 • 134) = 4 • 134 - 3 • 178
2 = 4 • (312 - 1 • 178) - 3 • 178 = 4 • 312 - 7 • 178
Dus met x = -7 en y = 4 is dat een oplossing van 178x + 312y = 2

STAP 2: ax + by = c

Als er niet GGD(a, b) staat maar een ander getal c, dan is er alleen een oplossing te vinden als je c kunt krijgen door een aantal maal de GGD(a, b) te doen. Die GGD moet dus een deler van c zijn!
Als dat kan, dan heb je ook meteen de oplossing gevonden: vermenigvuldig gewoon de hele vergelijking van stap 1 met ^c/_GGD.

Voorbeeld:
Los op: 178x + 312y = 14.
De oplossing in stap 1 was -7 • 178 + 4 • 312 = 2
Omdat de GGD (2) een deler is van 14 doen we gewoon alles keer 7: -49 • 178 + 28 • 312 = 14
Dus x = -49 en y = 28 is een oplossing.

Voorbeeld:
Los op: 178x + 312y = 15.
Nu is er geen oplossing omdat 15 niet deelbaar is door 2.
(dat kon je ook meteen zien: de rechterkant is altijd even en de linkerkant altijd oneven)

Het bewijs, dat er dan niet zo'n oplossing is, is erg eenvoudig; het zelfs wel in één zin, kijk maar:

"ax is deelbaar door GGD(a,b) en bx is ook deelbaar door GGD(a,b) dus de rechterkant van de vergelijking is deelbaar door GGD(a,b) dus moet de linkerkant dat ook zijn"
q.e.d.

STAP 3: Meerdere oplossingen.

In stap 1 en stap 2 vond je één oplossing (tenminste als die bestaat) van de gegeven vergelijking. (Mogelijke) andere oplossingen zijn te vinden via de volgende stelling:

Als x₀ en y₀ een oplossing is van de vergelijking ax + by = c,
dan is (x₀ + kb) en (y₀ - ka) voor elke gehele k ook een oplossing.

Een één-regel-bewijsje maar weer?
a(x₀ + kb) + b(y₀ - ka) = ax₀ + akb + by₀ - bka = ax₀ + by₀ = c   q.e.d.

Dat geeft dus oneindig veel oplossingen.

Toegift: Oplossingen onder een voorwaarde.

Stel dat we willen oplossen:   19x + 99y = 1999 met als voorwaarde dat x en y positief moeten zijn.
stap 1:   GGD(19, 99) = 1 en dat is een deler van 1999. Euclidisch algoritme geeft -26 • 19 + 5 • 99 = 1 (ga zelf na)
stap 2:   vermenigvuldigen met 1999 geeft dan: -51974 • 19 + 9995 • 99 = 1999
stap 3:   een algemene oplossing is nu x = -51974 + 99k en y = 9995 - 19k

x > 0 geeft -51974 + 99k > 0 ofwel k > 524,98....
y > 0 geeft 9995 - 19k > 0 ofwel k < 526,05...

Er zijn dus twee gehele oplossingen voor k:
k = 525 geeft   x = 1 en y = 20
k = 526 geeft   x = 100 en y = 1

Dat zijn de enige twee gehele positieve oplossingen van de gegeven vergelijking.

OPGAVEN

Los de volgende vergelijkingen op, geef alle oplossingen waarvoor x en y positieve gehele getallen zijn.

6x + 5y = 171

(26,3)(21,9)(16,15)
(11,21)(6,27)(1,33)

37x + 20y = 1209

(17,29)

87x - 64y = 3

(53,72)(117,159)...

Op hoeveel verschillende manieren kun je een totaalbedrag van 81 cent op een brief plakken als je postzegels van 4 cent en van 7 cent hebt?

3 manieren

Drie vermoeide piraten hebben een stapel kokosnoten veroverd. Ze besluiten eerst te gaan slapen en de stapel de volgende ochtend te verdelen.
Eén van hen wordt echter midden in de nacht wakker, geeft één kokosnoot aan een aap, begraaft een derde deel van de overgebleven kokosnoten, en gaat weer slapen.
Daarna wordt piraat 2 wakker, en die doet precies hetzelfde (één kokosnoot voor de aap, een derde deel begraven)

De derde piraat wordt pas wakker als het ochtend is, geeft één kokosnoot aan de aap en verdeelt de rest in drie gelijke stapels.

Hoeveel kokosnoten kunnen er in de oorspronkelijke stapel hebben gezeten?

Leg uit waarom dit probleem is terug te brengen tot de vergelijking 4x - 27y = 19

Wat is het minimale oorspronkelijke aantal kokosnoten?

Iemand wil voor precies €100,- in een kantoorboekhandel precies 20 voorwerpen gaan kopen.
Dat kunnen pennen zijn (€5,- per stuk) of kladblokken (€7,- per stuk) of elastieken (€2,- per stuk)
Op hoeveel verschillende manieren kan hij al zijn geld besteden?

5 manieren