Kettingbreuken

Overzicht ][ Getallentheorie

---

0. Overzicht

1. Gevolg van de Euclidische algoritme
2. Definitie kettingbreuk
3. Benaderende breuken
4. Algoritme
5. Geheeltallige oplossingen van ax + by = c

1. Gevolg van de Euclidische algoritme
Zij A = t / m een breuk met ggd(t,m) = 1.
De getallen t en m heten in dit geval onderling ondeelbaar of ook wel relatief priem.
Volgens de Euclidische algoritme (zie ook de pagina "Deelbaarheid") kunnen we nu getallen a_i en r_i vinden met
   
In de laatste twee regels is G = ggd(t,m) (een en andere geheel op basis van de Euclidische algoritme).
Voor G = 1 hebben we dus r_n - 2 = a_n.
Op basis hiervan vinden we
   

2. Definitie kettingbreuk
Uit hetgeen gevonden is in paragraaf 1 kunnen we nu eenvoudig (per regel) afleiden:

   

Toelichting bij de recursieve definitie
Regel (1) in de definitie zegt wat een kettingbreuk is bestaande uit één element.
Regel (2) in de definitie zegt wat een kettingbreuk is bestaanden uit n elementen, als de kettingbreuk met n-1 elementen bekend is.
[einde Toelichting]

Voorbeeld
   
[einde Voorbeeld]

Afwijkende vormen van kettingbreuken zijn bijvoorbeeld
(1) ]a1, a2, ..., an-2, ]an-1, an[[
(2) ]a1, a2, ..., an-3, ]an-2, an-1, an[[
(3) ]a1, a2, ..., an-1, ]a_n - 1, 1[[.
In dit laatste geval (3) is
   ]a_n - 1, 1[ = (a_n - 1) + ¹/₁ = a_n
zodat dus
   ]a1, a2, ..., an-1, ]a_n - 1, 1[[ =  ]a1, a2, ..., an[

3. Benaderende breuken
Voor A = ]a1, a2, ..., an[ schrijven we
   
zodat
   

Gevolg
   

4. Algoritme
Op basis van de uitdrukking voor P_k / Q_k (in het Gevolg in paragraaf 3):
   
kunnen we een algoritme voor de berekening van de waarde van een kettingbreuk ontwerpen.
We merken op, dat uit de laatste formule voor k = 2 een waarde kan worden gevonden voor P₀ en Q₀ (de 0-de benaderende breuk van elke kettingbreuk).
We vinden:
   P₂ = a₂P₁ + P₀ of a₂a₁ + 1 = a₂a₁ + P₀
   Q₂ = a₂Q₁ + Q₀ of a₂ = a₂ . 1 + Q₀
Hieruit volgt dus: P₀ = 1 en Q₀ = 0.

Voorbeeld
Uitgaande van A = ]3,7,2,5,11[ vinden we de opeenvolgende benaderende breuken uit
   
Dus A = ²⁸⁷⁴/₉₁₇.
[einde Voorbeeld]

Uit de genoemde uitdrukking voor P_k / Q_k kunnen we eveneens afleiden:
   
zodat we voor de teller hiervan vinden:
   
en dus
   
Deze relatie geeft een eenvoudige uitdrukking voor A = P_n / Q_n:
   

Opmerking
Zie voor een voorbeeld van een oneindige kettingbreuk de pagina "Gulden snede en Getallen van Fibonacci".
[einde Opmerking]

5. Geheeltallige oplossingen van ax + by = c
Uitgangspunt is een vergelijking
   ax + by = c
met a, b, c geheel en waarbij ggd(c, ggd(a,b)) = 1.
Als G =  ggd(a,b) | c, dan herleiden we via deling door G.
Zonder de algemeenheid geweld aan te doen kunnen we stellen, dat ggd(a,b)=1.

Particuliere oplossing
Zij x = x₁, y = y₁ een oplossing van de vergelijking.
Bekijk nu voor iedere gehele t : x = x₁ + bt , y = y₁ - at.
Nu is bij substitutie:
   ax + by = ax₁ + abt + by₁ - abt = ax₁ + by₁ = c
Dus ook x = x₁ + bt, y = y₁ - at is een oplossing van de vergelijking (vooor iedere t)
Stel x₂, y₂ is een tweede oplossing van de vergelijking.
Nu hebben we
   ax₁ + by₁ = c
   ax₂ + by₂ = c
Zodat
   a(x₂ - x₁) = b(y₁ - y₂)
Dus b | a(x₂ - x₁)
Er is dus een t met bt = x₂ - x₁, zodat at = y₁ - y₂.
Elke tweede oplossing van de vergelijking wordt dus gevonden uit x = x₁ + bt, y = y₁ - at.
We hebben nu dus bewezen

Opmerking
Door invoering van een nieuwe veranderlijke, -x of -y, kan er steeds voor gezorgd worden, dat a > 0 en b > 0.
[einde Opmerking]

Het vinden van een particuliere oplossing
Zij nu a / b = ]a1, a2, ..., an[ = P_n/ Q_n, zodat dus Pn = a en Qn = b.
We hebben a / b dus in een kettingbreuk ontwikkeld.
In paragraaf 4 hebben we afgeleid, dat P_nQ_n+1 - P_n+1Q_n =(-1)ⁿ.
Stel nu x = (-1)ⁿQ_n-1 en y = (-1)^n - 1P_n-1
Nu is, bij substitutie,

Gevolg

[einde Gevolg]

Voorbeelden
[1]
We lossen op de vergelijking 8 x + 11 y = 417
Nu is
   
zodat 8 / 11 =] 0,1,2,1,2 [, met n = 5.
De 4-de benadering van 8/11 is dan dus

Dus P_n-1 = 3 en Q_n-1 = 4
Met het bovenstaande Gevolg vinden we dus de algemene oplossing:
   x = -4 . 417 + 11 t
   y = 3 . 417 - 8 t
Voor de positieve oplossingen geldt ¹⁶⁶⁸/₁₁ < t <¹²⁵¹/₈. Dit is juist voor

[2]
31 x - 51 y = 22
   
Dus ³¹/₅₁ = ] 0,1,1,1,1,4,2 [ met n = 7.
] 0,1,1,1,1,4 [ = ¹⁴/₂₃, zodat de algemene oplossing van 31 x - 51 y = 22 gelijk is aan
   x = -23 . 22 + 51 t = -506 + 51 t
   -y = 14 . 22 + 31 t = -308 + 31 t
of ook
   x = 5 + 51 u
   y = 2 + 31 u
De positieve oplossingen vinden we voor u > 0.

[3]
2874 x + 917 y = 1.000.000
   ²⁸⁷⁴/₉₁₇ = ] 3,7,2,5,11 [ met n = 5.
   ] 3,7,2,5 [ = ²⁵⁷/₈₂.
Dus
   x = -82 . 10⁶ +917 t
   y = 257 . 10⁶ - 2874 t
Voor x > 0 hebben we t > 82 . 10⁶ / 917 = 89422,028...
Voor y > 0 hebben we t < 257 . 10⁶ / 2874 =  89422.40...
Er zijn dus geen positieve oplossingen van deze vergelijking.
Het bovenstaande kan snel worden geconcludeerd op basis van de hieronder staande Stelling 3.

[einde Voorbeelden]

Bewijs:
Stel x=x₁, y=y₁ is een oplossing van ax +by = 1. Dat wil zeggen
   ax₁ + by₁ = 1
waaruit dus volgt dat  y₁ = (1 - ax₁)/b.
De algemene oplossing van ax + by = c is dan
   x = cx₁ - bt
   y = cy₁ + at
Voor x > 0 hebben we dan t < cx₁/b
Voor y > 0 hebben we t > -cy₁/a = - (c - acx₁)/ab = cx₁/b - c/ab
Of te wel
   cx₁/b - c/ab < t < cx₁/b
Voor c/ab > 1 is er tenminste één gehele waarde van t tussen de beide grenzen.
Met andere woorden voor c > ab heeft de vergelijking positieve oplossingen.¨

---

[ketting.htm] laatste wijziging op: 13-09-2001