Difference between revisions of "Euler's Totient Theorem"

m
m (Proof)
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 each other.  
 
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.
+
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 22:01, 26 December 2013

Euler's Totient Theorem is a theorem closely related to his totient function.

Theorem

Let $\phi(n)$ be Euler's totient function. If ${a}$ is an integer and $m$ is a positive integer relatively prime to $a$, then ${a}^{\phi (m)}\equiv 1 \pmod {m}$.

Credit

This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies that ${m}$ is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.

Proof

Consider the set of numbers $A =${$n_1, n_2, ... n_{\phi(m)}$} (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 $B =${$an_1, an_2, ... an_{\phi(m)}$} (mod m) where $(a, m) = 1$. All elements of $B$ are relatively prime to $m$ so if all elements of $B$ are distinct, then $B$ has the same elements as $A$. This means that $n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}$(mod m) → $a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}$ (mod m) → $a^{\phi (m)} \equiv 1$ (mod m) as desired.

See also