Euclidean Algorithm/Examples/119 and 272

Examples of Use of Euclidean Algorithm

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

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

Integer Combination

$6$ can be expressed as an integer combination of $119$ and $272$:

$17 = 7 \times 119 - 3 \times 272$

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\)