[proofplan] We first prove the second formulation when $a \not\equiv 0 \pmod p$. Since $p$ is [[prime number|prime]], the non-zero [[modular arithmetic|residue classes modulo]] $p$ are precisely the units of $\mathbb{Z}/p\mathbb{Z}$, and multiplication by the class of $a$ permutes them. Comparing the product of all non-zero residues before and after this permutation gives $a^{p-1} \equiv 1 \pmod p$, and the stated congruence $a^p \equiv a \pmod p$ follows by treating the zero and non-zero residue classes separately. [/proofplan] [step:Show that multiplication by $a$ permutes the non-zero residue classes modulo $p$] Assume first that $a \not\equiv 0 \pmod p$. Let \begin{align*} R := \{1,2,\dots,p-1\} \end{align*} denote the standard representatives of the non-zero residue classes modulo $p$. Since $p$ is prime and $a \not\equiv 0 \pmod p$, we have $\gcd(a,p)=1$, so the residue class of $a$ is a unit in $\mathbb{Z}/p\mathbb{Z}$. Define the map \begin{align*} m_a : R &\to \mathbb{Z}/p\mathbb{Z} \\ k &\mapsto ak \pmod p . \end{align*} If $m_a(k)=m_a(\ell)$ for $k,\ell \in R$, then $ak \equiv a\ell \pmod p$. Multiplying by the inverse of $a$ modulo $p$ gives $k \equiv \ell \pmod p$. Since $k,\ell \in \{1,\dots,p-1\}$, this implies $k=\ell$. Thus $m_a$ is injective on $R$. Also, for each $k \in R$, the congruence $ak \equiv 0 \pmod p$ would imply $p \mid ak$. Since $p$ is prime and $p \nmid a$, Euclid's lemma gives $p \mid k$, contradicting $1 \le k \le p-1$. Hence every value of $m_a$ is a non-zero residue class. Therefore the $p-1$ classes \begin{align*} a,2a,\dots,(p-1)a \pmod p \end{align*} are pairwise distinct non-zero residue classes, so they are exactly the non-zero residue classes modulo $p$. [guided] We assume $a \not\equiv 0 \pmod p$ because this is the version in which division by $a$ modulo $p$ is allowed. Since $p$ is prime and $p \nmid a$, we have $\gcd(a,p)=1$. By Bezout's identity, there are integers $u,v \in \mathbb{Z}$ such that \begin{align*} ua + vp = 1. \end{align*} Reducing this congruence modulo $p$ gives $ua \equiv 1 \pmod p$, so the residue class of $a$ has inverse the residue class of $u$ in $\mathbb{Z}/p\mathbb{Z}$. Let \begin{align*} R := \{1,2,\dots,p-1\} \end{align*} be the set of standard integer representatives for the non-zero residue classes modulo $p$. We study multiplication by $a$ on this set by defining \begin{align*} m_a : R &\to \mathbb{Z}/p\mathbb{Z} \\ k &\mapsto ak \pmod p . \end{align*} The first point is injectivity. Suppose $k,\ell \in R$ and $m_a(k)=m_a(\ell)$. Then \begin{align*} ak \equiv a\ell \pmod p. \end{align*} Multiplying both sides by the inverse class $u$ of $a$ gives \begin{align*} k \equiv \ell \pmod p. \end{align*} Because both $k$ and $\ell$ lie between $1$ and $p-1$, their difference satisfies $-(p-2) \le k-\ell \le p-2$. The only multiple of $p$ in this range is $0$, so $k-\ell=0$ and therefore $k=\ell$. The second point is that no image is zero modulo $p$. If $ak \equiv 0 \pmod p$ for some $k \in R$, then $p \mid ak$. Since $p$ is prime, Euclid's lemma implies $p \mid a$ or $p \mid k$. The first alternative contradicts $a \not\equiv 0 \pmod p$, and the second contradicts $1 \le k \le p-1$. Thus $ak \not\equiv 0 \pmod p$ for every $k \in R$. We now have $p-1$ pairwise distinct non-zero residue classes. Since there are exactly $p-1$ non-zero residue classes modulo $p$, namely the classes represented by $1,2,\dots,p-1$, the list \begin{align*} a,2a,\dots,(p-1)a \pmod p \end{align*} is a permutation of the non-zero residue classes modulo $p$. [/guided] [/step] [step:Compare the products of the two permuted residue lists] Since the residue classes \begin{align*} a,2a,\dots,(p-1)a \pmod p \end{align*} are a permutation of the residue classes represented by $1,2,\dots,p-1$, their products are congruent modulo $p$: \begin{align*} (a)(2a)\cdots((p-1)a) \equiv 1\cdot 2 \cdots (p-1) \pmod p. \end{align*} Collecting the $p-1$ factors equal to $a$ on the left gives \begin{align*} a^{p-1}(p-1)! \equiv (p-1)! \pmod p. \end{align*} [/step] [step:Cancel the factorial factor modulo $p$] For each $k \in \{1,\dots,p-1\}$, we have $p \nmid k$, so $\gcd(k,p)=1$. Hence each residue class $k \pmod p$ is a unit in $\mathbb{Z}/p\mathbb{Z}$, and therefore the product $(p-1)!$ is also a unit modulo $p$. Multiplying \begin{align*} a^{p-1}(p-1)! \equiv (p-1)! \pmod p \end{align*} by the inverse of $(p-1)!$ modulo $p$ gives \begin{align*} a^{p-1} \equiv 1 \pmod p. \end{align*} Thus the equivalent formulation holds for every $a \in \mathbb{Z}$ with $a \not\equiv 0 \pmod p$. [/step] [step:Deduce $a^p \equiv a \pmod p$ for every integer $a$] Let $a \in \mathbb{Z}$. If $a \equiv 0 \pmod p$, then $a^p \equiv 0 \equiv a \pmod p$. If $a \not\equiv 0 \pmod p$, the result proved above gives \begin{align*} a^{p-1} \equiv 1 \pmod p. \end{align*} Multiplying this congruence by $a$ gives \begin{align*} a^p \equiv a \pmod p. \end{align*} Therefore $a^p \equiv a \pmod p$ for all $a \in \mathbb{Z}$. [/step] [step:Recover the non-zero formulation from $a^p \equiv a \pmod p$] Conversely, suppose $a \in \mathbb{Z}$ satisfies $a \not\equiv 0 \pmod p$ and assume \begin{align*} a^p \equiv a \pmod p. \end{align*} Since $a$ is a unit modulo $p$, we may multiply both sides by the inverse of $a$ in $\mathbb{Z}/p\mathbb{Z}$. This gives \begin{align*} a^{p-1} \equiv 1 \pmod p. \end{align*} Thus the two stated formulations are equivalent, and the theorem is proved. [/step]