2
$\begingroup$

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

4 Answers 4

6

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

  • 0
    Try `x\equiv y\pmod{z}` to get $x\equiv y\pmod{z}$2012-08-23
4

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

1

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$

1

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