Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I saw somewhere that by using Euler's Theorem for m=77 we have:

"$27^{60}\ \mathrm{mod}\ 77 = 1$ and by using modular exponentiation we also have : $27^{10}\ \mathrm{mod}\ 77 = 1$"

For example : if "$a^{30}\ \mathrm{mod}\ 31 = 1$"

Is $a^{10}\ \mathrm{mod}\ 31 = 1$ also true?

share|cite|improve this question
No. $27^{10} \mod 77 = 1$ does not follow from $27^{60} \mod 77 = 1$; it just happens to be true in the case of those particular numbers. And for the case of $\mod 31$, it is a fact of number theory that there is a value of $a$ for which $a^{k} \mod 31 \neq 1$ for all $0<k<30$. – Dustan Levenstein Feb 13 '14 at 14:52
up vote 2 down vote accepted

No, $a^{30} \equiv 1 \pmod{31}$ does not imply $a^{10}\equiv 1 \pmod{31}$. For the case $27^{10}\pmod{77}$, there are two things that contribute,

  1. $77 = 7\cdot 11$, so if $a^m \equiv 1 \pmod{7}$ and $a^m\equiv 1 \pmod{11}$, then $a^m \equiv 1 \pmod{77}$. Now $a^{10} \equiv 1 \pmod{11}$ for all $a$ not divisible by $11$ (Fermat's theorem), so the $11$ part is okay, and
  2. $27 = 3^3$, so $27^{10} = 3^{30} = (3^6)^5$, and again by Fermat's theorem, we have $a^6 \equiv 1\pmod{7}$ for all $a$ not divisible by $7$.
share|cite|improve this answer

Your Answer


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.