Euler Phi Extension and Divisor Sum Theorem
![](https://forthright48.com/wp-content/uploads/2015/09/extension-2-1200x800.jpg)
Previously we learned about Euler Phi Function. Today we are going to look at two theorems related to Euler Phi that frequently appears in CPPS. I am not sure whether these theorems have any official names, so I just made them up. These allow easy references so I will be using these names from now on.
Euler Phi Extension Theorem
Theorem: Given a number $N$, let $d$ be a divisor of $N$. Then the number of pairs $\\{a, N \\}$, where $1 \leq a \leq N$ and $gcd(a,N) = d$, is $\phi(\frac{N}{d})$.
Proof
We will prove the theorem using Euler Phi Function and Arithmetic notion.
We need to find the numbe of pairs $\{a, N \}$ such that $gcd(a,N) = d$, where $1 \leq a \leq N$.
Both $a$ and $N$ are divisible by $d$ and $d$ is the GCD. So, if we divide both $a$ and $N$ by $d$, then they will no longer have any common divisor.
$gcd(\frac{a}{d},\frac{N}{d}) = 1$, where $1 \leq a \leq N$.
We know that the possible values of $a$ lie in range $1 \leq a \leq N$. What about the possible values of $\frac{a}{d}$? $\frac{a}{d}$ must lie between $1 \leq \frac{a}{d} \leq \frac{N}{d}$ otherwise $a$ will cross its limit.
Therefore, $gcd(a,N) = d$, where $1 \leq a \leq N$ is same as, $gcd(\frac{a}{d},\frac{N}{d}) = 1$, where $1 \leq \frac{a}{d} \leq \frac{N}{d}$.
So all we need to do is find the value of $gcd(\frac{a}{d},\frac{N}{d}) = 1$, where $1 \leq \frac{a}{d} \leq \frac{N}{d}$.
Let $N’ = \frac{N}{d}$ and $a’ = \frac{a}{d}$. How many pairs of $\{a’, N’ \}$ are there such that $gcd(a’,N’) = 1$ and $1 \leq a’ \leq N’$? Isn’t this what Euler Phi Function finds? The answer is $\phi(N’) = \phi(\frac{N}{d})$.
Try solving the following problem: UVA 12425 – Best Friend
Euler Phi Divisor Sum Theorem
Theorem: For a given integer $N$, the sum of Euler Phi of each of the divisors of $N$ equals to $N$, i.e, $N = \sum_{d|N}\phi(d)$
Proof
The proof is simple. I have broken down the proof in the following chunks for the ease of understanding.
Forming Array $A$
Imagine, we the following fractions in a list:
$$\frac{1}{N}, \frac{2}{N}, \frac{3}{N}…\frac{N}{N}$$
Not very hard to imagine right? Let us convert this into an array of pairs. So now, we have the following array $A$:
$$A = [ {1,N},{2,N},{3,N}…{N,N} ]$$
So we have an array of form $\{a, N \}$, where $a$ is between $1$ and $N$. There are exactly $N$ elements in the array.
Finding GCD of Pairs
Next, we find the GCD of each pair, $g$. What are the possible values of $g$? Since $g$ must divide both $a$ and $N$, $g$ must be a divisor of $N$. Therefore, we can conclude that GCD of pair $\{a, N \}$ will be one of the divisors of $N$.
Let the divisors of $N$ be the following: $d_1, d_2, d_3…d_r$. So these are the only possible GCD.
Forming Parititions
Next, we form partitions $P_i$. Let us put all pairs which have $gcd(a,N) = d_i$ to partition $P_i$. Therefore, we will have $R$ partitions, where $R$ is the number of divisor of $N$. Note that each pair will belong to one partition only since a pair has a unique GCD. Therefore,
$$N = \sum_{i=1}^{R}P_i$$
Size of Each Paritition
How many elements does partition $P_i$ contain? $P_i$ has all the pairs $\{a, N \}$ such that $gcd(a,N) = d_i$, $1 \leq a \leq N$. Using Euler Phi Extension Theorem from above, this value is $\phi(\frac{N}{d_i})$.
Wrapping it Up
We are almost done with the proof. Since $N = \sum_{i=1}^{R}P_i$, we can now write:
$$N = \sum_{i=1}^{R}P_i = \sum_{i=1}^{R}\phi(\frac{N}{d_i})$$
But $d_i$ is just a divisor of $N$. So we can simplify and write:
$$N = \sum_{d|N}\phi(\frac{N}{d}) = \sum_{d|N}\phi(d)$$
Conclusion
These theorems may look so simple that you might think they are useless. Especially Euler Phi Divisor Sum Theorem, $N = \sum_{d|N} \phi(d)$. How is this useful at all? Hopefully, we will see one of its application on next post.
Reference
- forthright48 – Euler Totient or Phi Function
- Wiki – Divisor Sum