Square free and congruence modulo n 
I am trying to show that if $a^n\equiv a\pmod n$ for all integers $a$ then $n$ is square free. 

I have an idea to start with the contradiction that suppose $n=p^2m$ for some prime $p$, then n does not divide $a^{p^2m}-a$ for some integer $a$. Any hints would be appreciated thanks.
 A: Suppose that $n$ is divisible by $p^2$. Let $a=p$. Since $p^n$ is divisible by $p^2$, the number $p^2$ does not divide $p^n-p$.
A: Your claim is equivalent to the saying that $\{0\} \subset \mathbb{Z}/n\mathbb{Z}$ is a radical ideal in $\mathbb{Z}/n\mathbb{Z}$ only if n is squarefree. This equivalence follows because, for any commutative ring R, an ideal $I \subset R$ is radical if and only if $rad(I) = I$. What exactly is $rad(I)$ (aka the radical of I), you might ask? 
\begin{equation}
rad(I) = \{r \in R : r^n \in I \,\,\,for\,\, some\,\, n \in \mathbb{Z}^+\}
\end{equation}
Notice that this is precisely what you're trying to prove, since in this case, $R = \mathbb{Z}/n\mathbb{Z}$ and $I = n\mathbb{Z}$. Observe that the trivial ideal in this R is precisely $n\mathbb{Z}$. If the trivial ideal is radical, then for any $t \in  n\mathbb{Z}$, we have $t^n \in n\mathbb{Z}$. It is easy to see that this same property holds for all the additive cosets of $n\mathbb{Z}$ whenever this property holds. 
Below I will freely denote classes mod n using their representatives by enclosing them in brackets. It is clear that we are working in $\mathbb{Z}/n\mathbb{Z}$.
Proceeding to the proof of my original claim, suppose that n is squarefree. Then by the fundamental theorem of arithmetic, $n = p_1 \cdot ...\cdot p_k$ for unique prime factors $p_1, ..., p_k \in \mathbb{Z}^+$. First, note that we have the containment $\{0\} \subset rad(\{0\})$ since $[0] = [0]^1 \in \{0\}$. Now, let $[r] \in rad(\{0\})$ be arbitrary. Then, $[r]^m = [0]$ for some $m \in \mathbb{Z}^+$ since $[0]$ is the only element in the trivial ideal. Equivalently, $r^m = tn$ for some $t \in \mathbb{Z}$. Furthermore, by the fundamental theorem of arithmetic, $r=q_1^{f_1} \cdot ...\cdot q_h^{f_h}$ for unique prime factors $q_1, ..., q_h \in \mathbb{Z}^+$ and $f_1, ..., f_h \in \mathbb{Z}^+$. It follows that
$$\begin{align}
q_1^{mf_1} \cdot ...\cdot q_l^{mf_h} &= (q_1^{f_1} \cdot ...\cdot q_h^{f_h})^m \\
&= r^m \\
&= tn \\
&= t \cdot p_1 \cdot ...\cdot p_k
\end{align} $$
Since $p_i\,|\,t \cdot p_1 \cdot ...\cdot p_k$ for each $i \in \{1,...,k\}$, it must also be the case that $p_i\,|\,q_1^{mf_1} \cdot ...\cdot q_h^{mf_h}$ for each $i \in \{1,...,k\}$. Furthermore, because each $p_i$ is a unique prime, $p_i\,|\, q_j^{mf_j}$ for some unique $j \in \{1,...,h\}$. Thus, $p_i\,|\, q_j$. Since $p_i$ and $q_j$ are prime for every choice of $i$ and $j$, it follows that $p_i > 1$ and therefore $p_i = \pm q_j$ since the only units in $\mathbb{Z}$ are $\pm 1$. Without loss of generality, suppose that $p_i = q_j$ since the unit multiple will make no difference once we finally consider classes mod n. Thus, we have
$$ \begin{align}
r &= q_1^{f_1} \cdot ...\cdot q_h^{f_h} \\
&= p_1^{f_1} \cdot ... \cdot p_k^{f_k} \cdot q_{k+1}^{f_{k+1}} \cdot ... \cdot q_h^{f_h} \\
&= p_1 \cdot p_1^{f_1-1} \cdot ... \cdot p_k \cdot p_k^{f_k-1} \cdot q_{k+1}^{f_{k+1}} \cdot ... \cdot q_h^{f_h} \\
&= (p_1 \cdot ...\cdot p_k) \cdot p_1^{f_1-1} \cdot ... \cdot p_k^{f_k-1} \cdot q_{k+1}^{f_{k+1}} \cdot ... \cdot q_h^{f_h} \\
&= n \cdot p_1^{f_1-1} \cdot ... \cdot p_k^{f_k-1} \cdot q_{k+1}^{f_{k+1}} \cdot ... \cdot q_h^{f_h} \\
\end{align} $$
Denote $x = n \cdot p_1^{f_1-1} \cdot ... \cdot p_k^{f_k-1} \cdot q_{k+1}^{f_{k+1}} \cdot ... \cdot q_h^{f_h}$ for convenience. Hence, $r = nx$ and it follows that $[r] = [0]$. Therefore, $[r] \in \{0\}$, and since $[r]$ was chosen arbitrarily, we have the containment $rad(\{0\}) \subset \{0\}$. Thus, $rad(\{0\}) = \{0\}$ and $\{0\}$ is a radical ideal in $\mathbb{Z}/n\mathbb{Z}$. Q.E.D.
