Diophantine Equations

A Diophantine equation is simply a polynomial containing two or more unknowns with only integer solutions. Linear Diophantine equations have a form such as \(aX+bY=c\) while exponential Diophantine equations may have exponents such as \(X^n\) or \(Y^n\).

Diophantine equations are of great importance in cryptography and have a lot of interesting properties.

Suppose we have a linear Diophantine equation such as \(2024X + 748Y = C\). In order for \(2024X + 748Y\) to have integer solutions, \(C\) must be some multiple of the greatest common divisor (GCD) of \(2024\) and \(748\).

Using the Euclidean algorithm, which we'll talk about in another post, we can compute that the \(\gcd(2024, 748) = 44\). This means that for \(2024X + 748Y = Q\cdot\gcd(2024, 748)\), there are integer values for \(X\) and \(Y\) for every value of \(Q \in \mathbb{Z}\).

This is a common programming exercise when teaching recursion.

function gcd(a, b)
    b == 0 ? a : gcd(b, a % b)
end

We can also write it more iteratively to match the computations that we will be doing manually.

function gcd(a, b)
    while b > 0
        q = div(a, b)
        r = a - q*b
        a = b
        b = r
    end
    return a
end

Thinking a bit more about this, we know that for \(2024\) and \(748\), the greatest common divisor is \(44\). An interesting fact is that if the greatest common divisor of \(a\) and \(b\) happens to be \(1\), then \(a\) and \(b\) are co-prime or relatively prime meaning that the only number which divides both \(a\) and \(b\) is \(1\). What does this mean about the \(X\) and \(Y\) solutions? We'll get back to that in a moment.

Thinking about \(2024\) and \(748\) again, we can use the "extended Euclidean algorithm" to determine that \(X = -7\) and \(Y = 19\) for the equation, \(2024X + 748Y = \gcd(2024, 748)\), therefore we know that,

\[\begin{aligned} 2024 \cdot (-7) + 748 \cdot (19) = 44 \end{aligned}\]

We can continue scaling up or down the left and right hand sides of (1) and continue finding valid equations with integer solutions, such as

\[\begin{aligned} 2024 \cdot (-7\cdot k) + 748 \cdot (19\cdot k) = 44 \cdot k\text{.} \end{aligned}\]

So, if we wanted to know what the solutions are for \(2024X + 748Y = 88\), since \(2 \cdot 44 = 88\), then we know that \(X =-7\cdot 2 = -14\) and \(Y = 19\cdot 2 = 38\) are solutions. We can keep scaling both sides by some \(k\) and keep finding more equations with integer solutions.

Let's take this a step further with respect to finding solutions to other equations where the right hand side is given.

An Example with \(\gcd \geq 2\) and Solutions

Suppose we have the equation, \(184X + 72Y = 32\). Let's ask some questions.

1. Does the equation have no integer solutions, one integer solution, or many integer solutions?

2. If it has one or many, what are they?

The first thing we want to do is look at the equation,

\[\begin{aligned} 184X + 72Y = \gcd(184, 72) \end{aligned}\]

We start off by looking at \(184 = q \cdot 72 + r\) and iteratively apply the division algorithm to find the greatest common divisor. The way we do this is by dividing \(184\) by \(72\) which yields \(2.555(555)\). We chop off the decimals and subtract \(2 \cdot 72\) from \(184\) to determine the remainder which in this case is 40.

\[\begin{aligned} 184 &= 2 \cdot 72 + 40 \\ \end{aligned}\]

The next step is figure out how to make \(72\) with multiples of \(40\) plus a remainder.

\[\begin{aligned} 184 &= 2 \cdot 72 + 40 \\ 72 &= 1 \cdot 40 + 32 \\ \end{aligned}\]

Having computed that we can multiply 40 and 1 and add 32, we have our next step. We "play the same game" and determine how we can make \(40\) with multiplies of \(32\) plus a remainder. We'll continue doing the same thing until we find a remainder of \(0\).

\[\begin{aligned} 184 &= 2 \cdot 72 + 40 \\ 72 &= 1 \cdot 40 + 32 \\ 40 &= 1 \cdot 32 + \boxed{8} \\ 32 &= 4 \cdot 8 + 0 \\ \end{aligned}\]

Above we show the full computation and box the greatest common divisor. Essentially, when we find a remainder of \(0\), the previous remainder is the greatest common divisor.

Since we know that the greatest common divisor is \(8\), we can then backtrack to find values for \(X\) and \(Y\).

If we let \(a = 184\) and \(b = 72\), then \(40 = a - 2b\). Looking at the next line, we get \(b = 1 \cdot (a - 2b) + 32\) which yields \(32 = -a + 3b\).

\[\begin{aligned} 40 &= a - 2 \cdot b \\ 32 &= -a + 3b\\ \boxed{8} &= (a - 2b) -(-a + 3b) \\ &= 2a - 5b \\ \end{aligned}\]

Therefore, we have our solution with the GCD given as,

\[184 \cdot 2 - 72 \cdot 5 = 8\]

To find a solution to the original equation, \(X\) and \(Y\) must be scaled by some \(q\) where \(q \cdot 8 = 32\). Since \(q = 4\), our solution is given as \(X = 8\) and \(Y = -20\), yielding,

\[184 \cdot 8 - 72 \cdot 20 = 32\text{.} \]

The important point here is that while we'll always be able to find a greatest common divisor for any non-zero integers, the reason we found a solution to the original equation is because the right hand side was a multiple of the GCD.

And, in fact, if there are any solutions, then there are infinite solutions. We can find these with a simple formula.

\[X = X_0 + \frac{b}{\gcd(a, b)}k \text{\ \ \ and \ \ \ } Y = Y_0 - \frac{a}{\gcd(a, b)}k \]

For this specific equation, we have \(X = 2 + 9k\) and \(Y = -5 - 23k\).

When \(k=0\), then \(184 \cdot 2 - 72 \cdot 5 = 8\).

\[\begin{aligned} k &= 0,\ 184⋅2 + 72⋅-5 &= 8 \\ k &= 1,\ 184⋅11 + 72⋅-28 &= 8 \\ k &= 2,\ 184⋅20 + 72⋅-51 &= 8 \\ k &= 3,\ 184⋅29 + 72⋅-74 &= 8 \\ k &= 4,\ 184⋅38 + 72⋅-97 &= 8 \\ k &= 5,\ 184⋅47 + 72⋅-120 &= 8 \\ k &= 6,\ 184⋅56 + 72⋅-143 &= 8 \\ k &= 7,\ 184⋅65 + 72⋅-166 &= 8 \\ &\dots & \end{aligned}\]

We can continue to plug in values of \(k\) to find new solutions where the constant is the GCD, \(8\), and just how we scaled the values of \(x\) and \(y\) to find a solution to the equation where the RHS had the constant value of \(32\), we can scale any of these to find solutions to equations with other multiples of the GCD.

An Example with \(\gcd \geq 2\) and No Solutions

Looking at a similar equation, \(184X + 72Y = 37\), we again have the same GCD, \(8\), for the left-hand side, but since \(37\) isn't a multiple of \(8\), there are no solutions for this equation.

Using Julia

The Julia standard library comes with two functions, gcd and gcdx for the greatest common divisor and the extended Euclidean algorithm. gcd accepts two integers or an array of integers and will compute the \(\gcd\) of all submitted values. The gcdx function takes \(a\) and \(b\) values and returns three values: the \(\gcd\), \(x\) and \(y\).

# Solve AX + BY = K  =>  184X + 72Y = 32
a, b, k = 184, 72, 32
d, x, y = gcdx(a, b)

@show (x0, y0) = div(k, d) .* (x, y)
> (x0, y0) = div(k, d) .* (x, y) = (8, -20)

@show a*x0 + b*y0 == k
> a * x0 + b * y0 == k = true

Another example using Julia where we create functions for all possible solutions. We'll solve the equation, \(9X + 100Y = 1\).

a = 9; b = 100; k = 1;

function f(a, b, k)
    if gcd(a, b) == 1
        d, x0, y0 = gcdx(a, b)
        return t -> x0 + div(b, d)*t, t -> y0 - div(a, d)*t
    end
end

x, y = f(a, b, k)
sols = [ x.(-100:100) y.(-100:100) ]
all(x -> x == one(x), [a*s[1] + b*s[2] for s in eachrow(sols) ])
> true

Here's another example where the \(\gcd > 1\), we'll solve for \(6X + 9Y = 21\).

(a, b, k) = (6, 9, 21)

@show (d, x0, y0) = gcdx(6, 9)
> (d, x0, y0) = gcdx(6, 9) = (3, -1, 1)
@show (x0, y0) = div(k,d) .* (x0, y0)
> (x0, y0) = div(k, d) .* (x0, y0) = (-7, 7)

(x, y) = (t -> x0 + div(b, d)*t, t -> y0 - div(a, d)*t)

Q(t) = x(t), y(t)

Q.(0:4)
> 5-element Vector{Tuple{Int64, Int64}}:
>  (-7, 7)
>  (-4, 5)
>  (-1, 3)
>  (2, 1)
>  (5, -1)

In the last example, the \(\gcd(6, 9) = 3\), which means that the solution \(6\cdot -1 + 9 \cdot 1 = 3\) which isn't what we want. In order to find the solution we want, we scale \(x_0\) and \(y_0\) by div(k, d) which is \(\frac{21}{3} = 7\), yielding the desired initial values of \((-7, 7)\).