Originally Posted by

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

$\displaystyle 3k + 2 = 5p + 4$

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 $\displaystyle -5x_i + 3y_i = d_i$, ending in $\displaystyle d_i=0$

For the setup we start with $\displaystyle x_1=1, y_1=0, x_2=0, y_2=1$.

Code:

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

In each iteration we divide $\displaystyle d_{i-1}$ by $\displaystyle d_i$ to find the quotient $\displaystyle q_i$.

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:

$\displaystyle x_{i+1}=x_{i-1} - q_i x_i$

$\displaystyle y_{i+1}=y_{i-1} - q_i y_i$

$\displaystyle d_{i+1}=d_{i-1} - q_i d_i$

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

Now we've found in step 3 that:

$\displaystyle -5 \cdot 1 + 3 \cdot 2 = 1$

Multiply the entire equation by 2 to find:

$\displaystyle -5 \cdot 2 + 3 \cdot 4 = 2$

which is the solution you requested.