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.

$\endgroup$
  • 7
    $\begingroup$ Good start... So, $a^{12}=$____$\pmod{7}$ and $a^{12}=$____$\pmod{5}$. Can you fill in? $\endgroup$ – Did Jun 8 '12 at 8:43
  • $\begingroup$ @did oh yes !!! 1,1 and I got it .Thanks for the hint.How could I miss that :( $\endgroup$ – Saurabh Jun 8 '12 at 8:50
  • 2
    $\begingroup$ 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... $\endgroup$ – Did Jun 8 '12 at 8:57
16
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting solution by residues, instead of the further extension of the original approach. Thanks for sharing. $\endgroup$ – awllower Jun 8 '12 at 12:20
  • $\begingroup$ @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....$ $\endgroup$ – Saurabh Jun 20 '12 at 7:17
  • $\begingroup$ 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$. $\endgroup$ – Potato Jun 20 '12 at 8:00
  • $\begingroup$ @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})$. $\endgroup$ – Styles Feb 28 '18 at 7:00
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ One would also need the hint that $a^3=b^3\pmod{m}$. $\endgroup$ – Did Jun 8 '12 at 8:52
  • 1
    $\begingroup$ @Saurabh: It is a Complete hint. $\endgroup$ – mrs Jun 8 '12 at 9:10
  • $\begingroup$ @did: Yes, absolutely. $\endgroup$ – user9413 Jun 8 '12 at 9:40
  • $\begingroup$ @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})$??? $\endgroup$ – Styles Feb 28 '18 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.