Euclidean Algorithm/Examples/9n+8 and 6n+5

Examples of Use of Euclidean Algorithm

The GCD of $9 n + 8$ and $6 n + 5$ is found to be:

$\gcd \set {9 n + 8, 6 n + 5} = 1$

Hence:

$2 \paren {9 n + 8} - 3 \paren {6 n + 5} = 1$

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

$\ds 9 n + 8$

$=$

$\ds \paren {6 n + 5} + \paren {3 n + 3}$

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

$\ds 6 n + 5$

$=$

$\ds \paren {3 n + 3} + \paren {3 n + 2}$

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

$\ds 3 n + 3$

$=$

$\ds \paren {3 n + 2} + 1$

Thus:

$\gcd \set {9 n + 8, 6 n + 5} = 1$

Then we have:

$\ds 1$

$=$

$\ds \paren {3 n + 3} - \paren {3 n + 2}$

from $(3)$

$\ds $

$=$

$\ds \paren {3 n + 3} - \paren {\paren {6 n + 5} - \paren {3 n + 3} }$

from $(2)$

$\ds $

$=$

$\ds 2 \paren {3 n + 3} - \paren {6 n + 5}$

$\ds $

$=$

$\ds 2 \paren {\paren {9 n + 8} - \paren {6 n + 5} } - \paren {6 n + 5}$

from $(1)$

$\ds $

$=$

$\ds 2 \paren {9 n + 8} - 3 \paren {6 n + 5}$

$\blacksquare$

1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $2$: Some Properties of $\Z$: Exercise $2.3$