# Solving equation with two unknown integers

• Oct 9th 2012, 12:00 PM
Nora314
Solving equation with two unknown integers
Hi everyone! :)

I have my own comfortable way of solving equations with two unknowns like:

5s + 42t = 1

What I do when I solve this equation, is that I first think: ok, the absolute value of s must be bigger than the absolute value of t in order to get an answer as close to 1 as possible. Than I try t = 1, t = 2... and test with the appropriate s in order to get an answer as close to 1 as possible. The problem is that my method becomes extremely long for big numbers such as

123 456 s + 654 321 t = 3

Does anyone perhaps know some easy to use, good method which would solve these kind of equations efficiently?

Thank you all so much for reading this!
• Oct 9th 2012, 12:09 PM
TheEmptySet
Re: Solving equation with two unknown integers
Quote:

Originally Posted by Nora314
Hi everyone! :)

I have my own comfortable way of solving equations with two unknowns like:

5s + 42t = 1

What I do when I solve this equation, is that I first think: ok, the absolute value of s must be bigger than the absolute value of t in order to get an answer as close to 1 as possible. Than I try t = 1, t = 2... and test with the appropriate s in order to get an answer as close to 1 as possible. The problem is that my method becomes extremely long for big numbers such as

123 456 s + 654 321 t = 3

Does anyone perhaps know some easy to use, good method which would solve these kind of equations efficiently?

Thank you all so much for reading this!

Yes. This can be solve using the Euclidean algorithm. You can also look at this Bézout's identity - Wikipedia, the free encyclopedia

$\displaystyle 42=5(8)+2$
$\displaystyle 5 = 2(2)+1$

Now we can back substitue to get

$\displaystyle 1= 5-2(2)= 5-2(42-5(8))=5(17)+42(-2)$

Note we now have the equation

$\displaystyle \\ 5(17)+42(-2)=1 \\ 5s+42t=1$

So s=17 and t=-2
• Oct 9th 2012, 01:29 PM
MaxJasper
Re: Solving equation with two unknown integers
More s, t:

$\displaystyle \{s,t\}=\{-67,8\},\{-25,3\},\{17,-2\},\{59,-7\},\text{...}$
• Oct 10th 2012, 01:11 AM
Nora314
Re: Solving equation with two unknown integers
Thank you so much for posting an answer!

I took a look at the Wikipedia page you linked to and it makes more sense now. Though, I still have some trouble completely understanding this. I know how to use the Euclidean algorithm so the first part of your post makes sense to me. Though, when you start substituting I get a little bit lost. Like when you write 1 = 5 - 2(2), I understand that you found the number 2 by using the Euclidean algorithm, but I am not sure why you chose to substitute exactly that number in that way.
• Oct 10th 2012, 04:39 AM
TheEmptySet
Re: Solving equation with two unknown integers
Quote:

Originally Posted by Nora314
Thank you so much for posting an answer!

I took a look at the Wikipedia page you linked to and it makes more sense now. Though, I still have some trouble completely understanding this. I know how to use the Euclidean algorithm so the first part of your post makes sense to me. Though, when you start substituting I get a little bit lost. Like when you write 1 = 5 - 2(2), I understand that you found the number 2 by using the Euclidean algorithm, but I am not sure why you chose to substitute exactly that number in that way.

What I was doing was find the GCD of the two numbers. This is sometimes called the reverse Euclidean alogorithm, or extended Euclidean algorithm.
We can always frind the GCD of two numbers this way. There are a few example on this wiki page.

Extended Euclidean algorithm - Wikipedia, the free encyclopedia

This is why the equation only has solutions if

$\displaystyle \gcd(a,b)|c$
• Oct 10th 2012, 02:19 PM
Soroban
Re: Solving equation with two unknown integers
Hello, Nora314!

I have my own way, too.

Quote:

$\displaystyle \text{Solve the Diophantine equation: }\:5s + 42t \:=\: 1$

Solve for the variable with the smaller coefficient.

. . $\displaystyle s \:=\:\frac{\text{-}42t + 1}{5} \quad\Rightarrow\quad s \:=\:\text{-}8t + \frac{1-2t}{5}$ .[1]

Since $\displaystyle s$ is an integer, .$\displaystyle 1-2t$ must be a multiple of 5.

. . Hence: .$\displaystyle 1-2t \:=\:5a\:\text{ for some integer }a.$

Then: .$\displaystyle t \:=\:\frac{\text{-}5a + 1}{2} \quad\Rightarrow\quad t \:=\:\text{-}2a + \frac{1-a}{2}$ .[2]

We see that $\displaystyle a$ must be odd: .$\displaystyle a \:=\:2k-1$

Substitute into [2]: .$\displaystyle t \:=\:\text{-}2(2k-1) + \frac{1-(2k-1)}{2}$
. . which simplifies to: .$\displaystyle t \:=\:\text{-}5k-2$

Substitute into [1]: .$\displaystyle s \:=\:\text{-}8(\text{-}5k-2) + \frac{1-2(\text{-}5k-2)}{5}$
. . which simplifies to: .$\displaystyle s \:=\:42k+17$

Therefore: .$\displaystyle \begin{Bmatrix} s &=& 42k+17 \\ t &=& \text{-}5k -2 \end{Bmatrix}\;\text{ for any integer }k.$