Divisibility Problem

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

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