Kettingbreuken

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:

Definitie
De hierboven staande schrijfwijze voor het rationale getal A heet kettingbreuk (A is ontwikkeld in een kettingbreuk).
Schrijfwijze: A =]a₁, a₂, a₃, ..., a_n[ of ook wel A = k(a₁, a₂, a₃, ..., a_n).
De getallen a_i heten de elementen van de kettingbreuk.

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]

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[

Definitie
De uitdrukking P_i / Q_i = ]a₁, a₂, ..., a_k[ met k = 1, 2, ..., n, noemen we een benaderende breuk van A=]a₁,a₂, ..., a_n[.

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:

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

Stelling 1
Als x₁, y₁ een oplossing is van ax + by = c, dan is de algemene oplossing van de vergelijking x = x₁ + bt, y = y₁ - at.
De oplossing x₁, y₁ heet een particuliere oplossing van de vergelijking.

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,

ax + by	=	P_n . (-1)ⁿQ_n-1 + Qn . (-1)^n - 1P_n-1
	=	(-1)ⁿ (PnQn-1 - QnPn-1)
	=	(-1)²ⁿ
	=	1

Stelling 2
x = (-1)ⁿQ_n-1, y = (-1)^n - 1P_n-1 is oplossing van de vergelijking ax + by = 1, waarin P_n-1/Q_n-1 de (n-1)-de benaderende breuk is van a/b.
cx, cy is dan een particuliere oplossing van de vergelijking ax + by = c.

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

t =	152	153	154	155	156

x =	4	15	26	37	48
y =	35	27	19	11	3

[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.

Stelling 3
Voor natuurlijke getallen a, b, c is de vergelijking ax + by = c met ggd(a,b) = 1 is met natuurlijke getallen oplosbaar als c > ab.

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.�