Difference between revisions of "Fermat's little theorem"
From Encyclopedia of Mathematics
m (moved Fermat little theorem to Fermat's little theorem: Titled incorrectly) |
(TeX) |
||
| Line 1: | Line 1: | ||
| − | For a number | + | {{TEX|done}} |
| + | 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 proves that the order of every element of the [[Multiplicative group|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 | + | where $\phi(m)$ is the [[Euler function|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. |
====References==== | ====References==== | ||
Revision as of 08:40, 19 April 2014
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 proves 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.
References
| [1] | I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian) |
Comments
References
| [a1] | G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) |
How to Cite This Entry:
Fermat's little theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fermat%27s_little_theorem&oldid=31847
Fermat's little theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fermat%27s_little_theorem&oldid=31847
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article