Difference between revisions of "Euler's totient function"
m (→Formulas: fix latex) |
(→Identities) |
||
Line 28: | Line 28: | ||
== Identities == | == Identities == | ||
− | For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it. | + | (a) For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it. |
− | For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>. | + | (b) For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>. |
− | In fact, we also have for any <math>{a}, {b}</math> that <math>\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})</math>. | + | (c) In fact, we also have for any <math>{a}, {b}</math> that <math>\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})</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>. | + | (d) If <math>p</math> is prime and <math>n\ge{1}</math>,then <math>\phi(p^n)=p^n-p^{n-1}</math> |
+ | |||
+ | (e) 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 | 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 |
Revision as of 22:50, 22 May 2014
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
[hide]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
But we are obviously overcounting. We then subtract out those divisible by two of the . There are such numbers. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is
This sum represents the number of numbers less than sharing a common factor with , so
$\phi(n) = n - \left(\sum_{1 \le i \le m}\frac{n}{p_i}$ (Error compiling LaTeX. Unknown error_msg) $- \sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}} + \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}\right)$ (Error compiling LaTeX. Unknown error_msg)
Given the general prime factorization of , one can compute using the formula
Identities
(a) For prime p, , because all numbers less than are relatively prime to it.
(b) For relatively prime , .
(c) In fact, we also have for any that .
(d) If is prime and ,then
(e) 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