Tag archieven: diophantische vergelijkingen

Les 5: Diophantische vergelijkingen en modulo rekenen

Geplaatst op door

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 door

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 2: ax+by+cz=d

Geplaatst op door

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.

Het twee kannen probleem

Geplaatst op door

In dit  artikel bespreken we problemen waarin men beschikt over 2 lege kannen, zonder maatstreepjes. Verder is er een kraan waarmee men de kannen kan vullen en een gootsteen waarin men de kannen kan leeggieten. We aanvaarden volgende handelingen : Een kan volledig leeggieten, een kan helemaal vullen met de kraan, water van de ene kan overhevelen in de andere kan totdat de ene helemaal leeg is of de andere helemaal vol. Je vindt ook een Python programma om het probleem op te lossen

Rationale getallen

Geplaatst op door

Is het juist dat, indien x^7 en x^{12} rationaal zijn, x eveneens rationaal is?

We weten dat de vermenigvuldiging en de delig door een getal, verschillend van 0, inwendige bewerkingen zijn in \mathbb{Q}.  Dus als x^{12} en x^7 rationaal zijn, dan is hun quotiënt x^5 dat ook . Maar dan is het quotiënt van x^7 en x^5, en dat is x^2, ook een rationaal getal. Als x^2 rationaal is, dan ook (x^2)^3=x^6. Tenslotte volgt uit het feit dat x^6 en x^5 allebei rationaal zijn dat hun quotiënt x dat ook is.Het antwoord op de gestelde vraag is dus bevestigend.

We kunnen dit ook anders oplossen: We zoeken eigenlijk twee getallen a en b zodat (x^{12})^a:(x^7)^b=x, waarbij a en b gehele getallen zijn. Maar dan moet

    \[12a-7b=1\]

Dit is een Diophantische vergelijking en omdat de grootste gemene deler van 12 en 7 gelijk is aan 1, heeft deze vergelijking oneindig veel oplossingen. De meest eenvoudige is a=3 en b=5. Dit geeft ons in één keer ook de mogelijkheid het probleem te veralgemenen. Als we in de opgave werken met bijvoorbeeld x^9 en x^{12}, dan klopt het niet meer: de Diophantische vergelijking 12a-9b=1 heeft immers geen oplossingen omdat de grootste gemene deler van a en b gelijk is aan 3.