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

Re: Solving equation with two unknown integers

More s, t:

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

Re: Solving equation with two unknown integers

Hello, Nora314!

I have my own way, too.

Solve for the variable with the smaller coefficient.

. . .[1]

Since is an integer, . must be a multiple of 5.

. . Hence: .

Then: . .[2]

We see that must be odd: .

Substitute into [2]: .

. . which simplifies to: .

Substitute into [1]: .

. . which simplifies to: .

Therefore: .