# Thread: prove that 9 divides n^6+17 when gcd(9,n)=1

1. ## prove that 9 divides n^6+17 when gcd(9,n)=1

I have tried it with inductive method but can't prove it still. Please help.

2. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

Well you should be able to show what you did for the FIRST step of an induction proof. Hard to tell if you are on the right path if you don't show even your first step.

EDIT: Are you required to use induction?

3. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

The divisors of 9 are 1, 3, and 9. Saying that "gcd(9, n)= 1" means that n is not a multiple of 3. So n= 3k+ 1 or 3k+ 2. If n= 3k+ 1, you can write this as $(3k+ 1)^6+ 17$ and if n= 3k+ 2 as $(3k+ 2)^6+ 17$ and then do two inductions on k.

4. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

Originally Posted by HallsofIvy
The divisors of 9 are 1, 3, and 9. Saying that "gcd(9, n)= 1" means that n is not a multiple of 3. So n= 3k+ 1 or 3k+ 2. If n= 3k+ 1, you can write this as $(3k+ 1)^6+ 17$ and if n= 3k+ 2 as $(3k+ 2)^6+ 17$
Look at this page.

And this.

5. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

And here I did that by hand!

(Whenever I see the instructions "using technology", I can't help but think "isn't a pencil technology?" They don't grow on trees!)

6. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

Do you really need the inductions?

\displaystyle \begin{align*} \left( 3\,n + 1 \right) ^6 + 17 &= \left( 3\,n \right) ^6 + 6\,\left( 3\,n \right) ^5 \left( 1 \right) ^1 + 15\,\left( 3\,n \right) ^4 \left( 1 \right) ^2 + 20\,\left( 3\,n \right) ^3\left( 1 \right) ^3 + 15\,\left( 3\,n \right) ^2\left( 1 \right) ^4 + 6\,\left( 3\,n \right) ^1\,\left( 1 \right) ^5 + 1^6 + 17 \end{align*}

Upon simplification you can clearly see the factor of 9...

7. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

Originally Posted by HallsofIvy
And here I did that by hand! (Whenever I see the instructions "using technology", I can't help but think "isn't a pencil technology?" They don't grow on trees!)
That is known as the cellulose graphite method.

8. ## Re: prove that 9 divides n^6+17 when gcd(9,n)=1

Originally Posted by plato
that is known as the cellulose graphite method.
rofl