# Understanding abstract algebra proof of Fermat's Little Theorem

The following proof of Fermat's Little Theorem is taken verbatim from Fraleigh's A First Course in Abstract Algebra:

For any field, the nonzero elements form a group under the field multiplication. In particular, for $$\mathbb Z_p$$, the elements $$1,2,3,\ldots,p-1$$ form a group of order $$p-1$$ under multiplication modulo $$p$$. Since the order of any element in a group divides the order of the group, we see that for $$b\neq0$$ and $$b\in\mathbb Z_p$$, we have $$b^{p-1}=1$$ in $$\mathbb Z_p$$. Using the fact that $$\mathbb Z_p$$ is isomorphic to the ring of cosets of the form $$a+p\mathbb Z$$, we see at once that for any $$a\in\mathbb Z$$ not in the coset $$0+p\mathbb Z$$, we must have $$a^{p-1}\equiv1\pmod{p}.$$

I have no problem following the proof, except for one thing. The whole proof makes no mention at all about how $$p$$ must be a prime. Hence it seems like this proof demonstrates Fermat's Little Theorem for all numbers $$p$$, not just primes, which is absurd! Where precisely does this proof break down when $$p$$ is not prime? What am I missing? (Sorry if this question is too trivial, but I couldn't find an explanation elsewhere.)

• Hint: "For any field ...." – Bill Dubuque Nov 13 '18 at 3:23
• @BillDubuque Ah, but $\mathbb Z_n$ is a field if and only if every element is a unit, so every element is coprime to $n$, which is true exactly when $n$ is a prime, so that resolves the issue! Is that right? – YiFan Nov 13 '18 at 3:30

Due to the hint from Bill Dubuque and Doug M, I think I have resolved my own problem. The bolded claim in the proof which is integral to the rest of the proof is only applicable when $$\mathbb Z_p$$ is indeed a field, which requires that every element in it has a multiplicative inverse, so each of them is coprime with the order of $$\mathbb Z_{p}$$. In order to have every $$1,2,3,\ldots,p-1$$ be coprime with $$p$$ we need $$p$$ to be prime.
• Lagrange's Theorem on Finite Groups: If $G$ is a finite group with $|G|=n$ (that is, if $G$ has $n$ members) and if $H$ is a subgroup of $G$, then $|H|$ is a divisor of $|G|$. Corollary: $\forall x\in G\,(x^{|G|}=1_G)$, where $1_G$ is the identity of $G$.... ( For $x\in G$ consider the subgroup $H_x=\{x^n:n\in \Bbb Z\})$..... Lagrange came long after Fermat................+1 to you – DanielWainfleet Nov 13 '18 at 10:18
the order of the multiplicative group $$\bmod p$$ is $$\varphi(p)$$ in general, it's just that if $$p$$ is prime we have $$\varphi(p)=p-1$$.
• But we don't know that the elements in $\mathbb Z_p$ coprime with $p$ form a multiplicative group! Yes, this is true, but it comes quite a bit later in my book in the section discussing Euler's Theorem. So for now I only have the bolded statement to use to prove FLittleT. Could you help pinpoint where in the given proof does it actually use the primality of $p$? – YiFan Nov 13 '18 at 3:34
• if $p$ is not prime then the nonzero elements dont form a group. This is easy to see because any non trivial divisor of $p$ has no inverse. – Jorge Fernández Hidalgo Nov 13 '18 at 3:36