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

From ProofWiki
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$


Sources