Answer to Question #177796 in Discrete Mathematics for James Johnson

Question

Use the Euclidean algorithm to find gcd(2074, 2457) = d.

Answer 1

Let us use the Euclidean algorithm to find $d=\gcd(2074, 2457)$:

$2457=2074\cdot1+383\\ 2074=383\cdot 5+159\\ 383=159\cdot 2+65\\ 159=65\cdot2+29\\ 65=29\cdot 2+7\\ 29=7\cdot4+1\\ 7=7\cdot1+0$

We conclude that $d=\gcd(2074, 2457)=1.$