Difference between revisions of "Euler's Totient Theorem"
m (changed "relatively prime to to each other" to "relatively prime to m") |
m |
||
| Line 11: | Line 11: | ||
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 <math>m</math>. | 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 <math>m</math>. | ||
| − | 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. | + | 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. Note that dividing by <math> n_1 n_2 ... n_{\phi(m)}</math> is allowed since it is relatively prime to <math>m</math>. |
== See also == | == See also == | ||
Revision as of 01:50, 29 December 2015
Euler's Totient Theorem is a theorem closely related to his totient function.
Contents
Theorem
Let 
be Euler's totient function. If 
is an integer and 
is a positive integer relatively prime to 
,in other words If 
is a positive integer, 
is the number of integers in the range 
which are 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 also known as Euler's generalization or the Fermat-Euler theorem.
Proof
Consider the set of numbers 
{
} (mod m) 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 
{
} (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. Note that dividing by 
is allowed since it is relatively prime to .
