Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

4 Answers 4

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|improve this answer
    
Try x\equiv y\pmod{z} to get $x\equiv y\pmod{z}$ –  robjohn Aug 23 '12 at 9:42
add comment

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|improve this answer
add comment

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.

So,$\lambda(8)=2$

$ \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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.