4
$\begingroup$

I already got idea of solving gcd with three numbers. But I am wondering how to solve the extended Euclidean algorithm with three, such as:

47x + 64y + 70z = 1

Could anyone give me a hint? Thanks a lot.

$\endgroup$
  • $\begingroup$ In your example, you could just let $z=0$, and solve $47x+64y=1$. $\endgroup$ – Gerry Myerson Apr 1 '14 at 12:17
4
$\begingroup$

Notice that $gcd(x,y,z)=gcd(x,gcd(y,z))$. First we find $a$, $b$ such that $gcd(x,gcd(y,z))=ax+bgcd(y,z)$, then $c$, $d$ such that $gcd(y,z)=cy+dz$. Finally we obtain $gcd(x,y,z)=ax+bcy+bdz$.

$\endgroup$
2
$\begingroup$

This problem can be generalized to finding $x$, $y$, and $z$ in the equation $ax + by + cz = n$ where $a$, $b$, $c$, and $n$ are given and $\gcd(a, b, c) = 1$. If $\gcd(a, b, c) \nmid n$, then there is no solution, otherwise, we can divide both sides by $\gcd(a, b, c)$.

The method to solve for $x$, $y$, and $z$ is essentially the same as solving for $x$ and $y$ given a fixed value of $z$. The equation given is:

$ax + by + cz = n$

This reduces to:

$ax + by = n - cz$

The only restriction on $z$ is that $\gcd(a, b) \mid (n - cz)$.

If we take this equation $\mod b$, then we get:

$ax \equiv n - cz \mod b$

Let $a^{-1} \cdot a \equiv 1 \mod b$. (It is possible to find $a^{-1}$ by using the Extended Euclidean Algorithm on $a$ and $b$).

$a^{-1} \cdot ax \equiv x \equiv a^{-1} \cdot (n - cz) \mod b$

We now have a value for $x$ given $z$. To find the value of $y$ given $z$, all we need to do is solve another equation:

$by = n - ax - cz$

Since $ax \equiv n - cz \mod b$, $n - ax - cz \equiv 0 \mod b$ and $b \mid (n - ax - cz)$. Therefore:

$y = \frac{n - ax - cz}{b}$

$\endgroup$
1
$\begingroup$

If you find $x'$ and $y'$ such that $47x' + 64y' = gcd(47,64)$ then solve $gcd(47,64)\cdot t + 70z = 1$. Then $x = x't$ and $y = y't$. This works since $gcd(47,64,70) = gcd(gcd(47,64),70)$.

$\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.