| Version 7 |
Version 6 |
| \begin{thm*}[Fermat's little theorem] If $a, p \in \mathbb{Z}$ with $p$ a prime and $p \nmid a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ If we take away the condition that $p\nmid a$, then we have the congruence relation $$a^p\equiv a \pmod{p}$$ instead. \end{thm*} |
\begin{thm*}[Fermat's little theorem] If $a, p \in \mathbb{Z}$ with $p$ a prime and $p \nmid a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ If we take away the condition that $p\nmid a$, then we have the congruence relation $$a^p\equiv a \pmod{p}$$ instead. \end{thm*} |
|
|
| \textbf{Remarks}. |
\textbf{Remarks}. |
| \begin{itemize} |
\begin{itemize} |
| \item Although Fermat first noticed this property, he never actually proved it. There are several different ways to directly prove this theorem, but it is really just a corollary of the Euler theorem. |
\item Although Fermat first noticed this property, he never actually proved it. There are several different ways to directly prove this theorem, but it is really just a corollary of the Euler theorem. |
|
\item More generally, this is a statement about finite fields: if $K$ is a finite field of order $q$, then $a^{q-1}=1$ for all $0\ne a\in K$. More succinctly, the group of units in a finite field is cyclic. If $q$ is prime, then we have Fermat's little theorem.
|
\item More generally, this is a statement about finite fields: if $K$ is a finite field of order $q$, then $a^q=a$ for all $a\in K$. If $q$ is prime, then we have Fermat's little theorem.
|
| \item While it is true that $p$ prime implies the congruence relation above, the converse is false (as hypothesized by ancient Chinese mathematicians). A well-known example of this is provided by setting $a=2$ and $p=341=11\times 31$. It is easy to verify that $2^{341}\equiv 2 \pmod{341}$. A positive integer $p$ satisfying $a^{p-1}\equiv 1 \pmod{p}$ is known as a pseudoprime of base $a$. All primes are pseudoprimes of any base. |
\item While it is true that $p$ prime implies the congruence relation above, the converse is false (as hypothesized by ancient Chinese mathematicians). A well-known example of this is provided by setting $a=2$ and $p=341=11\times 31$. It is easy to verify that $2^{341}\equiv 2 \pmod{341}$. A positive integer $p$ satisfying $a^{p-1}\equiv 1 \pmod{p}$ is known as a pseudoprime of base $a$. All primes are pseudoprimes of any base. |
| \end{itemize} |
\end{itemize} |
|
|
| \begin{thebibliography}{7} |
\begin{thebibliography}{7} |
| \bibitem{hs} H. Stark, {\em An Introduction to Number Theory}. The MIT Press (1978) |
\bibitem{hs} H. Stark, {\em An Introduction to Number Theory}. The MIT Press (1978) |
| \end{thebibliography} |
\end{thebibliography} |
