# Divisibility Problem

• Jun 28th 2011, 12:12 AM
VinceW
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!
• Jun 28th 2011, 03:16 AM
Also sprach Zarathustra
Re: Divisibility Problem
Quote:

Originally Posted by VinceW
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)$
• Jun 28th 2011, 05:53 AM
VinceW
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}$
• Jun 28th 2011, 07:53 AM
chisigma
Re: Divisibility Problem
Quote:

Originally Posted by VinceW
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$