Astronomy Answers
The Extended Euclidean Algorithm


[Astronomy Answers] [Dictionary] [AnswerBook] [Universe Family Tree] [Science] [Starry Sky] [Planet Positions] [Calculate] [Colophon]

1. The Algorithm ... 2. Applications ... 2.1. Simultaneous Cycles ... 2.2. Greatest Common Divisor ... 2.3. Least Common Multiple ... 2.4. Good Approximations

\( \DeclareMathOperator{\lcm}{lcm} \)

1. The Algorithm

For two whole numbers \( x, y \), the extended Euclidean algorithm provides a series of solutions \( h_i, k_i, r_i \) (all whole numbers) for

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

where \( |r_i| \) gets ever smaller and eventually is equal to the greatest common divisor \( g = \gcd(x,y) \) of \( x \) and \( y \) ― the smallest possible value of \( r_i \) greater than zero for which such a solution exists.

The algorithm goes as follows:

\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}

The algorithm stops when \( d_i \) becomes equal to 0. Suppose that happens when \( i = m + 1 \), so \( m \) is the index of the last \( d_i \) unequal to zero. Then, for each \( i ≥ 0 \)

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

and in particular

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

2. Applications

2.1. Simultaneous Cycles

Suppose that we seek solutions \( k \) for the simultaenous equations (in whole numbers)

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

If a certain \( k \) solves those equations, then so does \( k + P \) with

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

the least common multiple of \( p_1 \) and \( p_2 \): the smallest number that can be divided evenly by both \( p_1 \) and \( p_2 \). If a certain \( k_0 \) is a solution, then all solutions are defined by

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

which means

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

for all whole numbers \( a \).

The solutions of only the first equation are

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

for all whole numbers \( b \). If we enter that into the second equation then we find

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

so

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

and

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

for all whole numbers \( c \), so we seek \( b, c \) for which

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

Suppose that we can find a solution \( b_0, c_0 \) for

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

where \( g = \gcd(p_1,p_2) \) is the greatest common divisor of \( p_1 and \( p_2 \) \): the greatst number that divides evenly into \( p_1 \) and \( p_2 \).

If \( q_2 - q_1 \) is not divisible by \( g \), then there is no solution to the original problem.

If \( q_2 - q_1 \) is divisible by \( g \), then the solution for equation \eqref{doel} is

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

Then

\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}

All solutions to the original problem are then

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

So, given \( q_1, q_2, p_1, p_2 \) we need:

We can find all of those using the extended Euclidean algorithm.

Suppose that a calendar uses simultaneous periods of 5 and 7 days, and ties running day number \( J \) with calendar date \( \{q_1,q_2\} \) through

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

so the first few days \( \{q_1,q_2\} \) of that calendar are: {0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {5,0}, {6,1}, {0,2}, {1,3}. We seek a formula that goes in the other direction, from \( \{q_1,q_2\} \) to \( J \).

We apply the algorithm to \( x = p_1 = 7, y = p_2 = 5 \) and find

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

so \( −2p_1 + 3p_2 = 1 \), which means \( b_0 = −2, c_0 = ―3 \), and

\[ \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} \]

so

\[ \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} \]

Let's check:

\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. Greatest Common Divisor

The greatest common divisor \( \gcd(x,y) \) of \( x \) and \( y \) is given by \( d_m \): the last \( d_i \) that is not equal to zero.

In the previous example \( d_2 = 1, d₃ = 0 \), so \( \gcd(7,5) = 1 \).

This greatest common divisor can also be found with the better-known (regular) Euclidean algorithm, which is slightly simpler than the extended Euclidean algorithm that we described before. The (regular) Euclidean algorithm is as follows:

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

The algorithm terminates when \( d_i \) becomes equal to 0. Suppose that is when \( i = m + 1 \). Then

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

If you seek the greatest common divisor and have no interest in the other applications of the extended algorith, then you're better off using the regular algorithm.

What is the greatest common divisor of 120 and 25? Then

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

so the greatest common divisor is 5. 120 is divisible by 5 (120/5 = 24), and 25 is divisible by 5 (25/5 = 5), and they cannot both be divided by an even larger number.

2.3. Least Common Multiple

The least common multiple \( \lcm(x,y) \) of \( x \) and \( y \) is equal to

\begin{equation} \lcm(x,y) = \frac{xy}{\gcd(x,y)} \end{equation}

because

\begin{equation} xy = \gcd(x,y) \lcm(x,y) \end{equation}

The greatest common divisor \( \gcd(x,y) \) can be found as described in the previous section.

What is the least common multiple of 120 and 25? We found earlier that their greatest common divisor is 5, so the least common multiple is \( 120×25/5 = 600 \). 600 is divisible by 120 (600/120 = 5) and is divisible by 25 (600/25 = 24), and no smaller number is divisible by both 120 and 25.

2.4. Good Approximations

Suppose that you have an irrational number \( z \) (not expressible as a ratio of whole numbers) like π ≈ 3.14159265... or √2 ≈ 1.41421356..., or the ratio of the lengths of astronomical periods such as the precise number of days in a solar year (365.2421898...), or the precise number of days in a lunar month (29.53058885...), and you want to find a ratio of whole numbers with a small denominator that is a good approximation to the irrational number ― for example to base a calendar on.

Then use the extended Euclidean algorithm with \( y = 1 \) and \( x = z \) the number for which you seek the approximation ― or use an adjusted version of the algorithm in which you use the number \( z_i \) (not necessarily a whole number) instead of \( n_i \) and \( d_i \), with

\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}

The ratios \( h_i/k_i \) for increasing \( i \) then provide successive "good" approximation, in the sense that there is no ratio \( h/k \) with \( k < k_i \) for which \( |h - zk| \) is less than \( |h_i - zk_i| \). For irrational numbers the algorithm does not terminate, so you need to stop it yourself, for example when \( k_i \) exceeds a chosen value.

With the results from the extended algorithm, the number \( z \) can be written

\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}

Also

\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}

and

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

so

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

Let's look for good approximations to the number π ≈ 3.14159265359... Then \( z_0 = π \) and then

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

The best approximation with a denominator less than 30,000 turns out to be 355/113, which deviated only about 0.000003. We find

\[ \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]

languages: [en] [nl]

//aa.quae.nl/en/reken/euclides.html;
Last updated: 2016-02-07