Euclidean Algorithm/Examples/119 and 272/Proof

From ProofWiki
Jump to navigation Jump to search

Examples of Use of Euclidean Algorithm

The GCD of $119$ and $272$ is found to be:

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


Proof

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


Thus:

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

$\blacksquare$