Divisibility Problem

**VinceW** · June 28th 2011, 12:12 AM

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!

**Also sprach Zarathustra** · June 28th 2011, 03:16 AM

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)$

**VinceW** · June 28th 2011, 05:53 AM

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}$

**chisigma** · June 28th 2011, 07:53 AM

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$

Thread: Divisibility Problem

LinkBack

Thread Tools

Display

Divisibility Problem

Re: Divisibility Problem

Re: Divisibility Problem

Re: Divisibility Problem

Similar Math Help Forum Discussions

Divisibility problem

Divisibility Problem(2)

Divisibility Problem

A divisibility problem

Divisibility problem