Diophantine Equation:

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

Diophantine problems have fewer equations than unknowns and involve finding integers that solve simultaneously all equations. As such sytems of equations define algebraic curves, algebraic surfaces, or, more generally, algebraic sets, their study is a part of algebraic geometry that is called Diophantine Geometry.

Linear Diophantine Equations:

In this blog, we will primarily concentrate on Linear Diophantine Equations.

The Equation:

$$\sum_{n=1}^{n} a_ix_i = N$$

$$\text{Here}\ a_i's\text{ and } N \text{ are known integers while } x_i’s \text{ are the unknown integer}$$

The simplest linear Diophantine equation which is also known as Bezout’s identity takes the form:

$$ax +by=c$$

where a,b,c are given integers and x,y are unknown integers. The solutions are described by the following theorems:

This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor (GCD) of a and b. Additionally, if (x, y) is one solution, then all other solutions can be written as (x + kv, y − ku), where k is any integer, and u and v are the results of dividing a and b by their GCD, respectively.

$$u = \frac{a}{\gcd(a,b)} \quad \text{and} \quad v = \frac{b}{\gcd(a,b)}$$

Proof:
If d is the greatest common divisor of a and b, Bézout's identity tells us that there are integers e and f such that ae + bf = d. If c is a multiple of d, then we can express c as dh for some integer h, and the pair (eh, fh) will be a solution to the equation. Additionally, for any integers x and y, the GCD(d) of a and b will divide the expression ax + by. Therefore, if the equation has a solution, c must be a multiple of d (i.e, d must divide c). If we express a as ud and b as vd, then for any solution (x, y), we have,

$$a(x + kv) + b(y - ku) = ax + by + k(av - bu) = ax + by + k(udv - vdu) = ax + by$$

this shows that if (x , y) are the solutions of the equation then , (x + kv, y - ku) is another solution . Finally, given two solutions such that

$$ax_1 + by_1 = ax_2 + by_2 = c$$

one deduces that,

$$u(x_2 - x_1) + v(y_2 - y_1) = 0$$

As u and v are coprime, Euclid's lemma shows that v divides x2 − x1, and thus that there exists an integer k such that both.

$$x_2 - x_1 = kv, \quad y_2 - y_1 = -ku$$

Therefore,

$$x_2 = x_1 + kv, \quad y_2 = y_1 - ku$$

which completes the required proof.

Analytic Solution:

When a≠0 and b≠0, can be equivalently treated as either of the following:

$$ax \equiv c \, (\text{mod} \, b)$$

$$by \equiv c \, (\text{mod} \, a)$$

This can be written by taking mod with b and then a on both sides of equation respectively.

Without loss of generality, assume that b≠0 and consider the first equation. When a and b are co-prime, the solution to it is given as

$$x \equiv c a^{-1} \, (\text{mod} \, b)$$

$$\text{where }a^{-1}\text{ is the modular inverse of a modulo b}$$

When a and b are not co-prime, values of ax modulo b for all integer x are divisible by g=gcd(a,b) , so the solution only exists when c is divisible by g . In this case, one of solutions can be found by reducing the equation by g:

$$\frac{a}{g} x \equiv \frac{c}{g} \, (\text{mod} \, \frac{b}{g})$$

$$\text{Here }\frac{a}{g} = u \text{ , } \frac{b}{g} = v .$$

By the definition of g , the numbers a/g and b/g are co-prime, so the solution is given explicitly as

$$\begin{cases} x \equiv \left(\frac{c}{g}\right) \left(\frac{a}{g}\right)^{-1} \, (\text{mod} \, \frac{b}{g}) \\ y = \frac{c-ax}{b}\end{cases}$$

Algorithmic solution:

To find one solution of the Diophantine equation with 2 unknowns, you can use the Extended Euclidean algorithm . First assume that a and b are non-negative. When we apply Extended Euclidean algorithm for a and b, we can find their greatest common divisor g and 2 numbers xg and yg such that:

$$a \cdot xg + b \cdot yg = g$$

If c is divisible by g=gcd(a,b) , then the given Diophantine equation has a solution, otherwise it does not have any solution. The proof is straight-forward: a linear combination of two numbers is divisible by their common divisor.

Now supposed that c is divisible by g , then we have:

$$a \cdot xg \cdot \left(\frac{c}{g}\right) + b \cdot yg \cdot \left(\frac{c}{g}\right) = c$$

Therefore one of the solutions of the Diophantine equation is:

$$x_0 = xg \cdot \left(\frac{c}{g}\right)$$

$$y_0 = yg \cdot \left(\frac{c}{g}\right)$$

The above idea still works when a or b or both of them are negative. We only need to change the sign of xo and yo when necessary.

Finally, we can implement this idea as follows (note that this code does not consider the case a = b = 0) :

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

Getting all solutions:

From one solution ( xo , yo ) , we can obtain all the solutions of the given equation.

Let g = gcd(a,b) and let xo , yo be integers which satisfy the following:

$$a \cdot x_0 + b \cdot y_0 = c$$

Now, we should see that adding b/g to xo, and, at the same time subtracting a/g from yo will not break the equality:

$$a \cdot (x_0 + bg) + b \cdot (y_0 - ag) = a \cdot x_0 + b \cdot y_0 + a \cdot bg - b \cdot ag = c$$

Obviously, this process can be repeated again, so all the numbers of the form:

$$\begin{align*} x & = x_0 + k \cdot \left(\frac{b}{g}\right) \\ y & = y_0 - k \cdot \left(\frac{a}{g}\right) \end{align*}$$

are solutions of the given Diophantine Equation.

Moreover, this is the set of all possible solutions of the given Diophantine equation.

Problem :

Statement : Dante is engaged in a fight with "The Savior". Before he can fight it with his sword, he needs to break its shields. He has two guns, Ebony and Ivory, each of them is able to perform any non-negative number of shots.

For every bullet that hits the shield, Ebony deals a units of damage while Ivory deals b units of damage. In order to break the shield Dante has to deal exactly c units of damage. Find out if this is possible.

Take a,b,c as input from the user representing the number of units of damage dealt by Ebony gun and Ivory gun, and the total number of damage required to break the shield, respectively.

Your task is to print "Yes" (without quotes) if Dante can deal exactly c damage to the shield and "No" (without quotes) otherwise.

Solution :

#include<bits/stdc++.h>
using namespace std;
//Function to implement Extended Euclid's algorithm
int extended_euclidean(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_euclidean(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
//Function to calculate modulo inverse of a with respect to m
int modulo_inverse(int a, int m)
{
    int x, y;
    int g = extended_euclidean(a, m, x, y);
    if (g != 1)
    {
        return -1;
    }
    else
    {
        x = (x % m + m) % m;
        return x;
    }
}
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int g = __gcd(a,b); // In built functiom to calculate gcd of two integers
    if(c%g!=0){
        cout << "NO" << endl;
    }
    else{
        //We also need to check if there is a set (x,y) such that x>=0 and y>=0
        int x = (c/g) * modulo_inverse((a/g),(b/g));
        int y = (c - a*x)/b;
        bool solution_exists = false;
        if(x>=0 && y>=0){
            solution_exists = true;
        }
        else{
            if(x<0 && y>=0){
                int x1 = (b/g) * (y/(a/g)) + x;
                if(x1>=0){
                    solution_exists = true;
                }
            }
            if(y<0 && x>=0){
                int y1 = (a/g) * (x/(b/g)) + y;
                if(y1>=0){
                    solution_exists = true;
                }
            }
        }
        if(solution_exists==true){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
}

Linear Diophantine Equations

Diophantine Equation: