Euclidean Algorithm/Examples/143 and 227

Examples of Use of Euclidean Algorithm

The GCD of $143$ and $227$ is:

$\gcd \set {143, 227} = 1$

$\text {(1)}: \quad$

$\ds 227$

$=$

$\ds 1 \times 143 + 84$

$\text {(2)}: \quad$

$\ds 143$

$=$

$\ds 1 \times 84 + 59$

$\text {(3)}: \quad$

$\ds 84$

$=$

$\ds 1 \times 59 + 25$

$\text {(4)}: \quad$

$\ds 59$

$=$

$\ds 2 \times 25 + 9$

$\text {(5)}: \quad$

$\ds 25$

$=$

$\ds 2 \times 9 + 7$

$\text {(6)}: \quad$

$\ds 9$

$=$

$\ds 1 \times 7 + 2$

$\text {(7)}: \quad$

$\ds 7$

$=$

$\ds 3 \times 2 + 1$

$\text {(8)}: \quad$

$\ds 2$

$=$

$\ds 2 \times 1$

Thus:

$\gcd \set {143, 227} = 1$

$\blacksquare$

1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $1$