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

Jump to: navigation, search

## 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$

## Proof

 $(1):\quad$ $\displaystyle 9 n + 8$ $=$ $\displaystyle \paren {6 n + 5} + \paren {3 n + 3}$ $(2):\quad$ $\displaystyle 6 n + 5$ $=$ $\displaystyle \paren {3 n + 3} + \paren {3 n + 2}$ $(3):\quad$ $\displaystyle 3 n + 3$ $=$ $\displaystyle \paren {3 n + 2} + 1$

Thus:

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

Then we have:

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

$\blacksquare$