Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How I am supposed to solve questions like

if $\gcd (a,42) =1$ and $168= 3\times 7\times8$ then show that $168$ divides $a^6-1$.

share|cite|improve this question
up vote 6 down vote accepted

By Fermat's theorem, $a^6 \equiv 1 \pmod{7}$ thus $a^6-1 = 7k$ for some $k \in \mathbb{N}$. Likewise, $a^6 = (a^2)^3 \equiv 1 \pmod{3}$ thus $a^6-1 = 3m$. Finally, $a^6-1 = (a-1)(a+1)(a^4+a^2+1)$. One of $a-1$ and $a+1$ is divisible by at least $4$ and the other by at least $2$ for any odd $a$, thus the whole expression is divisible by at least $8$.

share|cite|improve this answer
Try x\equiv y\pmod{z} to get $x\equiv y\pmod{z}$ – robjohn Aug 23 '12 at 9:42

From $(a,42) =1$ and using Fermat's little theorem :

  • $(a,7) =1$ so that $\ a^{7-1}\equiv 1\pmod{7}\quad$ ($7$ divides $a^6-1$)
  • $(a,3) =1$ so that $\ a^{3-1}\equiv 1\pmod{3}\quad$ ($3|(a^2-1)$ and $(a^2-1)|(a^6-1)$)
  • $(a,2) =1$ so that $a$ is odd but for odd $a$ we get $\ (\pm 1)^2\equiv (\pm 3)^2\equiv 1\pmod{8}$ and $a^6\equiv 1\pmod{8}$ (i.e. 8 divides $a^6-1$).

We conclude that $8\cdot 3\cdot 7$ divides $a^6-1$.

share|cite|improve this answer

Using Carmichael Function,

$ \lambda(168)= lcm(\lambda(3),\lambda(7), \lambda(8))$

Now $\lambda(3)=\phi(3)=2$ as 3 is prime,

$\lambda(7)=\phi(7)=6$ as 7 is prime and

$\lambda(8)=\frac{\phi(8)}{2}$ as 8 is of the from $2^n$ where $n$ is a natural number.


$ \lambda(168)= lcm(2, 6 , 2)=6$

So, $a^6≡1(mod\ 3\cdot7\cdot8)$ if $(a,42)=1$,

$=>168|(a^6-1)$ if $(a,42)=1$

share|cite|improve this answer

Hint $\ $ Either apply Carmichael's generalization of Euler-Fermat, or proceed directly via

$$\rm A^{N_j}\equiv 1\ \ (mod\ M_j)\ \Rightarrow\ A^{lcm\ N_j}\equiv 1\ \ (mod\ lcm\ M_j)\ \ \ for\ \ \ \begin{cases} \:N = (2,2,6)\\ \rm M = (8,3,7)\end{cases}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.