5
$\begingroup$

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.

  • 1
    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.2012-11-12
  • 0
    See Remark 3.3 of http://www.math.uconn.edu/~kconrad/blurbs/ugradnumthy/eulerthm.pdf, especially equation (3.2). Look also at the two references mentioned at the end of the remark.2014-12-19

1 Answers 1