Yes. This can be solve using the Euclidean algorithm. You can also look at this Bézout's identity - Wikipedia, the free encyclopedia
Now we can back substitue to get
Note we now have the equation
So s=17 and t=-2
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
Now we can back substitue to get
Note we now have the equation
So s=17 and t=-2
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
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: .