Difference between revisions of "Euler's totient function"

(Formulas: fixed the proof)
 
(16 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 
'''Euler's totient function''' <math>\phi(n)</math> applied to a [[positive integer]] <math>n</math> is defined to be the number of positive integers less than or equal to <math>n</math> that are [[relatively prime]] to <math>n</math>.  <math>\phi(n)</math> is read "phi of n."
 
'''Euler's totient function''' <math>\phi(n)</math> applied to a [[positive integer]] <math>n</math> is defined to be the number of positive integers less than or equal to <math>n</math> that are [[relatively prime]] to <math>n</math>.  <math>\phi(n)</math> is read "phi of n."
  
== Formulas ==
+
==Video==
 +
https://youtu.be/T7INnve59JM
 +
 
 +
== Formula ==
 +
 
 +
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>
 +
 
 +
 
 +
== Derivation ==
 
To derive the formula, let us first define the [[prime factorization]] of <math> n </math> as <math> n =\prod_{i=1}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m} </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}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m} </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> \frac{n}{p_1} </math> numbers less than <math> n </math> that are divisible by <math> p_1 </math>.  If we do the same for each <math> p_i </math> and add these up, we get
+
First, let's count the complement of what we want (i.e. all the numbers less than or equal to <math> n </math> that share a common factor with it).  There are <math> \frac{n}{p_1} </math> positive integers less than or equal to <math> n </math> that are divisible by <math> p_1 </math>.  If we do the same for each <math> p_i </math> and add these up, we get
  
<cmath> \frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.</cmath>
+
<center><cmath> \frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.</cmath></center>
  
 
But we are obviously overcounting.  We then subtract out those divisible by two of the <math> p_i </math>.  There are <math>\sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}</math> such numbers. 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_i </math>.  There are <math>\sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}</math> such numbers. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is
  
\[ \sum_{1 \le i \le m}\frac{n}{p_i}
+
<center><cmath> \sum_{1 \le i \le m}\frac{n}{p_i}
 
- \sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}
 
- \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}.\]
+
+ \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}. </cmath></center>
  
 
This sum represents the number of numbers less than <math>n</math> sharing a common factor with <math>n</math>, so
 
This sum represents the number of numbers less than <math>n</math> sharing a common factor with <math>n</math>, so
\[\begin{align*}
 
\phi(n) &= n - (\sum_{1 \le i \le m}\frac{n}{p_i}
 
- \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})\
 
&= n(1 - \sum_{1 \le i \le m}\frac{1}{p_i}
 
+ \sum_{1 \le i_1 < i_2 \le m}\frac{1}{p_{i_1}p_{i_2}}
 
- \cdots + (-1)^{m}\frac{1}{p_1p_2\ldots p_m})\
 
&= n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m}).
 
\end{align*}\]
 
  
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(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_m}).</cmath>
+
<math>\phi(n) = n - \left(\sum_{1 \le i \le m}\frac{n}{p_i}- \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)</math>
 +
 
 +
<math>\phi(n)= n\left(1 - \sum_{1 \le i \le m}\frac{1}{p_i}
 +
+ \sum_{1 \le i_1 < i_2 \le m}\frac{1}{p_{i_1}p_{i_2}} - \cdots + (-1)^{m}\frac{1}{p_1p_2\ldots p_m}\right)</math>
 +
 
 +
<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>
 +
 
 +
 
 +
*Note: Another way to find the closed form for <math>\phi(n)</math> is to show that the function is multiplicative, and then breaking up <math>\phi(n)</math> into its prime factorization.
  
 
== 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]] <math>p</math>, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it.
 +
 
 +
(b) For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>.
  
For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </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>.
  
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>.
+
(d) If <math>p</math> is prime and <math>n\ge{1},</math> then <math>\phi(p^n)=p^n-p^{n-1}</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>.
+
(e) For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors <math>d</math> 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
Line 42: Line 52:
 
<cmath>A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.</cmath>
 
<cmath>A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.</cmath>
 
Thus by the definition of Euler's phi we have that <math>|A_d^\prime|=\phi (n/d)</math>. As every integer <math>i</math> which satisfies <math>1\leq i\leq n</math> belongs in exactly one of the sets <math>A_d</math>, we have that
 
Thus by the definition of Euler's phi we have that <math>|A_d^\prime|=\phi (n/d)</math>. As every integer <math>i</math> which satisfies <math>1\leq i\leq n</math> belongs in exactly one of the sets <math>A_d</math>, we have that
<cmath>n=\sum_{d \mid n}\varphi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).</cmath>
+
<cmath>n=\sum_{d \mid n}\phi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).</cmath>
 +
 
 +
 
 +
(f) Another interesting thing to note is that <math>\phi(n)\leq n - 1</math>. This does seem very obvious but is helpful in solving many problems.
 +
 
 +
==Graph==
 +
 
 +
[[Image:Euler_totient_50000.png]]
  
 
==Notation==
 
==Notation==

Latest revision as of 14:49, 27 July 2024

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."

Video

https://youtu.be/T7INnve59JM

Formula

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).\]


Derivation

To derive the formula, let us first define the prime factorization of $n$ as $n =\prod_{i=1}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$ 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 or equal to $n$ that share a common factor with it). There are $\frac{n}{p_1}$ positive integers less than or equal to $n$ that are divisible by $p_1$. If we do the same for each $p_i$ and add these up, we get

\[\frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.\]

But we are obviously overcounting. We then subtract out those divisible by two of the $p_i$. There are $\sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}$ such numbers. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is

\[\sum_{1 \le i \le m}\frac{n}{p_i} - \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}.\]

This sum represents the number of numbers less than $n$ sharing a common factor with $n$, so

$\phi(n) = n - \left(\sum_{1 \le i \le m}\frac{n}{p_i}- \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)$

$\phi(n)= n\left(1 - \sum_{1 \le i \le m}\frac{1}{p_i} + \sum_{1 \le i_1 < i_2 \le m}\frac{1}{p_{i_1}p_{i_2}} - \cdots + (-1)^{m}\frac{1}{p_1p_2\ldots p_m}\right)$

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


  • Note: Another way to find the closed form for $\phi(n)$ is to show that the function is multiplicative, and then breaking up $\phi(n)$ into its prime factorization.

Identities

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

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

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

(d) If $p$ is prime and $n\ge{1},$ then $\phi(p^n)=p^n-p^{n-1}$

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

Proof. Split the set $\{1,2,\ldots,n\}$ into disjoint sets $A_d$ where for all $d\mid n$ we have \[A_d=\{x:1\leq x\leq n\quad\text{and}\quad \operatorname{syt}(x,n)=d \}.\] Now $\operatorname{gcd}(dx,n)=d$ if and only if $\operatorname{gcd}(x,n/d)=1$. Furthermore, $1\leq dx\leq n$ if and only if $1\leq x\leq n/d$. Now one can see that the number of elements of $A_d$ equals the number of elements of \[A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.\] Thus by the definition of Euler's phi we have that $|A_d^\prime|=\phi (n/d)$. As every integer $i$ which satisfies $1\leq i\leq n$ belongs in exactly one of the sets $A_d$, we have that \[n=\sum_{d \mid n}\phi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).\]


(f) Another interesting thing to note is that $\phi(n)\leq n - 1$. This does seem very obvious but is helpful in solving many problems.

Graph

Euler totient 50000.png

Notation

Sometimes, instead of $\phi$, $\varphi$ is used. This variation of the Greek letter phi is common in textbooks, and is standard usage on the English Wikipedia

See Also