Euler Phi Extension and Divisor Sum Theorem
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