Springen naar inhoud

[wiskunde] diophantische vergelijkingen: ax+by=c


  • Log in om te kunnen reageren

#1

Krypton

    Krypton


  • 0 - 25 berichten
  • 16 berichten
  • Gebruiker

Geplaatst op 05 mei 2009 - 20:01

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)

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Jan van de Velde

    Jan van de Velde


  • >5k berichten
  • 44858 berichten
  • Moderator

Geplaatst op 05 mei 2009 - 20:18

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

VAKGEBIED-TAGS
Plaats het vakgebied waarop je vraag betrekking heeft tussen rechte haken in de titel.
bijv: [biologie] of [frans]. Zo blijft dit huiswerkforum overzichtelijk.

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

ALS WIJ JE GEHOLPEN HEBBEN....
help ons dan eiwitten vouwen, en help mee ziekten als kanker en zo te bestrijden in de vrije tijd van je chip...
http://www.wetenscha...showtopic=59270

#3

Krypton

    Krypton


  • 0 - 25 berichten
  • 16 berichten
  • Gebruiker

Geplaatst op 05 mei 2009 - 21:36

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.

#4

mathfreak

    mathfreak


  • >1k berichten
  • 2460 berichten
  • Ervaren gebruiker

Geplaatst op 06 mei 2009 - 18:15

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.
"Mathematics is a gigantic intellectual construction, very difficult, if not impossible, to view in its entirety." Armand Borel

#5

Krypton

    Krypton


  • 0 - 25 berichten
  • 16 berichten
  • Gebruiker

Geplaatst op 07 mei 2009 - 19:48

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures