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!

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

Re: Solving equation with two unknown integers

More s, t:

$\displaystyle \{s,t\}=\{-67,8\},\{-25,3\},\{17,-2\},\{59,-7\},\text{...}$

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.

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$

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.$