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"
 
(34 intermediate revisions by 24 users not shown)
Line 1: Line 1:
−
'''Euler's totient function''', <math>\displaystyle \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.  <math>\displaystyle \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==
−
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.
+
https://youtu.be/T7INnve59JM
  
−
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
+
== Formula ==
  
−
<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>
+
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>
  
−
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>
+
== 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.
  
−
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
+
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
  
−
<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><cmath> \frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.</cmath></center>
  
−
which we can factor further as
+
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
  
−
<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>
+
<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}}
 +
+ \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}. </cmath></center>
  
−
Making one small adjustment, we write this as
+
This sum represents the number of numbers less than <math>n</math> sharing a common factor with <math>n</math>, so
  
−
<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>
+
<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>
  
−
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>.
+
<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>.
  
−
=== See also ===
+
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
 +
<cmath>A_d=\{x:1\leq x\leq n\quad\text{and}\quad \operatorname{syt}(x,n)=d \}.</cmath>
 +
Now <math>\operatorname{gcd}(dx,n)=d</math> if and only if <math>\operatorname{gcd}(x,n/d)=1</math>. Furthermore, <math>1\leq dx\leq n</math> if and only if <math>1\leq x\leq n/d</math>. Now one can see that the number of elements of <math>A_d</math> equals the number of elements of
 +
<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
 +
<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==
 +
Sometimes, instead of  <math>\phi</math>, <math>\varphi</math> is used. This variation of the Greek letter ''phi'' is common in textbooks, and is standard usage on the English [[Wikipedia]]
 +
 
 +
== See Also ==
  
 
* [[Number theory]]
 
* [[Number theory]]
 
* [[Prime]]
 
* [[Prime]]
 
* [[Euler's Totient Theorem]]
 
* [[Euler's Totient Theorem]]
 +
 +
[[Category:Functions]]
 +
[[Category:Number theory]]

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

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