Linear Diophantine equations

Equations of the form $\sum_i a_i x_i = 0$ where the $x_i$’s are integer unknowns are called linear Diophantine equations. Their integer solutions can be computed using greatest common denominator (GCD) tricks. In this post, we go over a few basic types of such equations and their integer solutions.

$ax+by = t$

Theorem: This equation has an integer solution $\Leftrightarrow \gcd(a,b) \mathrel\vert t$.

Proof (“$\Rightarrow$”): Assume an integer solution $(x_0, y_0)$ exists when $\gcd(a,b) \nmid t$. Since $\gcd(a,b)$ divides both $a$ and $b$, it divides any linear combination of them, including $ax_0 + by_0 = t$, which implies it divides $t$. Contradiction.

Proof (“$\Rightarrow$”): If $\gcd(a,b) = 1$, then an integer solution $x_0,y_0$ can be obtained using the Extended Eucliden algorithm, which finds $(u,v)$ such that $au + bv = \gcd(a,b)$. The solution is: \begin{align} x_0 &= u\cdot t / \gcd(a,b)\\\ y_0 &= v\cdot t / \gcd(a,b) \end{align} This is because $ax_0 + ay_0 = (au + bv) \frac{t}{\gcd(a,b)} = \gcd(a,b) \frac{t}{\gcd(a,b)} = t$.

Theorem: When $\gcd(a,b) \mathrel\vert t$, if $(x_0, y_0)$ is an integer solution to such an equation, then all integer solutions can be characterized as: \begin{align} x &= x_0 - k b/\gcd(a,b)\\\ y &= y_0 + k a/\gcd(a,b) \end{align} Here, $k$ is an arbitrary integer and either $a\ne 0$ or $b\ne 0$ (since otherwise $\gcd(a,b) = 0$ and $\gcd(a,b)\mathrel\vert t$ implies $t=0$, which means all integers $(x,y)$ are solutions).

Proof: First, one can easily verify that the proposed $(x,y)$ are indeed solutions that satisfy $ax+by=t$: \begin{align} ax + by &= ax_0 + kab / \gcd(a,b) + by_0 - kab/gcd(a,b)\\ &= ax_0 + by_0 = t \end{align} The more difficult part is to argue that every solution has this form! Assume $a\ne 0$ since the other $b\ne 0$ case is symmetric. Assume $(x,y)$ to be an integer solution and note that, since $(x_0, y_0)$ is a solution, this means: \begin{align} a(x-x_0) + b(y - y_0) &= 0\Leftrightarrow\\ a(x - x_0) &= b(y_0 - y)\Leftrightarrow\\ \frac{a}{\gcd(a,b)}(x-x_0) &= \frac{b}{\gcd(a,b)} (y_0 - y) \end{align} This implies $\frac{a}{\gcd(a,b)} \mathrel\vert \frac{b}{\gcd(a,b)} (y - y_0)$. Since $\gcd(\frac{a}{\gcd(a,b)}, \frac{b}{\gcd(a,b)}) = 1$¹, this means $\frac{a}{gcd(a,b)} \mathrel\vert (y-y_0)$, which means $\exists k$ such that: \begin{align} a/\gcd(a,b) \cdot k &= (y-y_0)\Leftrightarrow\\ y &= y_0 + k a / \gcd(a,b) \end{align} Next, substitute $y$ in $a(x-x_0) = b(y_0 - y)$, to get: \begin{align} a(x-x_0) &= b(y_0 - y_0 - k a / \gcd(a,b))\Leftrightarrow\\ x - x_0 &= (- b k a / \gcd(a,b)) / a\\ &= x_0 - k b / \gcd(a,b) \end{align} Note that since $a\ne 0$, we are allowed to divide by $a$ above.

$ax+by = 0$

In this case, since $x_0 = 0$ and $y_0 = 0$ is one integer solution, all integer solutions are of the form: \begin{align} x &= -kb/\gcd(a,b)\\
y &= ka/\gcd(a,b) \end{align}

$ax+by+cz = t$

Theorem: This equation has an integer solution $\Leftrightarrow \gcd(a,b,c) \mathrel\vert t$.

Proof (“$\Rightarrow$”): Proceeds analogously to the $ax+by = t$ case before.

Proof (“$\Leftarrow$”): We will generalize the proof from the $ax+by = t$ case before.

$\gcd(a,b,c) \mathrel\vert t \Rightarrow \gcd(a, \gcd(b, c)) \mathrel\vert t \Rightarrow ax + \gcd(b,c)w = t$ has an integer solution $(x_0, w_0)$.

Let $\gcd(b,c) = d$. We know $\exists (y_0, z_0)$ such that: \begin{align} b y_0 + c z_0 = d \end{align} Replacing in the previous equation, we have: \begin{align} ax_0 + \gcd(b,c)w_0 &= t\Leftrightarrow\\ ax_0 + dw_0 &= t\Leftrightarrow\\ ax_0 + (b y_0 + c z_0) w_0 &= t\Leftrightarrow\\ ax_0 + b w_0 y_0 + c w_0 z_0 &= t \end{align} Thus, an integer solution is $(x_0, y_0 w_0, z_0 w_0)$.

Theorem (from Sec 6.2 in ²): In this case, if $(x_0, y_0, z_0)$ is one integer solution, then all integer solutions are of the form: \begin{align} x &= x_0 + m b / \gcd(a,b) - \ell c / \gcd(a,c)\\
y &= y_0 + k c / \gcd(b,c) - m a / \gcd(a, b)\\
z &= z_0 + \ell a / \gcd(a, c) - k b / \gcd(b, c) \end{align} Here, $m,\ell,k$ are integers and at least one of $a,b$ or $c$ are $\ne 0$.

$ax+by+cz = 0$

In this case, all integer solutions are of the form: \begin{align} x &= m b / \gcd(a,b) - \ell c / \gcd(a,c)\\
y &= k c / \gcd(b,c) - m a / \gcd(a, b)\\
z &= \ell a / \gcd(a, c) - k b / \gcd(b, c) \end{align} Here, $m,\ell,k$ are arbitrary integers.

This could also be simplified in terms of the lowest common multiple (LCM), since $a b = \gcd(a,b) \lcm(a,b)\Rightarrow b / \gcd(a,b) = \lcm(a,b) / a$: \begin{align} x &= m \lcm(a,b) / a - \ell \lcm(a,c) / a = \frac{m\lcm(a,b) - \ell\lcm(a,c)}{a}\\
y &= k \lcm(b,c) / b - m \lcm(a, b) / b = \frac{k\lcm(b,c) - m\lcm(a,b)}{b}\\
z &= \ell \lcm(a, c) / c - k \lcm(b, c) / c = \frac{\ell\lcm(a,c) - k\lcm(b,c)}{c} \end{align}

An example

In a Catalano-Fiore vector commitment (VC)³ of size $n=3$, collision resistance is implied by the fact that the following equation with $(\ell+1)$-bit primes $e_1,e_2,e_3$ does not have any $\ell$-bit integer solutions:

\[e_2 e_3 v_1 + e_1 e_3 v_2 + e_1 e_2 v_3 = 0\]

The only integer solutions given by the formula above are at least $\ell+1$ bit wide: \begin{align} %x &= \frac{m \lcm(e_2 e_3, e_1 e_3) - \ell\lcm(e_2 e_3, e_1 e_2)}{e_2 e_3}\\
% &= \frac{m e_1 e_2 e_3 - \ell e_1 e_2 e_3}{e_2 e_3} = (m-\ell)e_1\\
x &= m (e_1 e_3) / \gcd(e_2 e_3, e_1 e_3) - \ell (e_1 e_2) / \gcd(e_2 e_3, e_1 e_2) =\\
&= m (e_1 e_3) / e_3 - \ell (e_1 e_2) / e_2 = m’ e_1\ (\text{where}\ m’=m-\ell)\\
y &= k’ e_2\\
z &= \ell’ e_3 \end{align}

$\sum_{i\in[n]} a_i x_i = t$

Theorem: This equation has an integer solution $\Leftrightarrow \gcd(a_1, \dots, a_n) \mathrel\vert t$.

Proof: The “$\Rightarrow$” direction proceeds as before.

The “$\Leftarrow$” direction proceeds by induction. The statement $P(n)$ being proved by induction is:

\[\forall a_i\in \mathbb{Z}, \gcd(a_1, \dots, a_n) \mathrel\vert t\Rightarrow \sum_{i\in[n]} a_i x_i = t\ \text{has an integer solution.}\]

We prove $P(n)$ is true for all $n \ge 2$. First, $P(2)$ is clearly true as we’ve shown before. Second, we must show $P(n) \Rightarrow P(n + 1)$. This we do analogously to the proof for $n=3$ from before. Let $d = \gcd(a_1, \dots, a_n)$. We know that $\gcd(a_1, \dots, a_{n+1}) = \gcd(d, a_{n+1})$. Since $d \mathrel| t$ (because $P(n)$ is true), this implies $\exists$ integers $s_0, w_0$ such that: \begin{align} d s_0 + a_{n+1} w_0 = t \Leftrightarrow \end{align}

Since $P(n)$ is true, we know there exist integers $s_1,\dots, s_n$ such that: \begin{align} \sum_{i\in[n]} a_i s_i = d \end{align}

Replacing $d$ in the previous equation, we get: \begin{align} d s_0 + a_{n+1} w_0 &= t \Leftrightarrow\\
\left(\sum_{i\in[n]} a_i s_i\right) s_0 + a_{n+1} w_0 &= t \end{align} Thus, a solution can be found by setting $x_i = s_0 s_i,\forall i\in[n]$ and $x_{n+1} = w_0$.