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.

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

Let $n\in \mathbb{N}$. Show that if $n$ is square-free, then there exists an integer $u > 1$ such that $a^{u} ≡_{n} a $ for all $a \in \mathbb{Z}$.

This is my attempt to prove it. For $n = p_{1}p_{2}...p_{r}$, with distinct primes $p_{1}p_{2}...p_{r}$, I consider $u=(p_{1} −1)(p_{2} −1)···(p_{r} −1)+1$. Then, if $a$ and $n$ are coprime, the result is trivial: in fact, $u=\phi(n)+1$ and we can apply Euler's Theorem.

Now, how can I prove that this particular $u$ also works for $a$ and $n$ not coprime?


share|cite|improve this question
up vote 3 down vote accepted

For $p|n$ you have $a^p\equiv_p a$, no matter if $p|a$ or not. In fact, $a^{k(p-1)+1}\equiv_p a$ for all $k\in\mathbb Z$, hence with your choice of $u$, $a^u\equiv_p a$. Then $a^u\equiv_n a$ follows by the chinese ermainder theorem.

share|cite|improve this answer

Your Answer


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