Difference between revisions of "Euler's Totient Theorem"
m (→Proof: fixed latex) |
(→Credit) |
||
Line 6: | Line 6: | ||
== Credit == | == Credit == | ||
− | This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies | + | This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies it when <math>{m}</math> is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem. |
==Proof== | ==Proof== |
Revision as of 10:56, 26 June 2020
Euler's Totient Theorem is a theorem closely related to his totient function.
Contents
Theorem
Let be Euler's totient function. If
is a positive integer,
is the number of integers in the range
which are relatively prime to
. If
is an integer and
is a positive integer relatively prime to
,Then
.
Credit
This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies it when is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.
Proof
Consider the set of numbers {
}
such that the elements of the set are the numbers relatively prime to
.
It will now be proved that this set is the same as the set
{
}
where
. All elements of
are relatively prime to
so if all elements of
are distinct, then
has the same elements as
. In other words, each element of
is congruent to one of
.This means that
→
→
as desired. Note that dividing by
is allowed since it is relatively prime to
.