10
$\begingroup$

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.

  • 6
    Good start... So, $a^{12}=$____$\pmod{7}$ and $a^{12}=$____$\pmod{5}$. Can you fill in?2012-06-08
  • 0
    @did oh yes !!! 1,1 and I got it .Thanks for the hint.How could I miss that :(2012-06-08
  • 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...2012-06-08

3 Answers 3

14

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

4

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.

  • 0
    Interesting solution by residues, instead of the further extension of the original approach. Thanks for sharing.2012-06-08
  • 0
    @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....$2012-06-20
  • 0
    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$.2012-06-20
  • 0
    @Potato:If $\operatorname{gcd}(m,n) =1$ and $a \equiv c (\text{mod m})$, $b \equiv d (\text{mod n})$, then $ab \equiv cd (\text{mod mn})$.2018-02-28
3

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

  • 0
    One would also need the hint that $a^3=b^3\pmod{m}$.2012-06-08
  • 1
    @Saurabh: It is a Complete hint.2012-06-08
  • 0
    @did: Yes, absolutely.2012-06-08
  • 0
    @user9413:If $\operatorname{gcd}(m,n) =1$ and $a \equiv c (\text{mod m})$, $b \equiv d (\text{mod n})$, then $ab \equiv cd (\text{mod mn})$???2018-02-28