Het algoritme van Euclides toegepast op
en
verloopt als volgt:
We kunnen dit rekenwerk ook zo opschrijven:
Het resultaat is een zogeheten kettingbreuk.
7.43 Definitie. We definiëren de kettingbreuk
van een rijtje rationale (later: reële) getallen
met .
Het is een inductieve definitie.
De notatie
is dus in feite een verkorte schrijfwijze voor . Voor
getallen
met
hebben we zo:
Het algoritme van Euclides wordt dan in kettingbreuknotatie:
Merk op dat ook ,
want .
We schrijven enkele kettingbreuken als gewone breuken (met slechts één breukstreep):
De teller en de noemer zijn in deze gevallen veeltermen in
. Hieronder zullen
we veeltermen en
definiëren en vervolgens
bewijzen dat inderdaad .
7.44 Definitie. We definiëren de rij veeltermen
door
Het algoritme van Euclides toegepast op
en leverde
. Met de
veeltermen kun
je de breuk
terugvinden:
Bij deze manier van rekenen heb je de quotiënten die in het algoritme optreden, in
omgekeerde volgorde nodig. Je krijgt zo de resten uit het algoritme in omgekeerde volgorde
terug. Opmerkelijk genoeg kan het ook andersom. De basis daarvoor is de volgende
stelling.
7.45 Stelling.Voor iedere geldt .
Bewijs. Laat
zijn de uitspraak
We bewijzen met volledige inductie dat
en voor
alle .
Voor
is het duidelijk.
Stel en
gelden voor
een met
. Dan te bewijzen
dat ook
geldt.
7.46Gevolg. Voor iederegeldt
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
7.47 Definitie.De rij veeltermen
is gedefinieerd door
en voor :
.
De rij van de veeltermen
wordt dus op dezelfde manier opgebouwd als die van de veeltermen ,
alleen de ‘startwaarden’ (voor
en )
zijn niet
en ,
maar
en .
7.48 Stelling.Voor allegeldt dat
voor alle rationale (later: reële) getallen met .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
7.49Voorbeeld. We schrijven
als gewone breuk met behulp van bovenstaande stelling:
Dus: .
(De
en
worden van links naar rechts berekend: bijv.
en .)
Vergelijk dit met het uitgebreide algoritme van Euclides. Daarbij treden, afgezien
van het teken, dezelfde getallen op, en wel de getallen
en .
Dit is eenvoudig met volledige inductie te bewijzen.
7.50 Stelling.Voor allegeldt dat
voor alle getallen met ,waarbij we steeds voor schrijven en voor analoog.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
7.51Gevolg. Zij .Laten gehele getallen zijn met .Dan
Bewijs. We schrijven
voor
en analoog voor .
Merk op dat
voor alle .
Uit
volgt dat
de enige positieve gemene deler van
en
is. Dus is hun grootste gemene deler gelijk aan .
□
Voor
en
hebben we dus
met .
Schrijven we bijvoorbeeld
als zo’n kettingbreuk, dan vinden we
en dus
met
en .
Python
Het omschrijven van gewone breuken in eindige kettingbreuken en omgekeerd kan
eenvoudig met de computer gebeuren. Het omzetten van gewone breuk naar kettingbreuk
is een vorm van het uitgebreide algoritme van Euclides, de ‘Chinese’ versie van het
algoritme.
def confrac(a, b): d = divmod(a, b) if d[1]==0: return (d[0],) else: return (d[0],) + confrac(b, d[1]) def fract(con): r, p = 0, 1 s, q = 1, 0 for i in con: r, p = p, r + i * p s, q = q, s + i * q return (p, q) def chin(a, b): i = 0 r, p = 0, 1 s, q= 1, 0 while b>0: i = i + 1 d = divmod(a, b) r, p = p, d[0] * p + r s, q = q, d[0] * q + s a, b = b, d[1] return (a, (-1)**i * s,-(-1)**i * r)