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.

If $\gcd(a,35)=1$, then show that $a^{12}\equiv1\pmod{35}$

I have tried this problem beginning with $a^6 \equiv 1 \pmod{7}$ and $a^4 \equiv 1 \pmod{5}$ (Fermat's Theorem) but couldn't get far enough. Please help.

share|improve this question
6  
Good start... So, $a^{12}=$____$\pmod{7}$ and $a^{12}=$____$\pmod{5}$. Can you fill in? –  Did Jun 8 '12 at 8:43
    
@did oh yes !!! 1,1 and I got it .Thanks for the hint.How could I miss that :( –  Saurabh Jun 8 '12 at 8:50
2  
You are welcome. Surely you know that you may write your own solution, post it here as an answer, wait a little bit, and accept it. It is even recommanded... –  Did Jun 8 '12 at 8:57
add comment

3 Answers

up vote 12 down vote accepted

Since $\gcd(a,7) =\gcd(a,5) = 1$, from Fermat's theorem,
$$a^6\equiv 1\pmod7 \quad \text{ and } \quad a^4\equiv1\pmod5. $$ Hence, $$ a^{12}\equiv 1\pmod7 \quad \text{ and } \quad a^{12}\equiv1\pmod5. $$ This means that $$7\mid a^{12}-1 \quad\text{ and } \quad 5\mid a^{12}-1. $$ Since $\gcd(7,5)=1$, $$35\mid a^{12}-1, $$ that is, $$ a^{12}\equiv1\pmod{35}. $$

share|improve this answer
add comment

One way to do this is to use Euler's totient theorem. You are familiar with Fermat's little theorem, and this is a generalized version. This approach is lengthier, but instructive, because it shows that the totient function doesn't always give you the minimal exponent. For more information, see here.

From the theorem, we know

$$a^{\phi(35)} \equiv_{35} 1$$

A simple computation shows that $\phi(35)=24$ (this can be shortened if you know more about the $\phi$ function).

So we have

$$a^{24}\equiv 1. $$

In general, if $k^2\equiv 1$, we see $(k-1)(k+1)\equiv 0$, so $k\equiv 1$ or $k\equiv -1$ (You need to think for a moment to see that other cases are ruled out, as this isn't an integral domain). Applying this to the above, we will be done once we rule out the case

$$a^{12}\equiv -1.$$

In particular, we would need $(a^6)^2$ to be $-1$ mod $35$. To show $-1$ is not a square mod $35$, it suffices to show it is not a square mod $7$ (if $a^2$ was -1 mod 35, the same $a$ mod 7 would produce $a^2\equiv -1$ mod 7).

And it is easy to see by checking all possibilities that $-1$ is not the square of any number when considered modulo 7.

share|improve this answer
    
Interesting solution by residues, instead of the further extension of the original approach. Thanks for sharing. –  awllower Jun 8 '12 at 12:20
    
@Potato In the $3\text{rd}$ paragraph how you had written "In general, if $k^2 \equiv 1$ we see....." How other cases are ruled out e.g. $k^2 \equiv 1 \pmod{3}$ then $k \equiv 1 \text{ or } k\equiv -1 \text{ or } k\equiv 4....$ –  Saurabh Jun 20 '12 at 7:17
    
We have the factorization $(k-1)(k+1)\equiv_{35} 0$. The numbers on the left have to be 0 or divisors of $35$. I actually forgot to explicitly write out the case $k=6$, but that's not hard to see using the same methods I used. But $k\equiv 4$ won't work, for example, because $3*15=15$, which is not a multiple of $35$. –  Potato Jun 20 '12 at 8:00
add comment

Note that:

  • If $a \equiv b \ (\text{mod m})$ then $a^{2} \equiv b^{2} \ (\text{mod m})$.

  • If $\operatorname{gcd}(m,n) =1$ and $a \equiv 1 (\text{mod m})$, $b \equiv 1 (\text{mod n})$, then $ab \equiv 1 (\text{mod mn})$.

share|improve this answer
    
One would also need the hint that $a^3=b^3\pmod{m}$. –  Did Jun 8 '12 at 8:52
1  
@Saurabh: It is a Complete hint. –  B. S. Jun 8 '12 at 9:10
    
@did: Yes, absolutely. –  user9413 Jun 8 '12 at 9:40
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.