Astronomy Answers
The Extended Euclidean Algorithm

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

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

• the greatest common divisor \( g = \gcd(p_1,p_2) \) of \( p_1 \) and \( p_2 \)
• the least common multiple \( P = \lcm(p_1,p_2) \) of \( p_1 \) and \( p_2 \)
• a solution \( b_0, c_0 \) of \( b_0p_1 - c_0p_2 = g \)

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

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.

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.

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.

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}

languages: [en] [nl]

//aa.quae.nl/en/reken/euclides.html;
Last updated: 2021-07-19