Difference between revisions of "Euler's Totient Theorem"
m |
m (grammar mistake corrected) |
||
| Line 2: | Line 2: | ||
== Theorem == | == Theorem == | ||
| − | Let <math>\phi(n)</math> be [[Euler's totient function]]. | + | 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 == | ||
Revision as of 02:03, 29 December 2015
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 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 .
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 
. In other words, each element of is congruent to one of .This means that 
(mod m) → 
(mod m) → 
(mod m) as desired. Note that dividing by 
is allowed since it is relatively prime to .
