Namespaces
Variants
Actions

Difference between revisions of "Fermat's little theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Category:Number theory)
(ce)
Line 1: Line 1:
 
{{TEX|done}}
 
{{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
+
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,$$
 
$$a^{\phi(m)}\equiv1\pmod m,$$

Revision as of 08:19, 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)
How to Cite This Entry:
Fermat's little theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fermat%27s_little_theorem&oldid=33823
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article