Euclidean Algorithm/Examples/272 and 1479

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Euclidean Algorithm

The GCD of $272$ and $1479$ is:

$\gcd \set {272, 1479} = 17$


Proof

\(\text {(1)}: \quad\) \(\ds 1479\) \(=\) \(\ds 5 \times 272 + 119\)
\(\text {(2)}: \quad\) \(\ds 272\) \(=\) \(\ds 2 \times 119 + 34\)
\(\text {(3)}: \quad\) \(\ds 119\) \(=\) \(\ds 3 \times 34 + 17\)
\(\text {(4)}: \quad\) \(\ds 34\) \(=\) \(\ds 2 \times 17\)

Thus:

$\gcd \set {272, 1479} = 17$

$\blacksquare$


Sources