AstronomieAntwoorden
Het Uitgebreide Algoritme van Euclides


[AA] [Woordenboek] [Antwoordenboek] [UniversumFamilieBoom] [Wetenschap] [Sterrenhemel] [Planeetstanden] [Reken] [Colofon]

1. Het Algoritme ... 2. Toepassingen ... 2.1. Gelijktijdige cycli ... 2.2. Grootste gemene deler ... 2.3. Kleinste gemene veelvoud ... 2.4. Goede benaderingen

\( \DeclareMathOperator{\kgv}{kgv} \DeclareMathOperator{\ggd}{ggd} \)

1. Het Algoritme

Voor twee hele getallen \( x, y \) geeft het uitgebreide algoritme van Euclides een serie oplossingen \( h_i, k_i, r_i \) (ook allen hele getallen) voor

\begin{equation} k_i x - h_i y = r_i \end{equation}

waarbij \( |r_i| \) steeds kleiner wordt en uiteindelijk gelijk wordt aan de grootste gemene deler \( g = \ggd(x,y) \) van \( x \) en \( y \) ― dat is de kleinste mogelijke waarde van \( r_i \) ongelijk aan nul waarvoor zo'n oplossing bestaat.

Het algoritme is als volgt:

\begin{align} n_0 & = x \\ d_0 & = y \\ h_{−2} & = k_{−1} = 0 \\ k_{−2} & = h_{−1} = 1 \\ q_i & = \left\lfloor \frac{n_i}{d_i} \right\rfloor \\ h_i & = q_{i}h_{i-1} + h_{i-2} \\ k_i & = q_{i}k_{i-1} + k_{i-2} \\ n_{i+1} & = d_i \\ d_{i+1} & = n_i - q_{i}d_i \end{align}

Het algoritme stopt als \( d_i \) gelijk wordt aan 0. Stel, dat is als \( i = m + 1 \), dus \( m \) is de index van de laatste \( d_i \) die niet gelijk is aan nul. Dan is voor elke \( i ≥ 0 \)

\begin{equation} xk_i - yh_i = (−1)^i d_{i+1} \end{equation}

en in het bijzonder

\begin{equation} |xk_m - yh_m| = d_{m+1} = \ggd(x,y) \end{equation}

2. Toepassingen

2.1. Gelijktijdige cycli

Stel, we zoeken oplossingen \( k \) voor de gelijktijdige vergelijkingen (in hele getallen)

\begin{align} k & ≡ q_1 \pmod{p_1} \\ k & ≡ q_2 \pmod{p_2} \end{align}

Als een bepaalde \( k \) een oplossing is van deze vergelijkingen, dan is \( k + P \) dat ook, met

\begin{equation} P = \kgv(p_1,p_2) \end{equation}

het kleinst gemene veelvoud van \( p_1 \) en \( p_2 \): het kleinste getal dat deelbaar is door zowel \( p_1 \) als \( p_2 \). Als een bepaalde \( k_0 \) een oplossing is, dan worden alle oplossingen gegeven door

\begin{equation} k ≡ k_0 \pmod{P} \end{equation}

ofwel

\begin{equation} k = k_0 + aP \end{equation}

voor alle hele getallen \( a \).

De oplossingen van alleen de eerste vergelijking zijn

\begin{equation} k = q_1 + bp_1 \end{equation}

voor alle hele getallen \( b \). Als we die invullen in de tweede vergelijking dan vinden we

\begin{equation} q_1 + bp_1 ≡ q_2 \pmod{p_2} \end{equation}

dus

\begin{equation} bp_1 ≡ q_2 - q_1 \pmod{p_2} \end{equation}

ofwel

\begin{equation} bp_1 = q_2 - q_1 + cp_2 \end{equation}

voor alle hele getallen \( c \), dus zoeken we \( b, c \) waarvoor geldt

\begin{equation} bp_1 - cp_2 = q_2 - q_1 \label{eq:doel} \end{equation}

Stel, we kunnen een oplossing \( b_0, c_0 \) vinden voor

\begin{equation} b_0p_1 - c_0p_2 = g \label{eq:basis} \end{equation}

waarin \( g = \ggd(p_1,p_2) \) de grootste gemene deler van \( p_1 \) en \( p_2 \) is: het grootste getal waardoor zowel \( p_1 \) en \( p_2 \) gedeeld kan worden zonder een rest te laten.

Als \( q_2 - q_1 \) niet deelbaar is door \( g \), dan is er geen oplossing voor het originele probleem.

Als \( q_2 - q_1 \) wel deelbaar is door \( g \), dan is de oplossing voor vergelijking \eqref{eq:doel}

\begin{align} b & = \frac{b_0(q_2 - q_1)}{g} \\ c & = \frac{c_0(q_2 - q_1)}{g} \end{align}

Dan is

\begin{align} k & = k_0 ≡ q_1 + bp_1 = q_1 + \frac{b_0p_1(q_2 - q_1)}{g} = q_1 \left( 1 - \frac{b_0p_1}{g} \right) + \frac{q_2b_0p_1}{g} \\ k & = k_0 ≡ q_2 + cp_2 = q_2 + \frac{c_0p_2(q_2 - q_1)}{g} = q_2 \left( 1 + \frac{c_0p_2}{g} \right) - \frac{q_1c_0p_2}{g} \end{align}

Alle oplossingen voor het originele probleem zijn dan

\begin{equation} k ≡ k_0 \pmod{P} \end{equation}

Gegeven \( q_1, q_2, p_1, p_2 \) hebben we dus nodig:

Al die zaken kunnen we vinden met behulp van het uitgebreide algoritme van Euclides.

Stel, een kalender gebruikt gelijktijdige perioden van 5 en 7 dagen, en verbindt doorlopende dagnummer \( J \) met kalenderdatum \( \{q_1,q_2\} \) door

\begin{align*} q_1 & = J \bmod 7 \\ q_2 & = J \bmod 5 \end{align*}

zodat de eerste paar dagen \( \{q_1,q_2\} \) van die kalender zijn: {0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {5,0}, {6,1}, {0,2}, {1,3}. We zoeken een formule die de andere kant op gaat, dus van \( \{q_1,q_2\} \) naar \( J \).

Dan passen we het algoritme toe op \( x = p_1 = 7, y = p_2 = 5 \) en vinden

inidiqihiki
−2 0 1
−1 1 0
0 7 5 1 1 1 1×7 − 1×5 = +2
1 5 2 2 3 2 2×7 − 3×5 = −1
2 2 1 2 7 5 5×7 − 7×5 = 0
3 1 0

dus \( −2p_1 + 3p_2 = 1 \), ofwel \( b_0 = −2 \), \( c_0 = ―3 \), en

\[ \begin{split} J & = q_1 × \left(1 - \frac{(−2)×7}{1} \right) + \frac{q_2×−2×7}{1} \pmod{35} \\ & = 15q_1 - 14q_2 \pmod{35} \end{split} \]

of

\[ \begin{split} J & = q_2 × \left( 1 + \frac{(−3)×5}{1} \right) - \frac{q_1×−3×5}{1} \pmod{35} \\ & = −14q_2 - (−15)q_1 \pmod{35} \\ & = 15q_1 - 14q_2 \pmod{35} \end{split} \]

Even controleren:

\begin{align*} \{4,4\} & → 15×4 - 14×4 \bmod{35} = 4 \\ \{5,0\} & → 15×5 - 14×0 \bmod{35} = 75 \bmod 35 = 5 \\ \{1,3\} & → 15×1 - 14×3 \bmod{35} = −27 \bmod 35 = 8 \end{align*}

2.2. Grootste gemene deler

De grootste gemene deler \( \ggd(x,y) \) van \( x \) en \( y \) wordt gegeven door \( d_m \): de laatste \( d_i \) die niet nul is.

In het voorheen gegeven voorbeeld is \( d_2 = 1, d₃ = 0 \), dus \( \ggd(7,5) = 1 \).

Deze grootste gemene deler kan ook gevonden worden met het meer bekende (gewone) "algoritme van Euclides", dat iets simpeler is dan het uitgebreide algoritme dat we eerder gaven. Het (gewone) algoritme van Euclides is als volgt:

\begin{align} n_0 & = x \\ d_0 & = y \\ n_{i+1} & = d_i \\ d_{i+1} & = n_i \bmod{d_i} \end{align}

Het algoritme stopt als \( d_i \) gelijk wordt aan 0. Stel dat is als \( i = m + 1 \). Dan

\begin{equation} \ggd(x,y) = d_m = n_{m+1} \end{equation}

Als je de grootste gemene deler zoekt en geen interesse hebt voor de andere toepassingen van het uitgebreide algoritme, dan kun je beter het kortere gewone algoritme gebruiken.

Wat is de grootste gemene deler van 120 en 25? Dan

\(i\) \(n_i\) \(d_i\)
0 120 25
1 25 20
2 20 5
3 5 0

dus de grootste gemene deler is 5. 120 is deelbaar door 5 (120/5 = 24), en 25 is deelbaar door 5 (25/5 = 5), en ze zijn niet allebei deelbaar door een nog groter getal.

2.3. Kleinste gemene veelvoud

Het kleinste gemene veelvoud \( \kgv(x,y) \) van \( x \) en \( y \) wordt gegeven door

\begin{equation} \kgv(x,y) = \frac{xy}{\ggd(x,y)} \end{equation}

want

\begin{equation} xy = \ggd(x,y) \kgv(x,y) \end{equation}

De grootste gemene deler \( \ggd(x,y) \) kan worden gevonden zoals beschreven in het vorige hoofdstuk.

Wat is het kleinste gemene veelvoud van 120 en 25? We vonden hierboven dat de grootste gemene deler gelijk is aan 5, dus het kleinste gemene veelvoud is \( 120×25/5 = 600 \). 600 is deelbaar door 120 (600/120 = 5) en is deelbaar door 25 (600/25 = 24), en geen kleiner getal is deelbaar door zowel 120 als 25.

2.4. Goede benaderingen

Stel je hebt een irrationaal getal \( z \) (niet precies uit te drukken als een breuk) zoals π ≈ 3,14159265... of √2 ≈ 1,41421356..., of de verhouding van lengtes van astronomische perioden zoals het preciese aantal dagen in een zonnejaar (365,2421898...), of het preciese aantal dagen tussen twee volle manen (29,53058885...), en je wilt een breuk vinden met een kleine noemer waarmee dat irrationale getal goed benaderd kan worden ― bijvoorbeeld om er een voorspelbare kalender op te baseren.

Gebruik dan het uitgebreide algoritme van Euclides met \( y = 1 \) en \( x = z \) het getal waarvoor je de benadering zoekt ― of een aangepaste versie waarin je getal \( z_i \) (niet per sé heel) gebruikt in plaats van \( n_i \) en \( d_i \), met

\begin{align} z_0 & = z \\ q_i & = \left\lfloor z_i \right\rfloor \\ z_{i+1} & = \frac{1}{z_i \bmod{1}} = \frac{1}{z_i - q_i} \end{align}

De breuken \( h_i/k_i \) zijn dan voor toenemende \( i \) opeenvolgende "goede" benaderingen, in de zin dat er geen breuk \( h/k \) is met \( k < k_i \) waarvoor \( |h - zk| \) kleiner is dan \( |h_i - zk_i| \). Voor irrationale getallen eindigt het algoritme niet, dus moet je het algoritme zelf stoppen, bijvoorbeeld als \( k_i \) groter wordt dan een voorafgekozen waarde.

Met de uitkomsten van het uitgebreide algoritme is het getal \( z \) ook te schrijven als

\begin{equation} z = \frac{q_0}{k_0} + \frac{1}{k_0k_1} - \frac{1}{k_1k_2} + \frac{1}{k_2k_3} - ... \end{equation}

Ook

\begin{equation} \left| \frac{h_i}{k_i} - \frac{h_{i-1}}{k_{i-1}} \right| = \frac{1}{k_{i}k_{i-1}} \end{equation}

en

\begin{equation} \left| z - \frac{h_i}{k_i} \right| < \frac{1}{k_{i}k_{i+1}} \end{equation}

dus

\begin{equation} |h_i - zk_i| < \frac{1}{k_{i+1}} \end{equation}

Laten we zoeken naar goede benaderingen voor het getal π ≈ 3,14159265359... Dan \( z_0 = π \) en dan

\(i\) \(z_i\) \(q_i\) \(h_i\) \(k_i\) \(h_i/k_i\) \(h_i - z_0k_i\)
−2 0 1
−1 1 0
0 3,14159265359 3 3 1 3 −0,14
1 7,06251330592 7 22 7 22/7 0,00885
2 15,9965944095 15 333 106 333/106 −0,00882
3 1,00341722818 1 355 113 355/113 3,0 × 10−5
4 292,63483365 292 103993 33102 103993/33102 −1,9 × 10−5

De beste benadering met een noemer kleiner dan 30.000 is dus 355/113, die slechts ongeveer 0,000003 afwijkt. We vinden

\[ \begin{split} π & ≈ 3 + \frac{1}{1×7} - \frac{1}{7×106} + \frac{1}{106×113} - \frac{1}{113×33102} + ... \\ & = 3 + \frac{1}{7} - \frac{1}{742} + \frac{1}{11978} - \frac{1}{3740526} + ... \end{split} \]



[AA]

talen: [en] [nl]

http://aa.quae.nl/nl/reken/euclides.html;
Laatst vernieuwd: 2016−02−07