# Theorem about mod n, when n is square free

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?

Thanks!

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