# Difference between revisions of "Euler's totient function"

ComplexZeta (talk | contribs) m (→Formulas: Removed abuse of notation) |
|||

Line 1: | Line 1: | ||

'''Euler's totient function''', <math>\phi(n)</math>, is defined as the number of positive integers less than or equal to a given positive integer that are [[relatively prime]] to that integer. | '''Euler's totient function''', <math>\phi(n)</math>, is defined as the number of positive integers less than or equal to a given positive integer that are [[relatively prime]] to that integer. | ||

− | + | == Formulas == | |

+ | To derive the formula, let us first define the prime factorization of <math> n </math> as <math> n = p_1^{e_1}p_2^{e_2}\cdot p_n^{e_n} </math> where the <math>\displaystyle p_i </math> are primes. Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to <math> n </math> are are relatively prime to it. | ||

− | + | 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_n^{e_n} </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_n{e_n} + p_1^{e_1}p_2^{e_2-1}\cdots p_n^{e_n} + \cdots + p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n - 1}.</math></center> | ||

+ | |||

+ | We can factor out though: | ||

+ | |||

+ | <center><math> p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}(p_1+p_2+\cdots + p_n).</math></center> | ||

+ | |||

+ | But we are obviously overcounting. So we then subtract out those divisible by two of the <math> p_1 </math>. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is | ||

+ | |||

+ | <center><math>p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}[(p_1+p_2+\cdots+p_n)-(p_1p_2+p_1p_3+\cdots+(-1)^np_{n-1}p_n)+\cdots+p_1p_2\cdots p_n]</math></center> | ||

+ | |||

+ | which we can factor further as | ||

+ | |||

+ | <center><math>p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}(p_1-1)(p_2-1)\cdots(p_n-1).</math></center> | ||

+ | |||

+ | Making one small adjustment, we write this as | ||

+ | |||

+ | <center><math> \phi(n) = n\left(1-\frac 1{p_1}\right)\left(1-\frac 1{p_2}\right)\cdots\left(1-\frac 1{p_n}\right).</math></center> | ||

Given the general [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}</math>, one can compute <math>\phi(n)</math> using the formula <math> \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) </math>. | Given the general [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}</math>, one can compute <math>\phi(n)</math> using the formula <math> \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) </math>. | ||

− | + | == Identities == | |

For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it. | For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it. |

## Revision as of 20:45, 25 June 2006

**Euler's totient function**, , is defined as the number of positive integers less than or equal to a given positive integer that are relatively prime to that integer.

## Formulas

To derive the formula, let us first define the prime factorization of as where the are primes. Now, we can use a PIE argument to count the number of numbers less than or equal to are 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. So 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 .