Difference between revisions of "Fermat's little theorem"
From Encyclopedia of Mathematics
m (moved Fermat little theorem to Fermat's little theorem: Titled incorrectly) |
(Comment: Converse is false, see pseudo-prime) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| 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 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 | + | 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==== | ||
| Line 15: | Line 16: | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979)</TD></TR></table> | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979)</TD></TR></table> | ||
| + | |||
| + | ====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 [[pseudo-prime|pseudoprime]]s. | ||
| + | |||
| + | ====References==== | ||
| + | <table> | ||
| + | <TR><TD valign="top">[b1]</TD> <TD valign="top"> 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</TD></TR> | ||
| + | </table> | ||
| + | [[Category:Number theory]] | ||
Latest revision as of 18:02, 8 November 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 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.
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) |
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
| [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 |
How to Cite This Entry:
Fermat's little theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fermat%27s_little_theorem&oldid=19340
Fermat's little theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fermat%27s_little_theorem&oldid=19340
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article