Difference between revisions of "Euler's Totient Theorem"
m |
m (→Proof) |
||
Line 12: | Line 12: | ||
Consider the set of numbers <math>A = </math>{<math>n_1, n_2, ... n_{\phi(m)} </math>} (mod m) such that the elements of the set are the numbers relatively prime to each other. It will now be proved that this set is the same as the set <math>B = </math>{<math>an_1, an_2, ... an_{\phi(m)} </math>} (mod m) where <math> (a, m) = 1</math>. All elements of <math>B</math> are relatively prime to <math>m</math> so if all elements of <math>B</math> are distinct, then <math>B</math> has the same elements as <math>A</math>. This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math>(mod m) => <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math> (mod m) => <math>a^{\phi (m)} \equiv 1</math> (mod m) as desired. | Consider the set of numbers <math>A = </math>{<math>n_1, n_2, ... n_{\phi(m)} </math>} (mod m) such that the elements of the set are the numbers relatively prime to each other. It will now be proved that this set is the same as the set <math>B = </math>{<math>an_1, an_2, ... an_{\phi(m)} </math>} (mod m) where <math> (a, m) = 1</math>. All elements of <math>B</math> are relatively prime to <math>m</math> so if all elements of <math>B</math> are distinct, then <math>B</math> has the same elements as <math>A</math>. This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math>(mod m) => <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math> (mod m) => <math>a^{\phi (m)} \equiv 1</math> (mod m) as desired. | ||
− | |||
− | |||
== See also == | == See also == |
Revision as of 15:54, 7 May 2013
Contents
ITS BY PANDEY
Euler's Totient Theorem is a theorem closely related to his function of the same name.
Theorem
Let be Euler's totient function. 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 that is prime. For this reason it is known as Euler's generalization and Fermat-Euler as well.
Proof
Consider the set of numbers {
} (mod m) such that the elements of the set are the numbers relatively prime to each other. It will now be proved that this set is the same as the set
{
} (mod m) where
. All elements of
are relatively prime to
so if all elements of
are distinct, then
has the same elements as
. This means that
(mod m) =>
(mod m) =>
(mod m) as desired.