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
diophantische vergelijking ax+by = 1
-
- Nieuw lid
- Berichten: 2
- Lid geworden op: 24 dec 2014, 22:32
Re: diophantische vergelijking ax+by = 1
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.
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.
-
- Nieuw lid
- Berichten: 2
- Lid geworden op: 24 dec 2014, 22:32
Re: diophantische vergelijking ax+by = 1
Bedankt, ik snap hem