Difference between revisions of "Euler's Totient Theorem"

m
m (Proof: fixed latex)
(2 intermediate revisions by one other user not shown)
Line 2: Line 2:
  
 
== Theorem ==
 
== Theorem ==
Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>,in other words If <math>n</math> is a positive integer, <math>\phi{(n)}</math> is the number of integers in the range <math>\{1,2,3\cdots{,n}\}</math> which are relatively prime to <math>n</math>.Then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>.
+
Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>n</math> is a positive integer, <math>\phi{(n)}</math> is the number of integers in the range <math>\{1,2,3\cdots{,n}\}</math> which are relatively prime to <math>n</math>. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>,Then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>.
  
 
== Credit ==
 
== Credit ==
Line 10: Line 10:
 
==Proof==
 
==Proof==
  
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>}<math>\pmod{m}</math> 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. Note that dividing by <math> n_1 n_2 ... n_{\phi(m)}</math> is allowed since it is 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>}<math>\pmod{m}</math> 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>. In other words, each element of <math>B</math> is congruent to one of <math>A</math>.This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math><math>\pmod{m}</math> → <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math><math>\pmod{m}</math> → <math>a^{\phi (m)} \equiv 1</math><math>\pmod{m}</math> 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 03:39, 29 December 2015

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

Theorem

Let $\phi(n)$ be Euler's totient function. If $n$ is a positive integer, $\phi{(n)}$ is the number of integers in the range $\{1,2,3\cdots{,n}\}$ which are relatively prime to $n$. 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)}$}$\pmod{m}$ such that the elements of the set are the numbers relatively prime to $m$. It will now be proved that this set is the same as the set $B =${$an_1, an_2, ... an_{\phi(m)}$}$\pmod{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$. In other words, each element of $B$ is congruent to one of $A$.This means that $n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}$$\pmod{m}$$a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}$$\pmod{m}$$a^{\phi (m)} \equiv 1$$\pmod{m}$ as desired. Note that dividing by $n_1 n_2 ... n_{\phi(m)}$ is allowed since it is relatively prime to $m$.

See also