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"

(→‎Formulas: fixed the proof)
m (→‎Formulas: not sure why the LaTeX screws up)
Line 11: Line 11:
  
 
\[ \sum_{1 \le i \le m}\frac{n}{p_i}
 
\[ \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}.\]
  
 
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}
+
<math>\phi(n) = n - (\sum_{1 \le i \le m}\frac{n}{p_i}</math> <math>- \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})</math>
−
+ \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m})\\
+
 
−
&= n(1 - \sum_{1 \le i \le m}\frac{1}{p_i}
+
<math>\phi(n)= 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}}
+
+ \sum_{1 \le i_1 < i_2 \le m}\frac{1}{p_{i_1}p_{i_2}}</math> <math>- \cdots + (-1)^{m}\frac{1}{p_1p_2\ldots p_m})</math>
−
- \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}).
+
<math>\phi(n)= n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m}).</math>
−
\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>
 
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>

Revision as of 23:58, 27 January 2009

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}^{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 $n$ that share a common factor with it). There are $\frac{n}{p_1}$ numbers less than $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 - (\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})$

$\phi(n)= 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})$

$\phi(n)= n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m}).$

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(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_m}).\]

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

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}\varphi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).\]

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=29781"