Difference between revisions of "Euler's Totient Theorem"

Revision as of 02: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$ .

@@ Line 10: / Line 10: @@
 ==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>. 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>(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 ==

Page

Toolbox

Search

Difference between revisions of "Euler's Totient Theorem"

Revision as of 02:39, 29 December 2015

Contents

Theorem

Credit

Proof

See also