0
$\begingroup$

I would like to calculate all the solutions to this equation using Euclides' algorithm and linear combination after finding the GCD. I suppose it's easy, but I'm a beginner.

$23x + 39y = 2$

$\endgroup$
1
$\begingroup$

Using the euclidean algorithm:

$$23x + 39y = 2$$

We have to find the $\gcd(23,39)$

Therefore,

$$39 = 23*(1) + 16$$ $$23 = 16*(1) + 7$$ $$16 = 7*(2) + 2$$ $$7 = 2*(3) + 1$$ $$2 = 1*(2)$$

so the gcd is $1$.

Now we rewrite:

$$1 = 7 - 3*(2)$$ $$1 = 7-3*(16-7*(2))$$ $$1 = 7*(7) - 3*(16)$$ $$1 = 7*(23-16) - 3*(16)$$ $$1 = 7*(23) - 10*(16)$$ $$1 = 7*(23) - 10*(39-23)$$ $$1 = 17*(23) - 10*(39)$$ So we multiply by $2$, since we get our orignial equation now:

$$2 = 34*(23) - 20*(39)$$

So one solution can be $x = 34$, and $y = -20$

Now generalizing, we find that:

$$x = 34 + \frac{39}{1}n = 34 + 39n$$ $$y = -20 - \frac{23}{1}n = -20 - 23n$$

For all integers $n$.

Look at this for more help:

comment if you have questions

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.