How would one solve a linear equation in two integer variables?

Question

For example, how would I find integers $a$ and $b$ that satisfy the following equation?

$$5a - 12b = 13$$

I always resorted to trial and error when doing something like this and more often than not I would finally reach my answer. But for this one I just kept going and going to no avail. So it finally brought about the concern that trial and error wasn't always going to work.

So what would be the best way to get two integer solutions to the above equation?

Answer 1

Guide:

Since we know that $5$ and $12$ are coprime, use Eucliean Algorithm to find $x, y \in \mathbb{Z}$ such that $$5x+12y = 1$$

After which, multiply the equation by $13$.

In general to solve for $$Aa-Bb=C$$ where $A,B, C$ is given.

Use euclidean algorithm to find $\gcd(A,B)=D$, if $D$ doesn't divide $C$, then there is no integer solutions. Otherwise, express $D$ as a linear combination of $A$ and $B$ and multiply the equation to get a particular solution.

Answer 2

Use the Euclidean Algorithm to find the gdc of $5$ and $12$. $$12=5\times2+2$$ $$5=2\times2+1$$ Then apply the extended Euclidean Algorithm, (do the initial algorithm in reverse with back-substitution) $$1=5-2\times2$$ $$1=5-2\times(12-5\times2)$$ $$1=5\times5-2\times12$$ Then multiply throughout by $13$ $$13=65\times5-26\times12$$ This gives you a particular solution $(a,b)=(65,26)$. The general form of any solution of a Linear Diophantine equation is given as follows $$a=a_0-\frac{12}{d}t,\ b=b_0-\frac{5}{d}t$$ Where $t$ is any integer and $d$ is the greatest common divisor of $5$ and $12$ which is $1$

Answer 3

Since 5 and 12 are relatively prime you are able to find two integers such as 3 and -7 such that $$ 3\times 12 -7\times 5 =1 $$

Upon multiplying by $13$, you get $$39\times 12 -91\times 5 =13$$

Answer 4

The Euclidean algorithm is best for large numbers, but for a small example like this, trial and error, combined with a little modular arithmetic works just fine, and is less work. Reducing $5a−12b=13$ modulo $12$, we have $a\equiv 1 \pmod{12},$ and $a\equiv 5 \pmod{12},$ by trial. Then it's clear that $a=5,$ $b=1$ is a solution.

Alternatively, we might reduce modulo $5,$ getting $3b \equiv 3 \pmod{5},$ so $b\equiv 1 \pmod{5},$ and again we find that $b=1$ gives $a=5.$

Answer 5

Write the equation in terms of another variable:

$$5a-12b=13 \iff a=\frac{13}{5}+\frac{12}{5}b$$

Now you just need to see that $13+12b \equiv 0 \pmod{5} \iff 12(b+1)+1 \equiv 0 \pmod{5} \Rightarrow b + 1= 5x +2,\, \forall x\in \mathbb{Z}$.

So the solutions have the form (by substituting $b=5x+1$ in the original equation)

$$a=12x+5, b = 5x+1, \, \forall x\in \mathbb{Z}$$

Now you can find as many integer solutions as you want.

Answer 6

The method here is to repeatedly putting new variables:

$5a-12b=13 \Leftrightarrow 5a=12b+13 \Leftrightarrow a=\frac{12b+13}{5}=2b+2+\frac{2b+3}{5}$

Put $\frac{2b+3}{5}=c$ with $c$ is an integer (because $a$ or $2b+2+c$ is an integer)

$\Leftrightarrow 2b+3=5c \Leftrightarrow 2b-5c=-3$ or $b=\frac{5c-3}{2}$.

$b$ is an integer $\Leftrightarrow 5c-3$ is divisible by $2 \Leftrightarrow c$ is an odd number.

Put $c=2k+1$ ($k$ is an integer), we have $b= \frac{5c-3}{2}=\frac{5(2k+1)-3}{2}=5k+1.$

$\Rightarrow a=\frac{12b+13}{5}=\frac{12(5k+1)+13}{5}=12k+5$.

The equation has infinite solutions: $\begin{cases}a=12k+5\\b=5k+1\end{cases}$, $\forall k\in \mathbb{Z}$.

Trial-and-error can still be applied for any numbers multiplied by $a$, $b$, as long as their $GCD$ is $1$.

For example this ugly equation: $73a+89b=3$. You won't have time to do trial-and-error, so here's a way to make it smaller:

• Put $a=\frac{3-89b}{73}=\frac{3-16b}{73}-b$, then $\frac{3-16b}{73} \in \mathbb{Z}$ because $a,b\in \mathbb{Z}$.

• Put $c=\frac{3-16b}{73}$, then $3-16b=73c$ or $b=\frac{3-73c}{16}=\frac{3-9c}{16}-4c$, then $\frac{3-9c}{16} \in \mathbb{Z}$ because $b,c\in \mathbb{Z}$.

• Put $d=\frac{3-9c}{16}$, then $3-9c=16d$ or $c=\frac{3-16d}{9}=\frac{3-7d}{9}-d$, then $\frac{3-7d}{9} \in \mathbb{Z}$ because $c,d\in \mathbb{Z}$.

• Put $e=\frac{3-7d}{9}$, then $3-7d=9e$ or $d=\frac{3-9e}{7}=\frac{3-2e}{7}-e$, then $\frac{3-2e}{7} \in \mathbb{Z}$ because $d,e\in \mathbb{Z}$.

• Put $f=\frac{3-2e}{7}$, then $3-2e=7f$ or $e=\frac{3-7f}{2}=\frac{1-f}{2}+1-3f$, then $\frac{1-f}{2} \in \mathbb{Z}$ because $e,f\in \mathbb{Z}$.

$e$ would be an integer if and only if $f=2k+1$ or $f$ odd

$\Rightarrow e=-7k-2$

$\Rightarrow d=9k+3$

$\Rightarrow c=-16k-5$

$\Rightarrow {\begin{cases}a=-89k-28\\b=73k+23\end{cases}}$