Difference between revisions of "Euler's totient function"
m (→Formulas) |
(→Identities) |
||
Line 37: | Line 37: | ||
For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>. | For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>. | ||
+ | |||
+ | Proof. Split the set <math>\{1,2,\ldots,n\}</math> into disjoint sets <math>A_d</math> where for all <math>d\mid n</math> we have | ||
+ | <cmath>A_d=\{x:1\leq x\leq n\quad\text{and}\quad \operatorname{syt}(x,n)=d \}.</cmath> | ||
+ | Now <math>\operatorname{gcd}(dx,n)=d</math> if and only if <math>\operatorname{gcd}(x,n/d)=1</math>. Furthermore, <math>1\leq dx\leq n</math> if and only if <math>1\leq x\leq n/d</math>. Now one can see that the number of elements of <math>A_d</math> equals the number of elements of | ||
+ | <cmath>A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.</cmath> | ||
+ | Thus by the definition of Euler's phi we have that <math>|A_d^\prime|=\phi (n/d)</math>. As every integer <math>i</math> which satisfies <math>1\leq i\leq n</math> belongs in exactly one of the sets <math>A_d</math>, we have that | ||
+ | <cmath>n=\sum_{d \mid n}\varphi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).</cmath> | ||
==Notation== | ==Notation== |
Revision as of 16:17, 25 July 2008
This is an AoPSWiki Word of the Week for July 18-July 24 |
Euler's totient function applied to a positive integer
is defined to be the number of positive integers less than or equal to
that are relatively prime to
.
is read "phi of n."
Contents
Formulas
To derive the formula, let us first define the prime factorization of as
where the
are distinct prime numbers. Now, we can use a PIE argument to count the number of numbers less than or equal to
that are relatively prime to it.
First, let's count the complement of what we want (i.e. all the numbers less than that share a common factor with it). There are
numbers less than
that are divisible by
. If we do the same for each
and add these up, we get
![$p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} + p_1^{e_1}p_2^{e_2-1}\cdots p_m^{e_m} + \cdots + p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m - 1}.$](http://latex.artofproblemsolving.com/6/8/8/688ecc3a83319b4940b4bdde2c73cbb83cdc37e5.png)
We can factor out, though:
![$p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1+p_2+\cdots + p_m).$](http://latex.artofproblemsolving.com/4/1/b/41b4215ff46317e82af659fa78c3e15ac48459ad.png)
But we are obviously overcounting. We then subtract out those divisible by two of the . We continue with this PIE argument to figure out that the number of elements in the complement of what we want is
![$p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}[(p_1+p_2+\cdots+p_m)-(p_1p_2+p_1p_3+\cdots+p_{m-1}p_m)+\cdots+(-1)^{m+1}(p_1p_2\cdots p_m)]$](http://latex.artofproblemsolving.com/8/a/4/8a43763284cf570bc49837c56ce3324ece17ba1b.png)
which we can factor further as
![$p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1-1)(p_2-1)\cdots(p_m-1).$](http://latex.artofproblemsolving.com/2/c/4/2c44276b8eadc34541e805fac92d4b5e4a551ed7.png)
Making one small adjustment, we write this as
![$\phi(n) = n\left(1-\frac 1{p_1}\right)\left(1-\frac 1{p_2}\right)\cdots\left(1-\frac 1{p_m}\right).$](http://latex.artofproblemsolving.com/1/4/4/14423cf3d688b8ef732c39cb1657cdbe73b1f8a2.png)
Given the general prime factorization of , one can compute
using the formula
Identities
For prime p, , because all numbers less than
are relatively prime to it.
For relatively prime ,
.
In fact, we also have for any that
.
For any , we have
where the sum is taken over all divisors d of
.
Proof. Split the set into disjoint sets
where for all
we have
Now
if and only if
. Furthermore,
if and only if
. Now one can see that the number of elements of
equals the number of elements of
Thus by the definition of Euler's phi we have that
. As every integer
which satisfies
belongs in exactly one of the sets
, we have that
Notation
Sometimes, instead of ,
is used. This variation of the Greek letter phi is common in textbooks, and is standard usage on the English Wikipedia