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.

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

share|improve this question
    
Hint: Use the Chinese remainder theorem. –  Peter Shor May 30 '13 at 10:51
add comment

5 Answers

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

share|improve this answer
    
Rats! You win and I lose by approx. 50 second. I shall erase my almost identical post. –  DonAntonio May 30 '13 at 10:59
1  
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
show 2 more comments

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$

share|improve this answer
add comment

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.

share|improve this answer
1  
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. –  user1938185 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. –  user1938185 May 30 '13 at 19:20
add comment

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

share|improve this answer
add comment

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

share|improve this answer
2  
Unfortunately $\phi(210)=48$ sinks this approach. –  Marc van Leeuwen May 31 '13 at 5:17
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.