Extended Euclidean Algorithm

The algorithm for computing the greatest common divisor (GCD) was discovered by ancient Greek mathematicians and is known as the "algorithm of mutual subtraction". Although references to this algorithm can be found in Aristotle's works, it was later named after Euclid. What the greatest common divisor is, its properties, and methods of calculation are discussed in [1].

Let's recall that the GCD of two numbers can be calculated according to the following recurrence:

In C language, the procedure for calculating the GCD looks like this:

int gcd(int a, int b)
{
  if (b == 0) return a;
  return gcd(b, a % b);
}

The Euclidean algorithm can be extended to find for given a and b such integers x and y that $ax+by=d$, where $d$ is the greatest common divisor of $a$ and $b$.

Lemma. Let for positive integers $a$ and $b$ ($a>b$) known $d$ = GCD($a$, $b$) = GCD($b$, $a$ mod $b$), and also numbers $x$’ and $y$’, for which

$d=x$’ · $b$ + $y$’ · ($a$ mod $b$)

Then the values of $x$ and $y$, which are solutions to the equation $ax+by=d$, are found from the relations

$x=y$’, $y=x$’ – $y$’ · $\left|\frac{a}{b}\right|$      (2)

Here $\left|\frac{a}{b}\right|$ denotes the integer part of the number a/b.

Proof. Since $a$ mod $b$ = $a$ – $\left|\frac{a}{b}\right|$ · $b$, then

$d=x$’ · $b$ + $y$’ · ($a$ – $\left|\frac{a}{b}\right|$ · $b$) = $y$’ · $a$ + ($x$’ – $y$’ · $\left|\frac{a}{b}\right|$ ) · $b$ = $x$ · $a$ + $y$ · $b$,

where denoted $x=y$’, $y=x$’ – $y$’ · $\left|\frac{a}{b}\right|$ .

The function gcdext(int a, int b, int *d, int *x, int *y), shown below, finds $d$ = GCD($a$, $b$) and such $x$, $y$ that $d=a\cdot x+b\cdot y$ for the input numbers $a$ and $b$. To find the unknowns $x$ and $y$, it is necessary to recursively start the function gcdext(b, a mod b, d, x, y) and recalculate the values of $x$ and $y$ using the formula above. The recursion ends when $b=0$. At $b=0$, GCD($a$, 0) = $a$ and $a=a\cdot 1+0\cdot 0$, so we consider $x=1$, $y=0$.

void gcdext (int a, int b, int *d, int *x, int *y)
{
  int s;
  if (b == 0)
  {
    *d = a; *x = 1; *y = 0;
    return;
  }
  gcdext(b,a % b,d,x,y);
  s = *y;
  *y = *x - (a / b) * (*y);
  *x = s;
}

For manual execution of the extended Euclidean algorithm, it is convenient to use a table with four columns (as shown below in the example), corresponding to the values of $a$, $b$, $x$, $y$. The calculation process is divided into three stages:

a) First, we calculate the GCD($a$, $b$), using the first two columns of the table and relation (1). In the last row in the column $a$, the value of $d$ = GCD($a$, $b$) will be found.

b) We enter the values 1 and 0 respectively into the columns $x$ and $y$ of the last row.

c) We will sequentially fill in the rows for the columns $x$ and $y$ from bottom to top. The values of $x$ and $y$ in the last row have already been entered at stage b). Assuming that the values ($x$’, $y$’) are already located in the current filled row, we will recalculate and enter the values ($x$, $y$) into the corresponding cells in the row above using formulas (2).

1. Extended Euclidean Algorithm. Find the solution to the equation $5x+3y=1$. The calculation of GCD(5, 3) and finding the corresponding $x$, $y$ are done in the table:

The order and direction of calculations are indicated by arrows and letters.

From the table, we find that GCD(5, 3) = $5\cdot (-1)+3\cdot 2=1$, i.e., $x=-1$, $y=2$.

Consider, for example, how the values ($x$, $y$) for the first row were obtained. From the second row, we take the values ($x$’, $y$’) = (1, -1). According to formulas (2), we get:

$x=y$’ = -1,

$y=x$’ – $y$’ · $\left|\frac{a}{b}\right|$  = 1 – (-1) · $\left|\frac{5}{3}\right|$  = 1 + 1 = 2

Linear Equation is an equation in the form $ax=b$ (mod $n$). It has a solution if and only if $b$ is divisible by $d$ = GCD($a$, $n$). If $d>1$, the equation can be simplified by replacing it with $a$’$x=b$’ (mod $n$’), where $a$’ = $a/d$, $b$’ = $b/d$, $n$’ = $n/d$. After such a transformation, the numbers $a$’ and $n$’ are coprime.

The algorithm for solving the equation $a$’$x=b$’ (mod $n$’) with coprime $a$’ and $n$’ consists of two parts:

1. Solve the equation $a$’$x=1$ (mod $n$’). To do this, use the extended Euclidean algorithm to find the solution ($x_0$, $y_0$) to the equation $a$’$x+n$’$y=1$. Taking the modulus $n$’ for the last equation, we get $a$’$x_0=1$ (mod $n$’).

2. Multiply the equation $a$’$x_0=1$ (mod $n$’) by $b$’. We get $a$’($b$’$x_0$) = $b$’ (mod $n$’), from which the solution to the initial equation $a$’$x=b$’ (mod $n$’) will be $x=b$’$x_0$ (mod $n$’).

Lemma. If GCD($k$, $m$) = 1, then the equation $ak=bk$ (mod $m$) is equivalent to $a=b$ (mod $m$).

Proof. From $ak=bk$ (mod $m$), it follows that ($a–b$) · $k$ is divisible by $m$. But since $k$ and $m$ are coprime, $a–b$ is divisible by $m$, i.e., $a=b$ (mod $m$).

Example. Solve the equation $18x=6$ (mod 8).

The value $d$ = GCD(18, 8) = 2 is a divisor of 6, so a solution exists. After simplification, we get the equation $9x=3$ (mod 4). According to the lemma, this is equivalent to $3x=1$ (mod 4). Solving the equation $3x+4y=1$ using the extended Euclidean algorithm, we get $x=-1$, $y=1$. Hence, $x=-1$ (mod 4) = 3. Thus, $x=3$ will be a solution to both the equation $3x=1$ (mod 4) and $18x=6$ (mod 8).

DIOPHANTINE EQUATIONS

Diophantine are equations in the form

$P(x_1,x_2,...,x_n)=0$,

where $P(x_1,...,x_n)$ is a polynomial with integer coefficients.

In this section, we will consider the algorithm for finding a solution to a linear Diophantine equation with two unknowns in the form $ax+by=c$ (for simplicity, we will omit multiplication signs and write simply $ax+by=c$).

Theorem 1. The equation $ax+by=c$ has a solution in integers if and only if $c$ is divisible by GCD($a$, $b$).

Theorem 2. If the pair ($x_0$, $y_0$) is a solution to the equation $ax+by=c$, then the entire set of its solutions ($x$, $y$) is described by the formula:

$x=x_0+kb$,

$y=y_0–ka$,

where $k$ ∈ Z. Obviously, if $a{x}_0+b{y}_0=c$, then $a(x_0+kb)+b(y_0–ka)=c$ for any integer $k$.

To find a particular solution ($x_0$, $y_0$) to the equation $ax+by=c$, one should first find the solution ($x$’, $y$’) to the equation $ax+by=d$ ($d$ – the greatest common divisor of $a$ and $b$) using the extended Euclidean algorithm, and then multiply it by $c/d$. That is,

$x_0=x$’ · $c/d$,

$y_0=y$’ · $c/d$

Example. Find the set of solutions to the equation $5x+3y=7$.

1. The equation has a solution, since 7 is divisible by GCD(5, 3) = 1.

2. Find the solution to the equation $5x$’ + $3y$’ = 1 using the extended Euclidean algorithm: ($x$’, $y$’) = (-1, 2).

3. Find the solution ($x_0$, $y_0$) to the initial Diophantine equation:

$x_0=-1\cdot 7/1=-7$,

$y_0=2\cdot 7/1=14$

According to Theorem 2, the set of solutions to the initial Diophantine equation is:

($x$, $y$) = (-7 + 3$k$, 14 – 5$k$)