# Is it true (based on Euler's theorem)

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?

-
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

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