Difference between revisions of "Euler's totient function"
m (→Formulas) |
|||
Line 8: | Line 8: | ||
First, let's count the complement of what we want (i.e. all the numbers less than <math> n </math> that share a common factor with it). There are <math> p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} </math> numbers less than <math> n </math> that are divisible by <math> p_1 </math>. If we do the same for each <math> p_k </math> and add these up, we get | First, let's count the complement of what we want (i.e. all the numbers less than <math> n </math> that share a common factor with it). There are <math> p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} </math> numbers less than <math> n </math> that are divisible by <math> p_1 </math>. If we do the same for each <math> p_k </math> and add these up, we get | ||
− | <center><math> 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}.</math></center> | + | <center><math> 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}.</math></center> |
We can factor out, though: | We can factor out, though: |
Revision as of 00:27, 22 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
We can factor out, though:
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
which we can factor further as
Making one small adjustment, we write this as
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
Sometimes, instead of , is used. This variation of the Greek letter phi is common in textbooks, and is standard usage on the English Wikipedia