Results 1 to 4 of 4

Thread: Divisibility Problem

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Divisibility Problem

    Show that $\displaystyle a^6 - 1$ is divisible by $\displaystyle 168$ whenever $\displaystyle (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 $\displaystyle a^6 \equiv 1 \pmod {7}$, $\displaystyle a \equiv 1 \pmod {2}$, and
    $\displaystyle a^2 \equiv 1 \pmod {3}$. We can raise the powers and combine to get $\displaystyle a^6 \equiv 1 \pmod {42}$. I'm
    not sure how to take it further and get to $\displaystyle 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 $\displaystyle a^6 - 1$ is divisible by $\displaystyle 168$ whenever $\displaystyle (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 $\displaystyle a^6 \equiv 1 \pmod {7}$, $\displaystyle a \equiv 1 \pmod {2}$, and
    $\displaystyle a^2 \equiv 1 \pmod {3}$. We can raise the powers and combine to get $\displaystyle a^6 \equiv 1 \pmod {42}$. I'm
    not sure how to take it further and get to $\displaystyle a^6 \equiv 1 \pmod {168}$. Thanks!
    $\displaystyle \gcd(a,42)=1$ then: $\displaystyle 2 \nmid a, 3 \nmid a, 7 \nmid a$.

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


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

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

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

    If $\displaystyle a\equiv b(\mod m)$ , $\displaystyle a\equiv b(\mod n)$ and $\displaystyle \gcd(n,m)=1 $then: $\displaystyle 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 $\displaystyle a^2 \equiv 1 \pmod {8}$. Fermat's theorem gives $\displaystyle 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
    6

    Re: Divisibility Problem

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

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

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

    Kind regards

    $\displaystyle \chi$ $\displaystyle \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: Dec 8th 2011, 07:24 PM
  2. Divisibility Problem(2)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 18th 2010, 02:02 PM
  3. Divisibility Problem
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: Sep 17th 2010, 06:40 AM
  4. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 27th 2010, 05:28 PM
  5. Divisibility problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 28th 2010, 03:42 PM

/mathhelpforum @mathhelpforum