Simple Hyperbolic Diophantine Equation

Problem

Given the integers $A, B, C, D$, find a pair of $(x,y)$ such that it satisfies the equation $Axy + Bx + Cy = D$.

For example, $2xy + 5x + 56y = -7$ has a solution $(x,y) = (-27,64)$.

Hyperbolic equations are usually of form $Ax^2 + By^2 + Cxy + Dx + Ey = F$. Here we don’t have coefficients of $x^2$ and $y^2$. That’s why we are calling it “Simple”.

So how do we tackle the problem? First we will rewrite the equation to make it easier to approach.

Rewriting The Equation

$Axy + Bx + Cy = D$
$A^2xy + ABx + ACy = AD$, Multiply A with both sides
$A^2xy + ABx + ACy + BC = AD + BC$, Add BC to both sides
$Ax ( Ay + B ) + C ( Ay + B ) = AD + BC$,
$\therefore (Ax + C) (Ay + B) = AD + BC$

Now that we have rewritten the equation, we can see that the problem has two cases. We will handle each case separately.

When $AD + BC = 0$

When $AD + BC = 0$, our equation becomes $(Ax + C)(Ay + B) = 0$. So we need to have either $(Ax + C) = 0$ or $(Ay+B) = 0$ to satisfy the equation.

So we have two possible formation of solutions. When $(Ax+C) = 0$, we have $x = \frac{-C}{A}$ and $y$ any integer value. When $(Ay+B)=0$, we have $y = \frac{-B}{A}$ and $x$ any integer value.

So, $(x,y) = (\frac{-C}{A},k)$ or $(k,\frac{-B}{A})$, where $k$ is any integer. What if it is not possible to divide $-C$ or $-B$ with $A$? Then there is no solution of that formation.

When $AD + BC \neq 0$

Let $P = AD+BC$. Since $(Ax + C)(Ay+B) = P$, $(Ax+C)$ and $(Ay+B)$ must be divisors of $P$. Let $d_1, d_2, d_3 … d_n$ be divisors of $P$. Then for each divisor $d_i$, if $(Ax + C) = d_i$ then $(Ay + B) = \frac{P}{d_i}$, so that we get $P$ when we multiply them.

$(Ax + C) = d_i$
$Ax = d_i – C$
$\therefore x = \frac{d_i – C}{A}$

$(Ay+B) = \frac{P}{d_i}$
$Ay = \frac{P}{d_i} – B$
$Ay = \frac{P – Bd_i}{d_i}$
$\therefore y = \frac{P – Bd_i}{Ad_i}$

Therefore for each divisor $d_i$, we have $(x,y) = ( \frac{d_i – C}{A}, \frac{P – Bd_i}{Ad_i} )$. This solution is valid only if we get integer values for $(x,y)$.

Careful when calculating divisors of $P$. In this problem, we have to include the negative divisors of $P$ in our calculation. For example, $4$ will have the following divisors $(1,2,4,-1,-2,-4)$.

Example

Find solutions for $2xy + 2x + 2y = 4$.

First we will find $P = AD + BC = 2 \times 4 + 2 \times 2 = 12$. $12$ has the following divisors: $(\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12 )$.

Since $(2x + 2)(2y + 2 ) = 12$, we get the following:

$d_1 = 1: x = \frac{1-2}{2} = \frac{-1}{2}, y = \frac{12 – 2 \times 1}{2 \times 1} = \frac{10}{2} = 5$
$d_2 = -1: x = \frac{-1-2}{2} = \frac{-3}{2}, y = \frac{12 – 2 \times -1}{2 \times -1} = \frac{14}{-2} = -7$
$d_3 = 2: x = \frac{2-2}{2} = 0, y = \frac{12 – 2 \times 2}{2 \times 2} = \frac{8}{4} = 2$
$d_4 = -2: x = \frac{-2-2}{2} = -2, y = \frac{12 – 2 \times -2}{2 \times -2} = \frac{16}{-4} = -4$
$d_5 = 3: x = \frac{3-2}{2} = \frac{1}{2}, y = \frac{12 – 2 \times 3}{2 \times 3} = \frac{6}{6} = 1$
$d_6 = -3: x = \frac{-3-2}{2} = \frac{-5}{2}, y = \frac{12 – 2 \times -3}{2 \times -3} = \frac{18}{-1} = -18$
$d_7 = 4: x = \frac{4-2}{2} = 1, y = \frac{12 – 2 \times 4}{2 \times 4} = \frac{4}{8} = \frac{1}{2}$
$d_8 = -4: x = \frac{-4-2}{2} = -3, y = \frac{12 – 2 \times -4}{2 \times -4} = \frac{20}{-8} = \frac{-5}{2}$
$d_9 = 6: x = \frac{6-2}{2} = 2, y = \frac{12 – 2 \times 6}{2 \times 6} = \frac{0}{12} = 0$
$d_{10} = -6: x = \frac{-6-2}{2} = -4, y = \frac{12 – 2 \times -6}{2 \times -6} = \frac{24}{-12} = -2$
$d_{11} = 12: x = \frac{12-2}{2} = 5, y = \frac{12 – 2 \times 12 }{2 \times 12 } = \frac{-12}{24} = \frac{-1}{2}$
$d_{12} = -12: x = \frac{-12-2}{2} = -7, y = \frac{12 – 2 \times -12 }{2 \times -12 } = \frac{36}{-24} = \frac{-3}{2}$

So the solutions are $(0,2),(-2,-4),(2,0),(-4,-2)$.

Code

Let us try to write a function that will count the number of solutions for the given problem above. If there are infinite solutions, the function will return $-1$.

bool isValidSolution ( int a, int b, int c, int p, int div ) {
    if ( ( ( div - c )% a ) != 0 ) return false; //x = (div - c) / a
    if ( ( (p-b*div) % (a*div) ) != 0 ) return false;// y = (p-b*div) /(a*div)
    return true;
}

int hyperbolicDiophantine ( int a, int b, int c, int d ) {
    int p = a * d + b * c;

    if ( p == 0 ) { //ad + bc = 0
        if ( -c % a == 0 ) return -1; //Infinite solutions (-c/a, k)
        else if ( -b % a == 0 ) return -1; //Infinite solutions (k, -b/a)
        else return 0; //No solution
    }
    else {
        int res = 0;

        //For each divisor of p
        int sqrtn = sqrt ( p ), div;
        for ( int i = 1; i <= sqrtn; i++ ) {
            if ( p % i == 0 ) { //i is a divisor
                //Check if divisors i,-i,p/i,-p/i produces valid solutions
                if ( isValidSolution(a,b,c,p,i) )res++;
                if ( isValidSolution(a,b,c,p,-i) )res++;
                if ( p / i != i ) { //Check whether p/i is different divisor than i
                    if ( isValidSolution(a,b,c,p,p/i) )res++;
                    if ( isValidSolution(a,b,c,p,-p/i) )res++;
                }
            }
        }

        return res;
    }
}

We have two functions here. The first function $\text{isValidSolution}()$ takes input $a,b,c, p, div$ and checks whether we can get a valid solution $(x,y)$ using $div$ as a divisor of $P$.

In line $7$ we start our function to find number of solutions. In line $10$ We check our first case when $AD + BC = 0$. If it is possible to form a valid solution, we return $-1$ in line $11,12$ otherwise $0$ in line $13$.

From line $15$ we start case when $AD + BC \neq 0$. For this case we have to find all divisors of $P$. We know that all divisors come in pairs and one part of that pair lies before $\sqrt{P}$. We we loop till $\sqrt{P}$ to find first part of the pair and process it in line $16$. The second part can be found by dividing $P$ by the first part. We process both these parts ( if second part is different than first part, line $26$ ) and their negative parts by passing them to $\text{isValidSolution}()$ functions. If they are valid we increase our result by 1.

If we are asked to print the solutions, we could do it by modifying the functions above. As long as we understand how the solution works, there should not be any problem in modifying the functions.

Resource

  1. alpertron - Methods to Solve $Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$

Linear Diophantine Equation

Problem

Given the value of integers $A, B$ and $C$ find a pair of integers $(x,y)$ such that it satisfies the equation $Ax + By = C$.

For example, if $A = 2, B = 3$ and $C = 7$, then possible solution of $(x,y)$ for equation $2x + 3y = 7$ would be $(2,1)$ or $(5,-1)$.

The problem above is a type of Diophantine problem. In the Diophantine problem, only integer solutions to an equation are required. Since $Ax + By = C$ is a linear equation, this problem is a Linear Diophantine Problem where we have to find a solution for a Linear Diophantine Equation.

For now, let us assume that $A$ and $B$ are non-zero integers.

Existence of Solution

Before we jump in to find the solution for the equation, we need to determine whether it even has a solution. For example, is there any solution for $2x + 2y = 3$? On the left side we have $2x + 2y$ which is even no matter what integer value of $(x,y)$ is used and on the right side, we have $3$ which is odd. This equation is impossible to satisfy using integer values.

So how do we determine if the equation has a solution? Suppose $g = gcd(A,B)$. Then $Ax + By$ is a multiple of $g$. In order to have a valid solution, since left side of the equation is divisible by $g$, the right side too must be divisible by $g$. Therefore, if $g \not| \ C$, then there is no solution.

Simplifying the Equation

Since both side of equation is divisible by $g$, i.e, $g \ | \ { \ (Ax + By), C \ }$, we can safely divide both side by $g$ resulting in a equivalent equation.

Let $a = \frac{A}{g}$, $b = \frac{B}{g}$ and $c = \frac{C}{g}$. Then,

$$(Ax + By = C) \ \equiv \ (ax + by = c)$$

After simplification, $gcd(a,b)$ is either $1$ or $-1$. If it is $-1$, then we need multiply $-1$ with $a,b$ and $c$ so that $gcd(a,b)$ becomes $1$ and the equation remains unchanged. Why did we make the $gcd(a,b)$ positive? You will find the reason below.

Using Extended Euclidean Algorithm

Recall that in a previous post “Extended Euclidean Algorithm“, we learned how to solve the Bezout’s Identity $Ax + By = gcd(A, B)$. Can we apply that here in any way?

Yes. Using ext_gcd() function, we can find Bezout’s coefficient for $ax + by = gcd(a,b)$. But we need to find solution for $ax + by = c$. Note that $gcd(a,b) = 1$, so when we use ext_gcd() we find a solution for $ax + by = 1$. Let this solution be $(x_1,y_1)$. We can extend this solution to solve our original problem.

Since we already have a solution where $ax_1 + by_1 = 1$, multiplying both sides with $c$ gives us $a(x_1c) + b(y_1c) = c$. So our result is $(x,y) = (x_1c, y_1c)$. This is why we had to make sure that $gcd(a,b)$ was $1$ and not $-1$. Otherwise, multiplying $c$ would have resulted $ax + by = -c$ instead.

Summary of Solution

Here is a quick summary of what I described above. We can find solution for Linear Diophantine Equation $Ax + By = C$ in 3 steps:

  1. No Solution: First check if solution exists for given equation. Let $g = gcd(A,B)$. If $g \not| \ C$ then no solution exists.
  2. Simplify Equation: Let $a = \frac{A}{g}, b = \frac{B}{g}$ and $c = \frac{C}{g}$. Then finding solution for $Ax + By = C$ is same as finding solution for $ax + by = c$. In simplified equation, make sure $GCD(a,b)$ is $1$. If not, multiply $-1$ with $a,b,c$.
  3. Extended Euclidean Algorithm: Use ext_gcd() to find solution $(x_1,y_1)$ for $ax + by = 1$. Then multiply the solution with $c$ to get solution for $ax + by = c$, where $x = x_1 \times c, y = y_1 \times c$.

Let us try few examples.

Example 1: $2x + 3y = 7$

Step $1$: $g = GCD(2,3) = 1$. Since $1$ divides $7$, solution exists.
Step $2$: Since $g$ is already $1$ there is nothing to simplify.
Step $3$: Using ext_gcd() we get $(x,y) = (-1,1)$. But this is for $ax + by = 1$. We need to multiply $7$. So our solution is $(-7,7)$.

$2 \times -7 + 3 \times 7 = -14 + 21 = 7$. The solution is correct.

Example 2: $4x + 10y = 8$

Step $1$: $g = GCD(4,10) = 2$. Since $2$ divides $8$, solution exists.
Step $2$: $a = \frac{4}{2}, b = \frac{10}{2}, c = \frac{8}{2}$. We will find solution of $2x + 5y = 4$.
Step $3$: Using ext_gcd() we get $(x,y) = (-2,1)$. But this is for $ax + by = 1$. We need to multiply $4$. So our solution is $(-8,4)$.

$ax + by = 2 \times -8 + 5 \times 4 = -16 + 20 = 4 = c$.
Also, $Ax + By = 4 \times -8 + 10 \times 4 = -32 + 40 = 8 = C$. The solution is correct. Both $ax + by = c$ and $Ax + By = C$ are satisfied.

Finding More Solutions

We can now find a possible solution for $Ax + By = C$, but what if we want to find more? How many solutions are there? Since the solution for $Ax + By = C$ is derived from Bezout’s Identity, there are infinite solutions.

Suppose we found a solution $(x,y)$ for $Ax + By = C$. Then we can find more solutions using the formula: $( x + k \frac{B}{g}, y – k \frac{A}{g})$, where $k$ is any integer.

Code

Let us convert our idea into code.

bool linearDiophantine ( int A, int B, int C, int *x, int *y ) {
    int g = gcd ( A, B );
    if ( C % g != 0 ) return false; //No Solution

    int a = A / g, b = B / g, c = C / g;
    ext_gcd( a, b, x, y ); //Solve ax + by = 1

    if ( g < 0 ) { //Make Sure gcd(a,b) = 1
        a *= -1; b *= -1; c *= -1;
    }

    *x *= c; *y *= c; //ax + by = c
    return true; //Solution Exists
}

int main () {
    int x, y, A = 2, B = 3, C = 5;
    bool res = linearDiophantine ( A, B, C, &x, &y );

    if ( res == false ) printf ( "No Solution\n" );
    else {
        printf ( "One Possible Solution (%d %d)\n", x, y );

        int g = gcd ( A, B );

        int k = 1; //Use different value of k to get different solutions
        printf ( "Another Possible Solution (%d %d)\n", x + k * ( B / g ), y - k * ( A / g ) );
    }

 return 0;
}

linearDiophantine() function finds a possible solution for equation $Ax + By = C$. It takes in $5$ parameters. $A,B,C$ defines the coefficients of equation and *x, *y are two pointers that will carry our solution. The function will return $true$ if solution exists and $false$ if not.

In line $2$ we calculate $gcd(A,B)$ and in line $3$ we check if $C$ is divisible by $g$ or not. If not, we return $false$.

Next on line $5$ we define $a,b,c$ for simplified equation. On line $6$ we solve for $ax + by = 1$ using ext_gcd(). Then we check if $g < 0$. If so, we multiply $-1$ with $a,b,c$ to make it positive. Then we multiply $c$ with $x,y$ so that our solution satisfies $ax + by = c$. A solution is found so we return true.

In $\text{main}()$ function, we call $\text{linearDiophantine}()$ using $A=2,B=3,C=5$. In line $22$ we print a possible solution. In line $27$ we print another possible solution using formula for more solutions.

$A$ and $B$ with Value $0$

Till now we assumed ${A, B}$ have non-zero values. What happens if they have value $0$?

When Both $A = B = 0$

When both $A$ and $B$ are zero, the value of $Ax + By$ will always be $0$. Therefore, if $C \neq 0$ then there is no solution. Otherwise, any pair of value for $(x,y)$ will act as a solution for the equation.

When $A$ or $B$ is $0$

Suppose only $A$ is $0$. Then equation $Ax + By = C$ becomes $0x + By = C \ \equiv \ By = C$. Therefore $y = \frac{C}{B}$. If $B$ does not divide $C$ then there is no solution. Else solution will be $(x,y) = (k, \frac{C}{B})$, where $k$ is any intger.

Using same logic, when $B$ is $0$, solution will be $(x,y) = ( \frac{C}{A}, k )$.

Coding Pitfalls

When we use $gcd(a,b)$ in our code, we mean the result from Euclidean Algorithm, not what we understand mathematically. $gcd(4,-2)$ is $-2$ according to Euclidean Algorithm whereas it is $2$ in common sense.

Resources

  1. Wiki - Diophantine Equation - https://en.wikipedia.org/wiki/Diophantine_equation
  2. forthright48 - Extended Euclidean Algorithm - https://forthright48.com/2015/07/extended-euclidean-algorithm.html

Extended Euclidean Algorithm

Extended Euclidean Algorithm is an extension of https://forthright48.com/2015/07/euclidean-algorithm.html which finds two things for integer $a$ and $b$:

  1. It finds the value of $GCD(a,b)$.
  2. It finds two integers $x$ and $y$ such that, $ax + by = gcd(a,b)$.

The expression $ax + by = gcd(a,b)$ is known as Bezout’s identity and the pair $(x,y)$ that satisfies the identity is called Bezout coefficients. We will look into Bezout’s identity at the end of this post. For now, just know the name.

How It Works

In Euclidean Algorithm we worked with remainders only. In Extended Euclidean Algorithm (ext_gcd) we will use the quotient and few other extra variables. Suppose we are finding $GCD(240,46)$. Using Euclidean Algorithm the steps for finding $GCD$ would be:

$GCD(240,46) = GCD(46, 240 \ \% \ 46) = GCD(46,10)$
$GCD(46,10) = GCD(10, 46 \ \% \ 10) = GCD(10,6)$
$GCD(10,6) = GCD(6, 10 \ \% \ 6) = GCD(6,4)$
$GCD(6,4) = GCD(4, 6 \ \% \ 4) = GCD(4,2)$
$GCD(4,2) = GCD(2, 4 \ \% \ 2) = GCD(2,0)$
$GCD(2,0) = 2$

Introducing $r$ and $q$

We will slowly move towards ext_gcd algorithm. Let us add two new variables. $r$ represents remainder and $q$ means quotient.

Let $r_0$ be $a$ and $r_1$ be $b$. At each step, we will calculate $r_i$. Let $q_i = \lfloor \frac{r_{i-2}}{ r_{i-1}} \rfloor$. Therefore, $r_i = r_{i-2} – q_i \times r_{i-1}$.

Then the above steps will look like the following:

Index i Quotient $q_i$ Remainder $r_i$
$0$ $240$
$1$ $46$
$2$ $240 / 46 = 5$ $240 – 5 \times 46 = 10$
$3$ $46 / 10 = 4$ $46 – 4 \times 10 = 6$
$4$ $10 / 6 = 1$ $10 – 1 \times 6 = 4$
$5$ $6 / 4 = 1$ $6 – 1 \times 4 = 2$
$6$ $4 / 2 = 2$ $4 – 2 \times 2 = 0$

This table is same as the calculation for Euclidean algorithm except for few extra details. Note that the line before last ( index $5$ ) contains the $GCD(a,b)$.

Introducing $x$ and $y$

We are trying to express $GCD(a,b) = ax + by$. So the variable $x$ and $y$ will hold the coefficients. To be exact we will write each row as terms of $a$ and $b$, i.e, $r_i = ax_i + by_i$.

Initially, $(x_0, y_0) = (1,0)$ and $(x_1, y_1) = (0,1)$. But how do we calculate $(x_i,y_i)$?

We know that $r_i = r_{i-2} – q_i \times r_{i-1}$. We also claimed that $r_i = ax_i + by_i$. By combining this two we get

$r_i = ( ax_{i-2} + by_{i-2} ) – q_i \times ( ax_{i-1} + by_{i-1} )$
$r_i = ax_{i-2} – q_i \times ax_{i-1} + by_{i-2} – q_i \times by_{i-1}$
$r_i = a ( x_{i-2} – q_i \times x_{i-1} ) + b ( y_{i-2} – q_i \times y_{i-1})$
$r_i = a x_i + b y_i$
$\therefore x_i = x_{i-2} – q_i \times x_{i-1} \ \text{and} \ y_i = y_{i-2} – q_i \times y_{i-1}$.

Our new table enhanced with $x$ and $y$ will now look like:

Index Quotient $q_i$ Remainder $r_i$ $x_i$ $y_i$
$0$ $240$ $1$ $0$
$1$ $46$ $0$ $1$
$2$ $240 / 46 = 5$ $240 – 5 \times 46 = 10$ $1 – 5 \times 0 = 1$ $0 – 5 \times 1 = -5$
$3$ $46 / 10 = 4$ $46 – 4 \times 10 = 6$ $0 – 4 \times 1 = -4$ $1 – 4 \times -5 = 21$
$4$ $10 / 6 = 1$ $10 – 1 \times 6 = 4$ $1 − 1 × −4 = 5$ $−5 − 1 × 21 = −26$
$5$ $6 / 4 = 1$ $6 – 1 \times 4 = 2$ $−4 − 1 × 5 = −9$ $21 − 1 × −26 = 47$
$6$ $4 / 2 = 2$ $4 – 2 \times 2 = 0$ $5 − 2 × -9 = 23$ $−26 − 2 × 47 = −120$

Our answer lies on the line before last. $240 \times -9 + 46 \times 47 = 2$.

So all we need to do now is implement these steps in code.

Code

Even though we will be calculating many rows in ext_gcd algorithm, in order to calculate any row we just need information from previous two rows. So we can save memory by simply storing $r_{i-2}, r_{i-1}, x_{i-2}, x_{i-1}, y_{i-2}, y_{i-1}$.

In our code, $x2$ is $x_{i-2}$, $x1$ is $x_{i-1}$ and $x$ is $x_i$. Same style is followed for other variable.

int ext_gcd ( int A, int B, int *X, int *Y ){
    int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    *X = x2; *Y = y2;
    return r2;
}

In line $1$ we define the function. The function ext_gcd() takes 4 parameters. The first two parameter $A$ and $B$ represents the two integers whose gcd we wish to find. The next two parameters *X and *Y are two integer pointers. Our function returns us $GCD(A,B)$ but we also want to find the coefficients $x,y$ such that $ax + by = GCD(A,B)$. So we extract those values using pointers.

In line $2$, we declare all necessary variables. We initiate some variables in line $3$ and $4$. Then a for loop starts in line $5$. We initiate few more variables in first section, $r2$ and $r1$. The loop runs till $r1$ becomes 0. In the last section of for loop, we make transitions of variables, such as $r2$ becomes $r1$ and $r1$ gets the new value $r$.

Inside the for loop we calculate values needed for the current row, $q, r, x, y$.

When the loop finishes, $r1$ contains $0$ and $r2$ is the row before it containing $GCD(A,B)$. So we send $x2,y2$ as coefficients.

Complexity

Same as Euclidean Algorithm.

Uniqueness of Solution

Using ext_gcd we found $(x,y)$ pair which satisfies $ax + by = gcd(a,b)$. But is it unique?

No. Once we find a pair $(x,y)$ using ext_gcd, we can generate infinite pairs of Bezout coefficients using the formula:

$$( x + k \frac{ b } { \text{gcd}(a,b)}, y – k \frac{ a } { \text{gcd}(a,b)} )$$

Using any integer value for $k$ we can generate a different pair of Bezout coefficients $(x,y)$ which will satisfy the Bezout’s identity. Here is why it works:

$a ( x + \frac{ kb } { \text{gcd}(a,b)} ) + b ( y – \frac{ ka } { \text{gcd}(a,b)} )$
$ax + \frac{ kab } { \text{gcd}(a,b)} + by – \frac{ kab } { \text{gcd}(a,b)}$
$ax + by$

As you can see above, the terms with $k$ in them cancel each other out. They don’t change the expression $ax + by$ in any way, therefore, there are infinite pairs of Bezout coefficients.

Smallest Positive Integer of form $ax + by$

We showed that it is possible to write $ax + by = gcd(a,b)$, now we need to find a positive number smaller than $gcd(a,b)$ of form $ax + by$. Is that even possible?

No. $gcd(a,b)$ divides both $a$ and $b$. Therefore, if a number is of form $ax + by$ it will be divisible by $gcd(a,b)$ since $ax$ and $by$ are both divisible by $gcd(a,b)$. And the smallest positive number which is divisible by $gcd(a,b)$ is $gcd(a,b)$ itself.

So $gcd(a,b)$ is the smallest positive number of the form $ax + by$.

Bezout’s Identity

This was mentioned at the beginning of the post. Almost everything related to Bezout’s Identity has been explained. I will still mention them once more for the sake of completeness.

Bézout’s identity (also called Bézout’s lemma) is a theorem in the elementary theory of numbers: let a and b be nonzero integers and let d be their greatest common divisor. Then there exist integers x and y such that $ax + by = d$

In addition,

  • the greatest common divisor d is the smallest positive integer that can be written as $ax + by$
  • every integer of the form ax + by is a multiple of the greatest common divisor d.

Wiki

Bezout’s Lemma simply states that $ax + by = gcd(a,b)$ exists. We need to use the Extended Euclidean Algorithm to find Bezout’s Coefficients.

Coding Pitfalls

Careful about the equation $ax + by = \text{gcd} (a,b)$. Here $\text{gcd}()$ means the result from Euclidean Algorithm, not what we mean mathematically. For example, when $a = 4$ and $b = -2$, Extended Euclidean Algorithm finds solution for $4x – 2y = -2$. According to Euclidean algorithm $gcd(4,-2)$ returns $-2$, though in common sense it should be $2$.

Reference

  1. forthright48 – Euclidean Algorithm – https://forthright48.com/2015/07/euclidean-algorithm.html
  2. Wiki – Extended Euclidean algorithm – https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
  3. Wiki – Bezout’s identity – https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity