Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Euler's totient function"
m (→‎Formulas)
Line 2: Line 2:
  
 
== Formulas ==
 
== 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>p_i </math> are distinct [[prime number]]s.  Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to  <math> n </math> that are relatively prime to it.
+
To derive the formula, let us first define the [[prime factorization]] of <math> n </math> as <math> n =\prod_{i=1}^{n}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n} </math> where the <math>p_i </math> are distinct [[prime number]]s.  Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to  <math> n </math> that 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  
 
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  
Line 12: Line 12:
 
<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>
 
<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.  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
+
But we are obviously overcounting.  We then subtract out those divisible by two of the <math> p_k </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>
+
<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+p_{n-1}p_n)+\cdots+(-1)^{n+1}(p_1p_2\cdots p_n)]</math></center>
  
 
which we can factor further as
 
which we can factor further as
Line 24: Line 24:
 
<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>
 
<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 <cmath>\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)</cmath>
  
 
== Identities ==
 
== Identities ==

Revision as of 10:25, 8 November 2007

Euler's totient function $\phi(n)$ applied to a positive integer $n$ is defined to be the number of positive integers less than or equal to $n$ that are relatively prime to $n$. $\phi(n)$ is read "phi of n."

Formulas

To derive the formula, let us first define the prime factorization of $n$ as $n =\prod_{i=1}^{n}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$ where the $p_i$ are distinct prime numbers. Now, we can use a PIE argument to count the number of numbers less than or equal to $n$ that are relatively prime to it.

First, let's count the complement of what we want (i.e. all the numbers less than $n$ that share a common factor with it). There are $p_1^{e_1-1}p_2^{e_2}\cdots p_n^{e_n}$ numbers less than $n$ that are divisible by $p_1$. If we do the same for each $p_k$ and add these up, we get

$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}.$

We can factor out, though:

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}(p_1+p_2+\cdots + p_n).$

But we are obviously overcounting. We then subtract out those divisible by two of the $p_k$. 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_n^{e_n-1}[(p_1+p_2+\cdots+p_n)-(p_1p_2+p_1p_3+\cdots+p_{n-1}p_n)+\cdots+(-1)^{n+1}(p_1p_2\cdots p_n)]$

which we can factor further as

$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).$

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_n}\right).$

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

Identities

For prime p, $\phi(p)=p-1$, because all numbers less than ${p}$ are relatively prime to it.

For relatively prime ${a}, {b}$, $\phi{(a)}\phi{(b)} = \phi{(ab)}$.

In fact, we also have for any ${a}, {b}$ that $\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})$.

For any $n$, we have $\sum_{d|n}\phi(d)=n$ where the sum is taken over all divisors d of $n$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&oldid=19194"