Results 1 to 8 of 8
Like Tree7Thanks
  • 1 Post By JeffM
  • 4 Post By HallsofIvy
  • 2 Post By Plato

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

  1. #1
    Newbie
    Joined
    Nov 2016
    From
    est
    Posts
    9

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,704
    Thanks
    802

    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?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,104
    Thanks
    2800

    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.
    Thanks from Plato, topsquark, JeffM and 1 others
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,149
    Thanks
    2603
    Awards
    1

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

    Quote Originally Posted by HallsofIvy View Post
    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.
    Thanks from topsquark and JeffM
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,104
    Thanks
    2800

    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!)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,817
    Thanks
    1924

    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...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,149
    Thanks
    2603
    Awards
    1

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

    Quote Originally Posted by HallsofIvy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,704
    Thanks
    802

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

    Quote Originally Posted by plato View Post
    that is known as the cellulose graphite method.
    rofl
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: Oct 25th 2012, 05:19 AM
  2. Prove that 5 divides at least one of {m,n,p}.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jul 27th 2012, 10:01 AM
  3. Prove using induction on n that 3 divides (4^n)+5
    Posted in the Number Theory Forum
    Replies: 16
    Last Post: Jul 2nd 2011, 06:38 AM
  4. Prove that ab divides c.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Mar 3rd 2010, 09:42 AM
  5. Prove that gcd(a,b) divides lcm[a,b]
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Feb 15th 2010, 07:44 PM

/mathhelpforum @mathhelpforum