Difference between revisions of "Euler's Totient Theorem"
Mathcool2009 (talk | contribs) m (→Proof) |
|||
| 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>, | + | 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>. |
== Credit == | == Credit == | ||
Revision as of 22:45, 22 May 2014
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 each other.
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.
