AstronomieAntwoorden
Het Uitgebreide Algoritme van Euclides

\(\def\|{&}\DeclareMathOperator{\D}{\bigtriangleup\!} \DeclareMathOperator{\d}{\text{d}\!}\)

\( \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:

• de grootste gemene deler \( g = \ggd(p_1,p_2) \) van \( p_1 \) en \( p_2 \)
• het kleinste gemene veelvoud \( P = \kgv(p_1,p_2) \) van \( p_1 \) en \( p_2 \)
• een oplossing \( b_0, c_0 \) van \( b_0p_1 - c_0p_2 = g \)

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

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.

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.

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.

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}

talen: [en] [nl]

//aa.quae.nl/nl/reken/euclides.html;
Laatst vernieuwd: 2021-07-19