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.

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|improve this question
1  
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 at 14:52

1 Answer 1

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|improve this answer

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.