De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Oplossingen voor Diophantische eerstegraads vergelijkingen

Is er een algemene manier om oplossing(en) te vinden voor een vergelijking met 2 getallen met ggd = 1 b.v. :
666x + 2003y = 1
of moet je gewoon proberen ?

s. Lip
Student universiteit - dinsdag 28 september 2004

Antwoord

De Diophantische eerstegraads vergelijking ax+by=c heeft gehele oplossingen voor x en y, als c een veelvoud is van de Grootste Gemene Deler van a en b: c/gcd(a,b) moet een geheel getal zijn. De oplossing is van de vorm:
x = X0 + k.b /gcd(a,b)
y = Y0 + k.a /gcd(a,b) met k

De oplossingen vind je met het Euclidische algoritme, een recursief algortime waarbij
gcd(a, b-a*iPart(b/a)) de volgende waarden van a en b levert.

Voorbeeld met 13 x + 43 y = 1:
iPart(b/a) = 3
gcd(a, b-a*iPart(b/a))= 4
Dit is te schrijven als
13 (x + 3y) + 4 y = 1.

Met x1 = x + 3y wordt dit: 13 x1 + 4 y = 1.

Nogmaals toepassen van het algoritme levert.
x1 + 4(y+ 3x1)= 1.
Met y1=y+3x1 wordt dit: x1 + 4y1 = 1.

Alle oplossingen van x1 + 4y1 = 1 zijn:
y1= k,
x1 = 1 4k met k .
Terugwerken naar x en y:
y = y1 3x1 geeft: y = k -3 (1-4k) = k-3 + 12 k= -3 + 13k
en
x = x1 3y geeft: x = 1 4k 3(13 k-3) =1-4k-39k+9 =10 -43k

Totale oplossing is:
x = 10 - 43k
y = -3 + 13k met k

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 28 september 2004


klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2018 WisFaq - versie IIb