<<< G13. DIOFANT1.83P  
Dipophantische vergelijkingen betreffen uitsluitend gehele getallen (en gehele oplossingen).
Hier wordt de eerstegraads Diophantische vergelijking ax+by=c opgelost (als er oplossingen zijn tenminste).
Gaat de lijn ax+by=c door roosterpunten (x,y)? Zoja, door welke roosterpunten?
Voor de beantwoording van die vraag moet je weten wat een Grootste Gemene Deler (GGD of gcd) is van twee getallen. Het woord zegt het al: bekijk alle gelijke (gemeenschappelijke) delers van die twee getallen; de grootste daarvan is de GGD. Zo is 20 de GGD van 40 en 60.
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.
Een van die oplossingen vind je met het Euclidische algoritme, een recursief patroon waarbij
gcd(a, b-a*iPart(b/a)) de volgende waarden van a en b levert.
De lijn 13x+17y=55 gaat bijv. door (220,-165) en ook (-1,4) [voor N= -13]