[wiskunde] diophantische vergelijkingen: ax+by=c

Krypton

Hej!

Voor mijn eindwerk wiskunde ga ik oa de diophantische vgl ax+by=c bespreken. hiervoor heb ik info op het internet gevonden, en mijn bewijs leidt tot dit:

Stelling: De diophantische vergelijking van ax+by=c heeft alleen maar uitkomsten als c een veelvoud is van de grootst gemene deler van a en b. (maw: c moet een lineaire combinatie zijn van a en b)

Om dit te bewijzen gaan we eerst het uitgebreid euclidisch algoritme bekijken aan de hand van een voorbeeld. Het uitgebreid euclidisch algoritme is een uitbreiding van het euclidisch algoritme met als voordeel dat men behalve de ggd van x en y ook de getallen a en b kan bepalen zodat ax+by=c.

Gegeven: de getallen 15 en 8 ( allebei elementen van N)

Gevraagd: zoek de ggd (grootst gemene deler)

Oplossing:

1. We schrijven 15 en als lineaire combinaties van zichzelf.

15= 1.15 0.8

8= 0.15 + 1.8

2. We voeren de deling uit.

15=1.15 0.8

8= 0.15 + 1.8

7= 1.15 1.8

1= -1.15 + 2.8

0= 8.15 15.8

3. We zien de ggd van de lineaire combinatie van 15 en 8, nl.1.

De voorlaatste stap is namelijk de laatste stap waarin de vergelijking van de vorm ax + by = c is. De getallen a en b zijn dan -1 en 2, die inderdaad lineaire combinaties zijn van 1.

Nu we hebben bewezen dat c een lineaire combinatie moet zijn van a en b, kunnen we de uitkomsten zoeken van deze vergelijking.

Gegeven: ax+by=c met a,b,c elementen van Z en c=k.ggd(a,b)

Stel dat we een uitkomst weten van deze vergelijking. Bijvoorbeeld x = x1 en

y = y1.

Bekijk nu voor elke gehele waarde van t: x = x1 + bt en y= y1 at:

ax+by= a(x1 + bt ) + b(y1 at) (substitutie)

= ax1 + abt +y1b abt

= ax1 + y1b

= c

Hieruit leidt je af dat x = x1 + bt en y= y1 at oplossingen zijn de vergelijking.

Stel je weet nog een tweede oplossing van de vergelijking: x=x2 en y=y2.

Dan:

ax1 + by1=c

en ax2+by2=c

zodat

ax1 + by1 = ax2+by2

Û ax2 + by2 - ax1 - by1 = 0

Û a (x2 x1 ) + b (y2 y1) = 0

Û a (x2 x1 ) = b (y1 y2)

Er is dus een t met bt= x2 x1 en at= y1 y2.

De oplossing voor deze vergelijking is dus ook : x = x1 + bt en y = y1 at .

Zowel voor een eerste uitkomst als voor een tweede uitkomst is de oplossing hetzelfde, dus de vorm van de oplossing is juist.

maar als ik dit wil toepassen op het potenprobleem (In een doos zitten kevers en spinnen. In totaal zijn er 78 poten. hoeveel kevers, hoeveel spinnen?) kom ik niets zinnig uit. Er klopt met andere woorden iets niet aan mijn bewijs, want op het internet staat onder de 't' nog (ggd (a,b)). én de parameter 't' in mijn bewijs is eigenlijk (y-y)/a en dus niet gewoon een element van R. Maar zo stond het in een bestaand bewijs. Hoe moet ik aan een juiste uitkomst van mijn potenprobleem komen zonder kettingbreuken te gebruiken?

(alvast bedankt)

Jan van de Velde

Dag Krypton, welkom op het forum Huiswerk en Practica.

Jij wilt vlot hulp. Dat is alleen goed mogelijk als je daar zelf wat voor doet.

Naast de algemene regels van dit forum hebben we voor dit huiswerkforum een paar speciale regels en tips.

Die vind je in de huiswerkbijsluiter

In die huiswerkbijsluiter staat bijvoorbeeld:

Quote[td] [color="#808080"][b][u]VAKGEBIED-TAGS[/u][/b] [i]Plaats het vakgebied waarop je vraag betrekking heeft tussen rechte haken in de titel. bijv: [biologie] of [frans]. Zo blijft dit huiswerkforum overzichtelijk.[/i] [/color] [/td]

Hebben we even voor je gedaan. Denk je er de volgende keer zélf aan??

[/color]

Krypton

Sorry. Ik geef toe dat ik snel over de regels heb gelezen.

Maar over mijn potenprobleem had ik wel diep nagedacht.

Mijn resultaat was dan ook:

In een doos zitten kevers en spinnen. In totaal zijn er 78 poten.

Vraag: Hoeveel kevers en hoeveel spinnen zijn er?

Oplossing: aangezien men geen halve poten kan hebben, is de oplossing van Diophantische aard.

De vergelijking is van de vorm 6x+8y=78.

Een eerste oplossing is (door gokken): x= 9 en y=3

=> x= 9.78+8.t y=3.78-6t.

Voor t=1: x=17 en y= -3. => negatieve oplossingen kunnen niet in dit geval.

Voor t= ½: x=13 en y=0. => zou kunnen maar in de opgave staat dat er kevers én spinnen zijn.

Voor t= -1: x=1 en y=9

Voor t= -½: x=5 en y=6.

maar eigenlijk komt dit dus ook op gokken neer. Maar het is wel een toepassing van de theorie.

Dus ik vat het niet meer.

mathfreak

Merk om te beginnen op dat 6x+8y=78 te vereenvoudigen is tot 3x+4y=39. Merk verder op dat x=1 en y=9 een oplossing is. Beschouw nu de vergelijking 3x+4y=0. Deze heeft de algemene oplossing x=-4t en y=3t. Laat nu zien dat x=1-4t en y=9+3t een algemene oplossing is van 3x+4y=39. Ik neem aan dat je er zo verder wel uitkomt.

Krypton

Merk om te beginnen op dat 6x+8y=78 te vereenvoudigen is tot 3x+4y=39. Merk verder op dat x=1 en y=9 een oplossing is. Beschouw nu de vergelijking 3x+4y=0. Deze heeft de algemene oplossing x=-4t en y=3t. Laat nu zien dat x=1-4t en y=9+3t een algemene oplossing is van 3x+4y=39. Ik neem aan dat je er zo verder wel uitkomt.

bedankt! dat heeft me enorm veel vooruit geholpen.

Volgens de formule is het wel x=1+4t en y=9-3t, maar dat komt op hetzelfde neer.

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[wiskunde] diophantische vergelijkingen: ax+by=c

[wiskunde] diophantische vergelijkingen: ax+by=c

Re: [wiskunde] diophantische vergelijkingen: ax+by=c

Re: [wiskunde] diophantische vergelijkingen: ax+by=c

Re: [wiskunde] diophantische vergelijkingen: ax+by=c

Re: [wiskunde] diophantische vergelijkingen: ax+by=c