Fermat's little theorem

For a number $a$ not divisible by a prime number $p$, the congruence $a^{p-1}\equiv1\pmod p$ holds. This theorem was established by P. Fermat (1640). It asserts that the order of every element of the multiplicative group of residue classes modulo $p$ divides the order of the group. Fermat's little theorem was generalized by L. Euler to the case modulo an arbitrary $m$. Namely, he proved that for every number $a$ relatively prime to the given number $m>1$ there is the congruence

$$a^{\phi(m)}\equiv1\pmod m,$$

where $\phi(m)$ is the Euler function. Another generalization of Fermat's little theorem is the equation $x^q=x$, which is valid for all elements of the finite field $k_q$ consisting of $q$ elements.

Comments

The converse of Fermat's little theorem does not hold: for any fixed $a$ there are infinitely many composite $n$ such that $a^{n-1} \equiv 1 \pmod n$. Such $n$ are known as pseudoprimes.

References

[1]	I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)
[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979)
[b1]	C. Pomerance, J.L. Selfridge, S.S. Wagstaff, Jr., "The pseudoprimes to $25\cdot10^9$" Math. Comp. , 35 (1980) pp. 1003–1026. Zbl 0444.10007. DOI 10.2307/2006210