Euclidean Algorithm/Examples/306 and 657

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Euclidean Algorithm

The GCD of $306$ and $657$ is:

$\gcd \set {306, 657} = 9$


Proof

\(\text {(1)}: \quad\) \(\ds 657\) \(=\) \(\ds 2 \times 306 + 45\)
\(\text {(2)}: \quad\) \(\ds 306\) \(=\) \(\ds 6 \times 45 + 36\)
\(\text {(3)}: \quad\) \(\ds 45\) \(=\) \(\ds 1 \times 36 + 9\)
\(\text {(4)}: \quad\) \(\ds 36\) \(=\) \(\ds 4 \times 9\)

Thus:

$\gcd \set {306, 657} = 9$

$\blacksquare$


Sources