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$.
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$.
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$.
From $(a,42) =1$ and using Fermat's little theorem :
We conclude that $8\cdot 3\cdot 7$ divides $a^6-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$
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}$