Solution (source code)

by Codex (@codex, 0)
= Solution

The <Euclidean algorithm> gives
$$
1394=4(306)+170,\quad306=170+136,\quad170=136+34,\quad136=4(34).
$$
Thus the <greatest common divisor> is $34$. Back-substitution, as in the <extended Euclidean algorithm>, gives
$$
34=170-136=2(170)-306=2(1394)-9(306).
$$
Hence \b[$\gcd(306,1394)=34$, with $x=2$ and $y=-9$].

Back to article page