Difference between revisions of "Euler's totient function"
(→See also: cap) |
|||
Line 39: | Line 39: | ||
Often instead of <math>\phi</math>, also <math>\varphi</math> is used. | Often instead of <math>\phi</math>, also <math>\varphi</math> is used. | ||
− | == See | + | == See Also == |
* [[Number theory]] | * [[Number theory]] |
Revision as of 19:48, 30 January 2008
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/8/6/5/86538594cb8b496a756a2ae1ea484ec6dec224f4.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
.
Notation
Often instead of , also
is used.