Les 5: Diophantische vergelijkingen en modulo rekenen

Geplaatst op 21 februari 2024 door admin

Als twee gehele getallen gelijk zijn, dan zijn hun resten bij deling door een zelfde natuurlijk getal, verschillend van nul, ook gelijk. Of via contrapositie: als er tenminste 1 natuurlijk getal n bestaat waarvoor $a \neq b \mod n$ , dan zal ook a verschillend zijn van b.

Proberen we eens met

$2x^2-3y^2-9463=0$

Herschrijf tot $2x^2-3y^2=9463$ .
We bepalen de resten van beide leden bij deling door 3: $2x^2-3y^2\equiv 9463 \mod 3$ .
Of $2x^2\equiv 1 \mod 3$ .
Het inverse element, modulo 3, van 2 is 2 zelf, dus kunnen we vorige vergelijking herschrijven als
$x^2\equiv 2 \mod 3$
Nu is 2 geen kwadraatrest modulo 3, want $0^2=0,1^2=1$ en $2^2=1$ .
Bijgevolg heeft de gegeven vergelijking geen oplossingen.

Les 4: ontbinding en exhaustie

Geplaatst op 16 februari 2024 door admin

Bij Diophantische vergelijkingen van een hogere graad kan je via ontbinding in factoren dikwijls de oplossing vinden. Neem bijvoorbeeld:

$3x^2-4xy+5=0$

We kunnen deze vergelijking herschrijven als
$x(3x-4y)=-5$
Als x en y gehele getallen zijn, dan moeten x en $3x-4y$ delers zijn van $-5$ .
We kunnen gemakkelijk alle mogelijkheden opschrijven:
$\begin{array}{c|c|c} x&3x-4y&y \\ \hline \\1&-5&2\\-1&5&-2\\5&-1&4\\-5&1&-4\end{array}$
We hebben dus als oplossingen $(1,2),(-1,-2),(5,4),(-5,-4)$ .

Les 3: Stelsels Diophantische vergelijkingen

Geplaatst op 10 februari 2024 door admin

We lossen één van de vergelijkingen op en vullend die dan in de andere in, waardoor er een verband ontstaat tussen de parameters. Neem bijvoorbeeld:

$\left\{\begin{matrix} 3x-6y+16z=1\\2x+5y-6z=2\end{matrix}\right$

Uit les 2 weten we dat de oplossing van de eerste vergelijking gegeven wordt door $x=5+16t+2v, y=5+16t+v, z=1+3t$ .
Invullen in de tweede vergelijking geeft: $2(5+16t+2v)+5(5+16t+v)-6(1+3t)=2$ . Na uitwerking vinden we $94t+9v=-27$ .
Dit is een Diophantische vergelijking met slechts twee onbekenden. De oplossingen hangen af van 1 parameter w: $t=54-9w$ en $v=-567+94w$ .
Brengen we deze waarden in bij de oplossingen van de eerste vergelijking van het stelsel, dan vinden we :
$\left\{\begin{matrix}x=-265+44w\\y=302-50w\\z=163-27w\end{matrix}\right$

Les 2: ax+by+cz=d

Geplaatst op 2 februari 2024 door admin

Omdat ggd(a,b,c) = ggd( ggd(a,b),c) kunnen we recursief werken. Neem als voorbeeld de vergelijking

$3x-6y+16z=1$

Herschrijf deze vergelijking als $3(x-2y)+16z=1$ .
Stel $x-2y=u$ , dan wordt de gegeven vergelijking $3u+16z=1$ .
Gebruikmakend van de techniek uit les 1 vinden we dat $u=-5-16t$ en $z=1+3t$ , met t een willekeurig geheel getal.
Met dezelfde methode kunnen we via $x-2y=1$ , de oplossing van $x-2y=u$ schrijven als $x=-u+2v$ en $y=-u+v$ met v een geheel getal.
Na eliminatie van u vinden we dus dat $x=5+16t+2v$ , $y=5+16t+v$ en $z=13t$ . Dit zijn alle gehele oplossingen van de gegeven vergelijking. Deze hangen af van 2 parameters.

Les 1: ax+by=c

Geplaatst op 28 januari 2024 door admin

Aan de hand van enkele voorbeelden bespreken we Diophantische vergelijkingen: dit zijn vergelijkingen met gehele coëfficiënten waarvan gehele oplossingen gevraagd worden.

We starten in les 1 met de basisvergelijking $ax+by=c$ met $a,b,c :in \mathbb{Z}$ . Neem bijvoorbeeld $7x+13y=81$ .

Omdat de grootste gemene deler van 7 en 13 gelijk is aan 1 en dit een deler is van 81, heeft deze vergelijking oplossingen.
Volgens de stelling van Bezout kunnen we deze grootste gemene deler schrijven als een lineaire combinatie van 7 en 13. Dat kan door het recursief gebruiken van het algoritme van Euclides voor het bepalen van de grootste gemene deler.
Zo is $7.2+13.(-1)=1$ en dus is $7.162+13.(-81)=81$ . Bijgevolg is $(162,-81)$ een particuliere oplossing van de gegeven vergelijking.
Als we nu de twee vergelijkingen $7.162+13.(-81)=81$ en $7x+13y=81$ van elkaar aftrekken vinden we $7(162-x)=13(81+y)$ . Bijgevolg is 7 een deler van $81+y$ en 13 een deler van $162-x$ .
Er bestaat dus een geheel getal t zodat
$\frac{162-x}{13}=\frac{81+t}{7}=t$
en dus is $x=162-13t$ en $y=-81+7t$ . Alle gehele oplossingen van de gegeven vergelijking zijn van deze vorm.