# Showing that $a^{12}\equiv 1\pmod{210}$ if $a$ is coprime to $210$

I ran into this next question:

Show that if $a$ is coprime to $210$:

$a^{12}\equiv1 \pmod{210}$.

This is not a homework question.

Thank you very much in advance,

Yaron

-
Hint: Use the Chinese remainder theorem. – Peter Shor May 30 '13 at 10:51

Hint: Since $210$ is the product of the pairwise relatively prime numbers $2$, $3$, $5$, and $7$, it is enough to show that (i) $a^{12}\equiv 1\pmod{2}$, and (ii) $a^{12}\equiv 1\pmod{3}$, and (iii) $a^{12}\equiv 1\pmod {5}$, and (iv) $a^{12}\equiv 1\pmod{7}$.

Each of these four tasks can be done using Fermat's Theorem.

Each of the tasks can also be done using somewhat less machinery, but then writing out the details takes quite a bit longer.

Detail: We show for example that $a^{12}\equiv 1\pmod{7}$. We have that $a$ and $7$ are coprime. Fermat's Theorem says that if $p$ is prime, and $a$ and $p$ are coprime, then $a^{p-1}\equiv 1\pmod{p}$. Taking $p=7$, we find that $a^6\equiv 1\pmod{7}$. Squaring both sides of this congruence, we find that $a^{12}\equiv 1\pmod{7}$.

The argument for $5$ is almost the same. We have by Fermat's Theorem that $a^{4}\equiv 1\pmod{5}$. Since $4$ divides $12$, it follows that $a^{12}\equiv 1\pmod{5}$. The same idea works for $3$ and for $2$. In the case of $2$ at least, it is silly to use Fermat's Theorem. For $a$ and $2$ coprime just says that $a$ is odd. And if $a$ is odd, so is $a^{12}$, which says that $a^{12}\equiv 1\pmod{2}$.

-
Rats! You win and I lose by approx. 50 second. I shall erase my almost identical post. – DonAntonio May 30 '13 at 10:59
Why erase, it is not a race. Anyway, OP might prefer your way of putting it. – André Nicolas May 30 '13 at 11:01
When posts are so alike (not that this question was tough...) I think more than one covering some aspect of it may confuse the OP – DonAntonio May 30 '13 at 11:03
thank you very much. but i'm not really sure how to proceed with fermat's theorem. – user76508 May 30 '13 at 11:34
I will add a few lines. – André Nicolas May 30 '13 at 11:38

HINT:

Using Carmichael Function,

$$\lambda(210)=\text{lcm}\{\lambda(2),\lambda(3),\lambda(5),\lambda(7)\}=\text{lcm}(1,2,4,6)=12$$

In fact,we can find a larger $n$ such that $a^{12}\equiv\pmod n$ for all $a$ co-prime to $n$

We need $\lambda(n)$ divides $12$

Case $1:$ If $p=2,$ we know, $\lambda(2^r)=\begin{cases} 2^{r-1} &\mbox{if } 1\le r \le 2 \\ 2^{r-2} & \text{ otherwise }\end{cases}$

$2^{r-2}$ needs to divide $12,r-2\le 2\implies r \le 4$

Case $2:$ If $p$ is odd prime, $\lambda(p^r)=\phi(p^r)=p^{r-1}(p-1),$

If $r>1,$ as the only odd divisor$(>1)$ of $12$ is $3^1\implies p=3,r=2$

Else $r=1\implies p-1$ must divide $12\implies p$ can be $2,3,5,7,13$

$2,3$ have already been encountered

So, the highest value of $n$ will be $13^1\cdot7^1\cdot5^1\cdot3^2\cdot2^4$

As $a^{12}\equiv1\pmod {13\cdot7\cdot5\cdot3^2\cdot2^4}$ if $(a,13\cdot7\cdot5\cdot3^2\cdot2^4)=1,$

$a^{12}\equiv1\pmod d$ where $d$ is any divisor of $13\cdot7\cdot5\cdot3^2\cdot2^4$ and $(a,d)=1$ as $(a,13\cdot7\cdot5\cdot3^2\cdot2^4)=1$

-

Since you have to consider only $a$ modulo $210$, you is only a finite number of case to check. And since it is not a homework, everybody will trust you if you claim you used your computer.

-
This is not an answer but, at most, a comment – DonAntonio May 30 '13 at 11:23
Not in my opinion. If the number of cases is finite, complete enumeration is a valid proof. If the computation is trivial, you do not write it on papers. And this was not a homework question. – AlainD May 30 '13 at 11:43
You are certainly in principle right. – André Nicolas May 30 '13 at 12:00
While checking each residue class mod $210$ so that $(a.210)=1$ would prove that $a^{12}\equiv1\pmod{210}$, it is hardly enlightening of the underlying reasons, how one might answer the question without computer aid, or how one might answer the same question for some much larger numbers. – robjohn May 30 '13 at 12:44
Methink the sentence ", as it can be checked by direct computation on the 210 cases" will pass any referee as a valid mathematical proof. It is not the four color map theorem. – AlainD May 30 '13 at 19:20

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

$$A^{N_j}\equiv 1\ \ ({\rm mod}\ M_j)\ \Rightarrow\ A^{{\rm lcm}\ N_j}\equiv 1\ \ ({\rm mod\ lcm}\ M_j)$$

$${\rm for}\quad \begin{cases} \:N = (1,2,4,6)\,\Rightarrow\,{\rm lcm}\ N_j\, = 12\\ \, M = (2,3,5,7)\,\Rightarrow\, {\rm lcm}\ M_j = 210\end{cases}\ \ \ \$$

-

hints:first find phi(210)=the number of positive integers less than 210 and prime to 210....then apply Euler's theorem : a^phi(210) congruence to 1 mod(210)...

-
Unfortunately $\phi(210)=48$ sinks this approach. – Marc van Leeuwen May 31 '13 at 5:17