Online Math tools

Linear diophantine equation au+bv=c

For a given $a, b \in \mathbb{Z}$ and $c \in \mathbb{N}^{*}$ solve the equation : $$au+bv=c$$

What is a linear diophantine equation ?

Let $a, b \in \mathbb{Z}^{*}$, and $c \in \mathbb{N}^{*}$, the equation : $$ax + by = c \quad (E)$$ with solutions in $\mathbb{Z}^2$ called linear diophantine equation.

Equation $(E)$ had solutions if and only if $\gcd(a,b)$ devide $c$.
If $(u_0, v_0)$ is a special solution of $(E)$ then the set of solutions is : $$S=\left\{\left(u_0 + k \frac{b}{\gcd(a,b)}, v_0 - k\frac{a}{\gcd(a,b)}\right) \ \middle| \ k \in \mathbb{Z} \right\}$$ To solve equation $(E)$ we should first find a Bezout coefficients $a u_0 + b v_0 = \gcd(a, b)$ then solving $(E)$.
Share page