Difference between revisions of "Euler's Totient Theorem"
m (Euler's Totient Theorem moved to Euler's totient theorem) |
(→Credit) |
||
(22 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
− | + | '''Euler's Totient Theorem''' is a theorem closely related to his [[totient function]]. | |
− | 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>, | + | == Theorem == |
+ | 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 == | |
− | This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies | + | This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies it when <math>{m}</math> is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem. |
− | === See also | + | ==Proof== |
+ | |||
+ | 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>}<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 == | ||
* [[Number theory]] | * [[Number theory]] | ||
* [[Modular arithmetic]] | * [[Modular arithmetic]] | ||
* [[Euler's totient function]] | * [[Euler's totient function]] | ||
+ | * [[Carmichael function]] | ||
+ | |||
+ | [[Category:Number theory]] | ||
+ | |||
+ | [[Category:Theorems]] |
Revision as of 10:56, 26 June 2020
Euler's Totient Theorem is a theorem closely related to his totient function.
Contents
Theorem
Let be Euler's totient function. If is a positive integer, is the number of integers in the range which are relatively prime to . 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 it when is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.
Proof
Consider the set of numbers {} 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 {} where . All elements of are relatively prime to so if all elements of are distinct, then has the same elements as . In other words, each element of is congruent to one of .This means that → → as desired. Note that dividing by is allowed since it is relatively prime to .