Originally Posted by

**SweatingBear** I just want to know how I can solve this "equation"

when considering it as a linear Diophantine equation.

Now, the Euclidean algorithm is used for calculating the greatest common factor here. But how is that useful and how is it actually used in equations like these?

So, I would appreciate it if you could show me the procedure of using the Euclidean algorithm in order to find a value for x?

Well, your example is perhaps too simple to illustrate the extended Euclidean algorithm, but here goes.

First I'll rewrite your equation to -5x + 3y = 2.

With the extended Euclidean algorithm we find x and y, such that -5x + 3y = gcd(5,3) = 1.

To this end we iterate through a sequence of , ending in

For the setup we start with .

Code:

i -5x_i + 3y_i = d_i q_i
1 1 0 -5
2 0 1 3 -2

In each iteration we divide by to find the quotient .

In the first step that gives a quotient of -2.

Then we subtract q_i times the equation from the previous step.

Code:

i -5x_i + 3y_i = d_i q_i
1 1 0 -5
2 0 1 3 -2
3 1 2 1 3
4 0

That is:

This is repeated until we hit zero, which already happened at step 4.

Now we've found in step 3 that:

Multiply the entire equation by 2 to find:

which is the solution you requested.