2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Hint: "For any field ...." $\endgroup$ – Bill Dubuque Nov 13 '18 at 3:23
  • 1
    $\begingroup$ @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? $\endgroup$ – YiFan Nov 13 '18 at 3:30
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – DanielWainfleet Nov 13 '18 at 10:18
0
$\begingroup$

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

So in fact this is a proof of Euler's theorem.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – YiFan Nov 13 '18 at 3:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Jorge Fernández Hidalgo Nov 13 '18 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.