diophantische vergelijking ax+by = 1

Matrixrekenen, vectorruimten, groep-en ringstructuren, (lineaire) tranformaties.
Plaats reactie
ikweethetniet
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 24 dec 2014, 22:32

diophantische vergelijking ax+by = 1

Bericht door ikweethetniet » 24 dec 2014, 22:53

Hallo allemaal,

Voor een bewijs wil ik deze stelling gebruiken, het stond als hint, maar ik weet niet hoe ik hem kan bewijzen.

Als gehele getallen x en y copriem zijn, bestaan er gehele getallen a en b zodat ax + by = 1

Ik heb op internet gezocht, kwam erop dat dit de Bézout's Identity heette. Maar ik kon geen duidelijk bewijs vinden. Kunnen jullie me hierbij helpen?

Alvast bedankt :)

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: diophantische vergelijking ax+by = 1

Bericht door arie » 25 dec 2014, 11:02

Zie http://nl.wikipedia.org/wiki/Stelling_v ... %C3%A9zout
Er bestaan meerdere bewijzen, bijvoorbeeld:

Definieer c als kleinst positieve getal van alle lineaire combinaties van x en y.
Dus:
We kijken naar de verzameling van alle lineaire combinaties mx + ny
van x en y (waarbij m en n alle mogelijke gehele getallen mogen zijn).
In die verzameling moet er 1 de kleinst positieve zijn, noem die c.
Merk op: er bestaan dan dus gehele u en v zodanig dat
c = ux + vy

Kijk nu naar alle lineaire combinaties van x en y:
z = mx + ny

Volgens deling met rest (= het delingsalgoritme) bestaan er dan
gehele q en r
waarbij 0 <= r < c
zodanig dat
z = qc + r

Maar dan is
r = z - qc
= mx + ny - q(ux + vy)
= (m - qu)x + (n - qv)y

Dus r is een lineaire combinatie van x en y EN 0 <= r < c.
Maar omdat c de kleinst positieve lineaire combinatie van x en y is, moet r = 0 zijn.
Dus z = qc + r = qc + 0 = qc
ofwel:
Elke lineaire combinatie van x en y is een veelvoud van c.
Dus ook x (= 1*x + 0*y) en y (= 0*x + 1*y) zijn veelvouden van c.
ofwel:
c is een deler van x en
c is een deler van y,
maar dan is c ook een deler van d = ggd(x, y) = de grootst gemene deler van x en y.
Dus c <= d. [1]

Omdat d = ggd(x, y) een deler is van x EN d een deler is van y,
is d ook een deler van ux + vy = c
Dus d <= c. [2]

Uit [1] en [2] volgt: d = c
ofwel:
Er zijn een gehele u en v zodanig dat
d = ggd(x, y) = ux + vy.

Gebruik dit resultaat om jouw stelling te bewijzen.

ikweethetniet
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 24 dec 2014, 22:32

Re: diophantische vergelijking ax+by = 1

Bericht door ikweethetniet » 25 dec 2014, 15:44

Bedankt, ik snap hem :D

Plaats reactie