Results 1 to 4 of 4

Math Help - Divisibility Problem

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Divisibility Problem

    Show that a^6 - 1 is divisible by 168 whenever (a, 42) = 1.

    This is on the chapter on Wilson's Theorem and Fermat's Little Theorem.

    With Fermat's Little Theorem, we can see a^6 \equiv 1 \pmod {7}, a \equiv 1 \pmod {2}, and
    a^2 \equiv 1 \pmod {3}. We can raise the powers and combine to get a^6 \equiv 1 \pmod {42}. I'm
    not sure how to take it further and get to a^6 \equiv 1 \pmod {168}. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Divisibility Problem

    Quote Originally Posted by VinceW View Post
    Show that a^6 - 1 is divisible by 168 whenever (a, 42) = 1.

    This is on the chapter on Wilson's Theorem and Fermat's Little Theorem.

    With Fermat's Little Theorem, we can see a^6 \equiv 1 \pmod {7}, a \equiv 1 \pmod {2}, and
    a^2 \equiv 1 \pmod {3}. We can raise the powers and combine to get a^6 \equiv 1 \pmod {42}. I'm
    not sure how to take it further and get to a^6 \equiv 1 \pmod {168}. Thanks!
    \gcd(a,42)=1 then: 2 \nmid a, 3 \nmid a, 7 \nmid a.

    2 \nmid a \rightarrow  a^2\equiv 1(\mod8)\rightarrow a^6\equiv 1(\mod8)


    3 \nmid a \rightarrow(Fermat's theorem) a^2\equiv 1(\mod3\rightarrow ) a^6\equiv 1(\mod3)

    7 \nmid a \rightarrow(Fermat's theorem)  a^6\equiv 1(\mod7)

    Now, use the following lemma to make the final conclusion:

    If a\equiv b(\mod m) , a\equiv b(\mod n) and \gcd(n,m)=1 then: a\equiv b(\mod mn)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Re: Divisibility Problem

    Your steps match mine exactly, except I don't understand where you got a^2 \equiv 1 \pmod {8}. Fermat's theorem gives a \equiv 1 \pmod {2}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Divisibility Problem

    Quote Originally Posted by VinceW View Post
    Your steps match mine exactly, except I don't understand where you got a^2 \equiv 1 \pmod {8}. Fermat's theorem gives a \equiv 1 \pmod {2}
    If a \nmid 2 then a=2 n +1 is an odd number. Now is...

    a^{2}-1= 4 n (n+1) \implies \frac{a^{2}-1}{8}= \frac{n\ (n+1)}{2}

    ... and that means that (a^{2}-1) | 8 ...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 8th 2011, 07:24 PM
  2. Divisibility Problem(2)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 18th 2010, 02:02 PM
  3. Divisibility Problem
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: September 17th 2010, 06:40 AM
  4. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2010, 05:28 PM
  5. Divisibility problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 28th 2010, 03:42 PM

/mathhelpforum @mathhelpforum