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.

It is well known that if $\gcd(a,n)=1$, then $a^{ϕ(n)}=1$ mod $n$.

Are there any results similar to Euler's theorem that can be used when $a$ and $n$ are not coprime.

Feel free to add any restrictions on $a$, $n$ other than $a$, $n$ being coprime.

Thank you.

share|improve this question
What do you mean by "similar" and "can be used"? If your ultimate motive is to calculate $a^m \bmod n$, then you can easily get $a^m \bmod p^k$ for all the prime powers in the prime factorization of $n$, and use the Chinese remainder theorem to put them together. –  ShreevatsaR Nov 12 '12 at 4:06
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.