Namespaces
Variants
Actions

Difference between revisions of "Fermat's little theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384001.png" /> not divisible by a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384002.png" />, the congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384003.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384004.png" /> divides the order of the group. Fermat's little theorem was generalized by L. Euler to the case modulo an arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384005.png" />. Namely, he proved that for every number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384006.png" /> relatively prime to the given number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384007.png" /> there is the congruence
+
{{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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384008.png" /></td> </tr></table>
+
$$a^{\phi(m)}\equiv1\pmod m,$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f0384009.png" /> is the [[Euler function|Euler function]]. Another generalization of Fermat's little theorem is the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f03840010.png" />, which is valid for all elements of the finite field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f03840011.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038400/f03840012.png" /> elements.
+
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
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article