Hello codeforces!↵
↵
In one of the recent contests there appeared [a problem](https://codeforces.me/problemset/problem/1717/E) which involved Euler's phi function, and I figured I could write a bit about this function here. ↵
↵
First, I will briefly introduce Euler's phi function, talk about two of its properties, and give you proofs of both of them. Ultimately, it will lead us to a way to compute the value of this function for some given integer n with reasonable time complexity.↵
↵
[cut] ↵
<br>↵
↵
I tried to keep this post quite basic, so that it's accessible to everyone. Therefore, if you are already quite good at some topic mentioned here, feel free to skip a section or two.↵
↵
Also, I would like to say thank you to my friend, [user:sysia,2022-09-11], who helped me a lot with writing this post and suppressed my tendency to write too much.↵
↵
<br>↵
↵
### What is Euler's phi function?↵
↵
Euler's phi function (which may be also called Euler's totient function) is a function that gives us the number of positive integers less or equal to a given integer n that are [coprime](http://en.wikipedia.org/wiki/Coprime_integers) to n. It is usually denoted by the greek letter $\phi$. For instance, if we consider the number 6, there are exactly 3 integers that are not greater than 6 and coprime to it. These intergers are 1, 3 and 5. Therefore $\phi(6) = 3$. Similarly $\phi(9) = 6$. The numbers that are not greater than 9 and coprime to it are 1, 2, 4, 5, 7 and 8. Note that according to the definition $\phi(1) = 1$.↵
↵
<br>↵
↵
### The properties of Euler's phi function↵
↵
Euler's phi function has numerous interesting properties, and if you are looking for the whole list, I suggest that you consult [wikipedia](https://en.wikipedia.org/wiki/Euler%27s_totient_function). For competitive programming, however, two of them are particularly important.↵
↵
**1. Value of phi for an integer power of a prime number**↵
↵
Let $p$ be a prime number and $k$ a positive integer. Then↵
\begin{equation*}↵
\phi(p^k) = p^k — p^{k — 1}.↵
\end{equation*}↵
↵
The proof of this property is quite straightforward. Consider all positive integers that are not greater than $p^k$. Let us count those which are not coprime to $p^k$. An integer is not coprime to $p^k$ if and only if it is a multiple of $p$. We see that there are $p^{k-1}$ multiples of p in the interval $[1, p^k]$. Therefore, there are $p^k - p^{k-1}$ integers which are not multiples of p in this interval. Thus, $\phi(p^k) = p^k - p^{k - 1}$.↵
↵
**2. Multiplicativity under the condition that both arguments are coprime**↵
↵
Let $a$ and $b$ be two coprime positive integers. Then↵
\begin{equation*}↵
\phi(ab) = \phi(a)\phi(b).↵
\end{equation*}↵
↵
This property is a bit trickier to prove and the next two sections are devoted to its proof.↵
↵
<br>↵
↵
### Chinese Remainder Theorem↵
Chinese Remainder Theorem is a well-known topic in competitive programming. Therefore, I would like to keep this section relatively short and not go too much into details. If you want the proof or simply would like to learn more about it, you can visit [this page](https://brilliant.org/wiki/chinese-remainder-theorem/).↵
↵
Now for the theorem itself.↵
Let's say that we have k congruences:↵
\begin{equation*}↵
x \equiv a_1 \;\;\; (mod\;\;n_1),↵
\end{equation*}↵
\begin{equation*}↵
x \equiv a_2 \;\;\; (mod\;\;n_2),↵
\end{equation*}↵
\begin{equation*}↵
...↵
\end{equation*}↵
\begin{equation*}↵
x \equiv a_k \;\;\; (mod\;\;n_k)↵
\end{equation*}↵
such that $n_1, n_2, ..., n_k$ are pairwise coprime (that is, for every pair of integers (i, j) such that $1 \leq i < j \leq k$, we have $gcd(n_i, n_j) = 1$). The Chinese Remainder Theorem says that there exists exactly one integer $x$ in the interval $[0, n_1 \, \cdot \, n_2 \, \cdot \, ... \, \cdot \, n_k - 1]$ that satisfies all the congruences.↵
↵
Let's have a look at an example. Consider the following congruences↵
\begin{equation*}↵
x \equiv 1 \;\;\; (mod \;\; 5),↵
\end{equation*}↵
\begin{equation*}↵
x \equiv 3 \;\;\; (mod \;\; 4),↵
\end{equation*}↵
\begin{equation*}↵
x \equiv 6 \;\;\; (mod \;\; 9).↵
\end{equation*}↵
↵
One can check that the only integer in the interval $[0, 179]$ that satisfies all of them is 41.↵
↵
In fact, there is [an algorithm](https://codeforces.me/blog/entry/61290) that allows us to find $x$ given $a_1, a_2, ..., a_k$ and $n_1, n_2, ..., n_k$.↵
↵
For the purpose of this blog, however, we will consider only the case where $k=2$. Let's say we have two coprime positive integers $n_1$ and $n_2$. What the theorem says is that for every pair of integers $(a_1, a_2)$ ($0 \leq a_1 < n_1$, $0 \leq a_2 < n_2$) there exists exactly one integer $x$ in the interval $[0, n_1 \cdot n_2 - 1]$ such that $x \equiv a_1 \; (mod \; n_1)$ and $x \equiv a_2 \; (mod \; n_2)$. In other words, every pair of integers $(a_1, a_2)$ uniquely determines some integer $x$ in the interval $[0, n_1 \cdot n_2 - 1]$.↵
↵
Now let's notice that every integer $x$ in the interval $[0, n_1 \cdot n_2 - 1]$ also uniquely determines some pair $(a_1, a_2)$, namely the pair $(x \; mod \; n_1, \; x \; mod \; n_2)$.↵
↵
Let's have a look at an example below. We have $n_1 = 3$ and $n_2 = 4$. In the picture we have pairs $(a_1, a_2)$ on the left and integers from 0 to 11 on the right. Arrows are drawn between each pair and its corresponding integer. Note that each pair has exactly one corresponding integer and each integer has exactly one corresponding pair.↵
↵
↵
↵
With Euler's phi function we deal with intervals of the form $[1, n]$, whereas in CRT they are usually of the form $[0, n - 1]$. It turns out that it doesn't really matter. We could change the interval in CRT to the form of $[1, n]$ and the theorem will still be true. If you don't see it immediately, take your time to convince yourself. From now on, we will be using the $[1, n]$ convention.↵
↵
For the rest of this blog I am going to call the pair $(a_1, a_2) = (x \; mod \; n_1, x \; mod \; n_2)$ the pair corresponding to $x$. Similarly, I am going to call the integer $x$ in the interval $[1, n_1 \cdot n_2]$ such that $a_1 = x \; mod \; n_1$ and $a_2 = x \; mod \; n_2$ the integer corresponding to the pair $(a_1, a_2)$. ↵
↵
<br>↵
↵
### The proof of multiplicativity↵
↵
Now that we have learnt about CRT, we can finally prove the second property of our function. To do so, let's prove the following lemma.↵
↵
**Lemma**: Let $n_1$ and $n_2$ be two coprime integers. A positive integer $x \leq n_1 \cdot n_2$ is coprime to $n_1 \cdot n_2$ if and only if $gcd(x \; mod \; n_1, n_1) = 1$ and $gcd(x \; mod \; n_2, n_2) = 1$.↵
↵
We can rephrase this lemma with two statements:↵
↵
Firstly, for every pair of integers $(a_1, a_2)$ such that $0 \leq a_1 < n_1$, $0 \leq a_2 < n_2$, $gcd(a_1, n_1) = 1$, and $gcd(a_2, n_2) = 1$, the integer $x$ corresponding to this pair is coprime to $n_1 \cdot n_2$. ↵
↵
Secondly, for every integer $x$ in the interval $[1, n_1 \cdot n_2]$ that is coprime to $n_1 \cdot n_2$, its corresponding pair $(a_1, a_2)$ has the following property: $gcd(x \; mod \; n_1, n_1) = 1$ and $gcd(x \; mod \; n_2, n_2) = 1$.↵
↵
<br>↵
↵
<spoiler summary="A proof of the first statement">↵
We have a pair of integers $(a_1, a_2)$ such that $0 \leq a_1 < n_1$, $0 \leq a_2 < n_2$, $gcd(a_1, n_1) = 1$, and $gcd(a_2, n_2) = 1$. Let $x$ be the integer corresponding to this pair. We will prove that $x$ is coprime to $n_1 \cdot n_2$ by contradiction. Suppose that there exists some prime number $p$ such that $p$ divides both $x$ and $n_1 \cdot n_2$, that is $x$ and $n_1 \cdot n_2$ are not coprime. If $p$ divides $n_1 \cdot n_2$, then<br> one of these three conditions must hold:↵
↵
1. $p \; | \; n_1$ and $p \not| \; \ n_2$↵
2. $p \; | \; n_2$ and $p \not| \; \ n_1$ ↵
3. $p \; | \; n_1$ and $p \; \ | \; \ n_2$↵
↵
This is due to the fact that $p$ is prime and $n_1$ is coprime to $n_2$. Without loss of generality, let's say that $p$ divides $n_1$. Since $a_1 = x \; mod \; n_1$, we have↵
\begin{equation*}↵
x = a_1 + k \cdot n_1↵
\end{equation*}↵
for some integer $k$. Then we see that↵
\begin{equation*}↵
a_1 = x — k \cdot n_1.↵
\end{equation*}↵
Now let's notice that both $x$ and $n_1$ are divisible by $p$, so $x - k \cdot n_1$ must be divisible by $p$ as well. We conclude that $a_1$ is divisible by $p$. However, it is contradictory with our assumption. We assumed that $a_1$ is coprime to $n_1$, but there is some number $p > 1$ that divides both $a_1$ and $n_1$. Thus, our claim that there exists some prime number $p$ such that $p$ divides both $x$ and $n_1 \cdot n_2$ is false.↵
</spoiler>↵
↵
<spoiler summary="A proof of the second statement">↵
We have an integer $x$ in the interval $[1, n_1 \cdot n_2]$ such that $x$ is coprime to $n_1 \cdot n_2$. We will prove that the pair $(a_1, a_2)$ corresponding to $x$ has the following property: $a_1$ is co-prime to $n_1$ and $a_2$ is coprime to $n_2$. Again, we will prove it by contradiction. Suppose that there exists some integer $d > 1$ such that $d$ divides both $a_1$ and $n_1$. From the definition of $a_1$ we have↵
\begin{equation*}↵
a_1 = x \; mod \; n_1,↵
\end{equation*}↵
which means that↵
\begin{equation*}↵
x = a_1 + k \cdot n_1↵
\end{equation*}↵
for some integer $k$. We supposed that $a_1$ and $n_1$ are both divisible by $d$, so their sum is also divisible by $d$. Thus, $x$ is also divisible by $d$. It means that we have found an integer $d > 1$ such that $d$ divides both $x$ and $n_1$. If $d$ divides $n_1$, then it obviously divides $n_1 \cdot n_2$, so $x$ and $n_1 \cdot n_2$ are not coprime. This contradiction proves that $a_1$ has to be coprime to $n_1$. The reasoning for $a_2$ and $n_2$ is the same, which concludes our proof.↵
</spoiler>↵
↵
Now, consider two coprime integers $n_1$ and $n_2$. We know that every number $x$ in the interval $[1, n_1 \cdot n_2]$ that is coprime to $n_1 \cdot n_2$ has its corresponding pair of integers $(a_1, a_2)$ such that $a_1$ is coprime to $n_1$ and $a_2$ is coprime to $n_2$. It also works the other way, every pair of integers $(a_1, a_2)$ such that $a_1$ is coprime to $n_1$ and $a_2$ is coprime to $n_2$ has its corresponding integer $x$ coprime to $n_1 \cdot n_2$.↵
↵
Therefore, the number of positive integers that are not greater than $n_1 \cdot n_2$ and coprime to it is equal to the number of pairs $(a_1, a_2)$ where $0 \leq a_1 < n_1$ and $0 \leq a_2 < n_2$ such that $a_1$ is coprime to $n_1$ and $a_2$ is coprime to $n_2$. The number of such pairs is obviously $\phi(n_1) \phi(n_2)$ since we can choose $a_1$ in $\phi(n_1)$ ways and $a_2$ in $\phi(n_2)$ ways. Thus,↵
\begin{equation*}↵
\phi(n_1 \cdot n_2) = \phi(n_1) \cdot \phi(n_2).↵
\end{equation*}↵
↵
Let's have a look at the example below. It's the picture from the previous section, but this time I marked certain pairs and numbers with a nice greenish colour. The numbers marked are those which are coprime to 12, and the pairs marked are those pairs $(a_1, a_2)$ that satisfy the property that $a_1$ is coprime to 3 and $a_2$ is coprime to 4. What our lemma says is that the marked numbers correspond to the marked pairs and vice versa.↵
↵
↵
↵
Alternatively, we can use a bit more math notation and say the following.↵
↵
Let A be the set of positive integers not greater than $n_1$ that are coprime to $n_1$, namely↵
↵
<p>↵
↵
$$ A = \left\{ x \in \mathbb{Z} : 1 \leq x \leq n_1 \; \ and \; \ gcd(x, n_1) = 1 \right\}. $$↵
↵
</p>↵
↵
We define B and C in a similar manner↵
↵
<p>↵
↵
$$↵
B = \left\{ x \in \mathbb{Z} : 1 \leq x \leq n_2 \; \ and \; \ gcd(x, n_2) = 1 \right\},↵
$$↵
↵
</p>↵
<p>↵
↵
$$↵
C = \left\{ x \in \mathbb{Z} : 1 \leq x \leq n_1 \cdot n_2 \; \ and \; \ gcd(x, n_1 \cdot n_2) = 1 \right\}.↵
$$↵
↵
</p>↵
↵
Note that by definition $\phi(n_1) = |A|$, $\phi(n_2) = |B|$, and $\phi(n_1 \cdot n_2) = |C|$. Our lemma tells us that there exists [a bijection](https://en.wikipedia.org/wiki/Bijection) between $A \times B$ and $C$. Therefore, $|A \times B| = |C|$. We know that $|A \times B| = |A| \cdot |B| = \phi(n_1) \phi(n_2)$, so $|C| = \phi(n_1) \phi(n_2)$. Using the fact that $|C| = \phi(n_1 \cdot n_2)$, we get ↵
\begin{equation*}↵
\phi(n_1 \cdot n_2) = \phi(n_1) \phi(n_2).↵
\end{equation*} ↵
↵
Note that here $A \times B$ is defined as follows↵
↵
<p>↵
$$↵
A \times B = \left\{ (a, b) : a \in A \; \ and \; \ b \in B \right\}.↵
$$↵
</p>↵
↵
<br>↵
↵
### Evaluating Euler's phi function↵
↵
In order to compute $\phi(n)$ we will exploit the two properties that appeared earlier in this post. Consider the prime factorisation of n↵
\begin{equation*}↵
n = p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} \dots p_k ^ {\alpha_k}.↵
\end{equation*}↵
Note that each of the numbers $p_1 ^ {\alpha_1}, p_2 ^ {\alpha_2}, ..., p_k ^ {\alpha_k}$ is a power of some prime number, so we can easily evaluate $\phi(p_1 ^ {\alpha_1}), \phi(p_2 ^ {\alpha_2}), ..., \phi(p_k ^ {\alpha_k})$ using the first property of our function. Namely,↵
\begin{equation*}↵
\phi(p_1 ^ {\alpha_1}) = p_1 ^ {\alpha_1} — p_1 ^ {\alpha_1 — 1},↵
\end{equation*}↵
\begin{equation*}↵
\phi(p_2 ^ {\alpha_2}) = p_2 ^ {\alpha_2} — p_2 ^ {\alpha_2 — 1},↵
\end{equation*}↵
\begin{equation*}↵
...↵
\end{equation*}↵
\begin{equation*}↵
\phi(p_k ^ {\alpha_k}) = p_k ^ {\alpha_k} — p_1 ^ {\alpha_k — 1}.↵
\end{equation*}↵
Moreover, these number are pairwise coprime, so in order to compute $\phi(p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} ... p_k ^ {\alpha_k})$, we can just take the product of the value of $\phi$ for each of them. We obtain↵
\begin{equation*}↵
\phi(n) = ↵
\end{equation*}↵
\begin{equation*}↵
= \phi(p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} ... p_k ^ {\alpha_k}) =↵
\end{equation*}↵
\begin{equation*}↵
= \phi(p_1 ^ {\alpha_1}) \cdot \phi(p_2 ^ {\alpha_2}) ... \phi(p_k ^ {\alpha_k}) = ↵
\end{equation*}↵
\begin{equation*}↵
= (p_1 ^ {\alpha_1} — p_1 ^ {\alpha_1 — 1})( p_2 ^ {\alpha_2} — p_2 ^ {\alpha_2 — 1} ) \; ... \; (p_k ^ {\alpha_k} — p_1 ^ {\alpha_k — 1}).↵
\end{equation*}↵
↵
Note that this formula is usually given in a slightly different form:↵
\begin{equation*}↵
\phi(n) = n \cdot \left( 1 — \frac{1}{p_1} \right) \cdot \left( 1 — \frac{1}{p_2} \right) \cdot ... \cdot \left( 1 — \frac{1}{p_k} \right).↵
\end{equation*}↵
↵
If you don't immediately see that the two formulas above are the same, you can take time to convince yourself that it is indeed true. It's quite understandable why the latter is usually given. It's quite a beautiful formula in fact. Mathematics at its finest. I personally prefer to look at it this way (and [user:sysia,2022-09-11] does so too).↵
↵
Now, having our formula↵
\begin{equation*}↵
\phi(n) = (p_1 ^ {\alpha_1} — p_1 ^ {\alpha_1 — 1})( p_2 ^ {\alpha_2} — p_2 ^ {\alpha_2 — 1} ) \; ... \; (p_k ^ {\alpha_k} — p_1 ^ {\alpha_k — 1}),↵
\end{equation*}↵
↵
we can easily compute $\phi(n)$ in $O(log \; n)$ time if we know the prime factorisation of n. We don't even need to use fast exponentiation, since the sum $\alpha_1 + \alpha_2 + ... + \alpha_k$ is bounded by $O(log \; n)$. Here is a C++ function that returns $\phi(n)$:↵
↵
~~~~~↵
int phi(int n) {↵
vector<pair<int, int>>divisors = factorize(n); ↵
//pairs {prime number, exponent}↵
↵
int ans = 1;↵
for(auto [prime, exp] : divisors) {↵
int power = 1;↵
for (int i = 1; i<exp; i++){↵
power *= prime;↵
} ↵
ans *= (power * prime - power); // (p^exp - p^{exp-1})↵
}↵
return ans;↵
}↵
~~~~~↵
↵
The bottleneck here is the time complexity of factorisation. We could just use a simple $O(\sqrt{n})$ algorithm or, if you want to deal with really large numbers, you can get more fancy and use [Pollard's rho algorithm](https://cp-algorithms.com/algebra/factorization.html#pollards-rho-algorithm), which should work in $O(n ^ {\frac{1}{4}})$ (this time complexity analysis is heuristic, but the algorithm is quite fast in practice).↵
↵
If you want to compute $\phi(k)$ for every $k$ from 1 up to some integer $n$, then it's possible to make it even faster. Using an idea similar to [the sieve of Eratosthenes](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html), we can precompute an array $sieve$ (0-indexed) of size $n + 1$ so that $sieve_x$ is equal to some prime divisor of $x$ (it doesn't matter which one). ↵
↵
Now, we will compute $phi_i$ for each $i$ from $1$ to $n$. When we compute $phi_i$ for some $i$, we will use the fact the we have already computed $phi_j$ for $1 \leq j < i$. We take some prime divisor $p$ of $i$ from $sieve_i$ and find the greatest power $k$ such that $p ^ k \; | \; i$. We know that $i = p^k \cdot \frac{i}{p^k}$. Moreover, $gcd \left( p^k, \frac{i}{p ^ k} \right) = 1$. Therefore, we can set $phi_i = (p^k - p^{k - 1}) \cdot phi_{\frac{i}{p^k}}$. Here is a C++ function that uses this idea↵
↵
↵
~~~~~↵
vector<int> phi_from_1_to_n(int n) {↵
vector<int>phi(n + 1, 1), sieve(n + 1, -1);↵
↵
for(int i = 2; i <= n; i++) {↵
if(sieve[i] == -1) {↵
sieve[i] = i;↵
for(long long j = 1ll * i * i; j <= n; j += i)↵
sieve[j] = i;↵
}↵
}↵
↵
for(int i = 2; i <= n; i++) {↵
int p = sieve[i], j = i;↵
while(j % p == 0) {↵
phi[i] *= p;↵
j /= p;↵
}↵
//j is now equal to i / p^k↵
phi[i] = (phi[i] / p) * (p - 1) * phi[j];↵
}↵
return phi;↵
}↵
~~~~~↵
↵
An obvious bound for the time complexity of this function is $O(n \, log \, n)$ (with relatively small constant, though). However, I can't prove that there doesn't exist a better bound. If some of you can find a better bound, or can prove that $O(n \, log \, n)$ is the best we can get, I'd love to read about it in the comments.↵
↵
<br>↵
↵
### Practice problems↵
↵
Here is a couple of practice problems. If you know any problems related to this topic that are not mentioned here, you can mention them in the comments.↵
↵
1. [problem:1717E]↵
2. [VJUDGE — GCD — Extreme (II)](https://vjudge.net/problem/UVA-11426) (suggested by [user:18o3,2022-09-12])↵
3. [SPOJ — ETF — Euler Totient Function](https://www.spoj.com/problems/ETF/)↵
↵
<br>↵
↵
### Conclusion↵
↵
That's the end of this post. I hope you benefited from it and, most importantly, liked it. Also, it's my first post here, so any suggestions from you will be appreciated. Lastly, if you know some more interesting properties of Euler's totient function that may come in handy in competitive programming, you can consider sharing them with us in the comments.↵
↵
Have a good day there!↵
↵
↵
In one of the recent contests there appeared [a problem](https://codeforces.me/problemset/problem/1717/E) which involved Euler's phi function, and I figured I could write a bit about this function here. ↵
↵
First, I will briefly introduce Euler's phi function, talk about two of its properties, and give you proofs of both of them. Ultimately, it will lead us to a way to compute the value of this function for some given integer n with reasonable time complexity.↵
↵
[cut] ↵
<br>↵
↵
I tried to keep this post quite basic, so that it's accessible to everyone. Therefore, if you are already quite good at some topic mentioned here, feel free to skip a section or two.↵
↵
Also, I would like to say thank you to my friend, [user:sysia,2022-09-11], who helped me a lot with writing this post and suppressed my tendency to write too much.↵
↵
<br>↵
↵
### What is Euler's phi function?↵
↵
Euler's phi function (which may be also called Euler's totient function) is a function that gives us the number of positive integers less or equal to a given integer n that are [coprime](http://en.wikipedia.org/wiki/Coprime_integers) to n. It is usually denoted by the greek letter $\phi$. For instance, if we consider the number 6, there are exactly 3 integers that are not greater than 6 and coprime to it. These intergers are 1, 3 and 5. Therefore $\phi(6) = 3$. Similarly $\phi(9) = 6$. The numbers that are not greater than 9 and coprime to it are 1, 2, 4, 5, 7 and 8. Note that according to the definition $\phi(1) = 1$.↵
↵
<br>↵
↵
### The properties of Euler's phi function↵
↵
Euler's phi function has numerous interesting properties, and if you are looking for the whole list, I suggest that you consult [wikipedia](https://en.wikipedia.org/wiki/Euler%27s_totient_function). For competitive programming, however, two of them are particularly important.↵
↵
**1. Value of phi for an integer power of a prime number**↵
↵
Let $p$ be a prime number and $k$ a positive integer. Then↵
\begin{equation*}↵
\phi(p^k) = p^k — p^{k — 1}.↵
\end{equation*}↵
↵
The proof of this property is quite straightforward. Consider all positive integers that are not greater than $p^k$. Let us count those which are not coprime to $p^k$. An integer is not coprime to $p^k$ if and only if it is a multiple of $p$. We see that there are $p^{k-1}$ multiples of p in the interval $[1, p^k]$. Therefore, there are $p^k - p^{k-1}$ integers which are not multiples of p in this interval. Thus, $\phi(p^k) = p^k - p^{k - 1}$.↵
↵
**2. Multiplicativity under the condition that both arguments are coprime**↵
↵
Let $a$ and $b$ be two coprime positive integers. Then↵
\begin{equation*}↵
\phi(ab) = \phi(a)\phi(b).↵
\end{equation*}↵
↵
This property is a bit trickier to prove and the next two sections are devoted to its proof.↵
↵
<br>↵
↵
### Chinese Remainder Theorem↵
Chinese Remainder Theorem is a well-known topic in competitive programming. Therefore, I would like to keep this section relatively short and not go too much into details. If you want the proof or simply would like to learn more about it, you can visit [this page](https://brilliant.org/wiki/chinese-remainder-theorem/).↵
↵
Now for the theorem itself.↵
Let's say that we have k congruences:↵
\begin{equation*}↵
x \equiv a_1 \;\;\; (mod\;\;n_1),↵
\end{equation*}↵
\begin{equation*}↵
x \equiv a_2 \;\;\; (mod\;\;n_2),↵
\end{equation*}↵
\begin{equation*}↵
...↵
\end{equation*}↵
\begin{equation*}↵
x \equiv a_k \;\;\; (mod\;\;n_k)↵
\end{equation*}↵
such that $n_1, n_2, ..., n_k$ are pairwise coprime (that is, for every pair of integers (i, j) such that $1 \leq i < j \leq k$, we have $gcd(n_i, n_j) = 1$). The Chinese Remainder Theorem says that there exists exactly one integer $x$ in the interval $[0, n_1 \, \cdot \, n_2 \, \cdot \, ... \, \cdot \, n_k - 1]$ that satisfies all the congruences.↵
↵
Let's have a look at an example. Consider the following congruences↵
\begin{equation*}↵
x \equiv 1 \;\;\; (mod \;\; 5),↵
\end{equation*}↵
\begin{equation*}↵
x \equiv 3 \;\;\; (mod \;\; 4),↵
\end{equation*}↵
\begin{equation*}↵
x \equiv 6 \;\;\; (mod \;\; 9).↵
\end{equation*}↵
↵
One can check that the only integer in the interval $[0, 179]$ that satisfies all of them is 41.↵
↵
In fact, there is [an algorithm](https://codeforces.me/blog/entry/61290) that allows us to find $x$ given $a_1, a_2, ..., a_k$ and $n_1, n_2, ..., n_k$.↵
↵
For the purpose of this blog, however, we will consider only the case where $k=2$. Let's say we have two coprime positive integers $n_1$ and $n_2$. What the theorem says is that for every pair of integers $(a_1, a_2)$ ($0 \leq a_1 < n_1$, $0 \leq a_2 < n_2$) there exists exactly one integer $x$ in the interval $[0, n_1 \cdot n_2 - 1]$ such that $x \equiv a_1 \; (mod \; n_1)$ and $x \equiv a_2 \; (mod \; n_2)$. In other words, every pair of integers $(a_1, a_2)$ uniquely determines some integer $x$ in the interval $[0, n_1 \cdot n_2 - 1]$.↵
↵
Now let's notice that every integer $x$ in the interval $[0, n_1 \cdot n_2 - 1]$ also uniquely determines some pair $(a_1, a_2)$, namely the pair $(x \; mod \; n_1, \; x \; mod \; n_2)$.↵
↵
Let's have a look at an example below. We have $n_1 = 3$ and $n_2 = 4$. In the picture we have pairs $(a_1, a_2)$ on the left and integers from 0 to 11 on the right. Arrows are drawn between each pair and its corresponding integer. Note that each pair has exactly one corresponding integer and each integer has exactly one corresponding pair.↵
↵
↵
↵
With Euler's phi function we deal with intervals of the form $[1, n]$, whereas in CRT they are usually of the form $[0, n - 1]$. It turns out that it doesn't really matter. We could change the interval in CRT to the form of $[1, n]$ and the theorem will still be true. If you don't see it immediately, take your time to convince yourself. From now on, we will be using the $[1, n]$ convention.↵
↵
For the rest of this blog I am going to call the pair $(a_1, a_2) = (x \; mod \; n_1, x \; mod \; n_2)$ the pair corresponding to $x$. Similarly, I am going to call the integer $x$ in the interval $[1, n_1 \cdot n_2]$ such that $a_1 = x \; mod \; n_1$ and $a_2 = x \; mod \; n_2$ the integer corresponding to the pair $(a_1, a_2)$. ↵
↵
<br>↵
↵
### The proof of multiplicativity↵
↵
Now that we have learnt about CRT, we can finally prove the second property of our function. To do so, let's prove the following lemma.↵
↵
**Lemma**: Let $n_1$ and $n_2$ be two coprime integers. A positive integer $x \leq n_1 \cdot n_2$ is coprime to $n_1 \cdot n_2$ if and only if $gcd(x \; mod \; n_1, n_1) = 1$ and $gcd(x \; mod \; n_2, n_2) = 1$.↵
↵
We can rephrase this lemma with two statements:↵
↵
Firstly, for every pair of integers $(a_1, a_2)$ such that $0 \leq a_1 < n_1$, $0 \leq a_2 < n_2$, $gcd(a_1, n_1) = 1$, and $gcd(a_2, n_2) = 1$, the integer $x$ corresponding to this pair is coprime to $n_1 \cdot n_2$. ↵
↵
Secondly, for every integer $x$ in the interval $[1, n_1 \cdot n_2]$ that is coprime to $n_1 \cdot n_2$, its corresponding pair $(a_1, a_2)$ has the following property: $gcd(x \; mod \; n_1, n_1) = 1$ and $gcd(x \; mod \; n_2, n_2) = 1$.↵
↵
<br>↵
↵
<spoiler summary="A proof of the first statement">↵
We have a pair of integers $(a_1, a_2)$ such that $0 \leq a_1 < n_1$, $0 \leq a_2 < n_2$, $gcd(a_1, n_1) = 1$, and $gcd(a_2, n_2) = 1$. Let $x$ be the integer corresponding to this pair. We will prove that $x$ is coprime to $n_1 \cdot n_2$ by contradiction. Suppose that there exists some prime number $p$ such that $p$ divides both $x$ and $n_1 \cdot n_2$, that is $x$ and $n_1 \cdot n_2$ are not coprime. If $p$ divides $n_1 \cdot n_2$, then<br> one of these three conditions must hold:↵
↵
1. $p \; | \; n_1$ and $p \not| \; \ n_2$↵
2. $p \; | \; n_2$ and $p \not| \; \ n_1$ ↵
3. $p \; | \; n_1$ and $p \; \ | \; \ n_2$↵
↵
This is due to the fact that $p$ is prime and $n_1$ is coprime to $n_2$. Without loss of generality, let's say that $p$ divides $n_1$. Since $a_1 = x \; mod \; n_1$, we have↵
\begin{equation*}↵
x = a_1 + k \cdot n_1↵
\end{equation*}↵
for some integer $k$. Then we see that↵
\begin{equation*}↵
a_1 = x — k \cdot n_1.↵
\end{equation*}↵
Now let's notice that both $x$ and $n_1$ are divisible by $p$, so $x - k \cdot n_1$ must be divisible by $p$ as well. We conclude that $a_1$ is divisible by $p$. However, it is contradictory with our assumption. We assumed that $a_1$ is coprime to $n_1$, but there is some number $p > 1$ that divides both $a_1$ and $n_1$. Thus, our claim that there exists some prime number $p$ such that $p$ divides both $x$ and $n_1 \cdot n_2$ is false.↵
</spoiler>↵
↵
<spoiler summary="A proof of the second statement">↵
We have an integer $x$ in the interval $[1, n_1 \cdot n_2]$ such that $x$ is coprime to $n_1 \cdot n_2$. We will prove that the pair $(a_1, a_2)$ corresponding to $x$ has the following property: $a_1$ is co-prime to $n_1$ and $a_2$ is coprime to $n_2$. Again, we will prove it by contradiction. Suppose that there exists some integer $d > 1$ such that $d$ divides both $a_1$ and $n_1$. From the definition of $a_1$ we have↵
\begin{equation*}↵
a_1 = x \; mod \; n_1,↵
\end{equation*}↵
which means that↵
\begin{equation*}↵
x = a_1 + k \cdot n_1↵
\end{equation*}↵
for some integer $k$. We supposed that $a_1$ and $n_1$ are both divisible by $d$, so their sum is also divisible by $d$. Thus, $x$ is also divisible by $d$. It means that we have found an integer $d > 1$ such that $d$ divides both $x$ and $n_1$. If $d$ divides $n_1$, then it obviously divides $n_1 \cdot n_2$, so $x$ and $n_1 \cdot n_2$ are not coprime. This contradiction proves that $a_1$ has to be coprime to $n_1$. The reasoning for $a_2$ and $n_2$ is the same, which concludes our proof.↵
</spoiler>↵
↵
Now, consider two coprime integers $n_1$ and $n_2$. We know that every number $x$ in the interval $[1, n_1 \cdot n_2]$ that is coprime to $n_1 \cdot n_2$ has its corresponding pair of integers $(a_1, a_2)$ such that $a_1$ is coprime to $n_1$ and $a_2$ is coprime to $n_2$. It also works the other way, every pair of integers $(a_1, a_2)$ such that $a_1$ is coprime to $n_1$ and $a_2$ is coprime to $n_2$ has its corresponding integer $x$ coprime to $n_1 \cdot n_2$.↵
↵
Therefore, the number of positive integers that are not greater than $n_1 \cdot n_2$ and coprime to it is equal to the number of pairs $(a_1, a_2)$ where $0 \leq a_1 < n_1$ and $0 \leq a_2 < n_2$ such that $a_1$ is coprime to $n_1$ and $a_2$ is coprime to $n_2$. The number of such pairs is obviously $\phi(n_1) \phi(n_2)$ since we can choose $a_1$ in $\phi(n_1)$ ways and $a_2$ in $\phi(n_2)$ ways. Thus,↵
\begin{equation*}↵
\phi(n_1 \cdot n_2) = \phi(n_1) \cdot \phi(n_2).↵
\end{equation*}↵
↵
Let's have a look at the example below. It's the picture from the previous section, but this time I marked certain pairs and numbers with a nice greenish colour. The numbers marked are those which are coprime to 12, and the pairs marked are those pairs $(a_1, a_2)$ that satisfy the property that $a_1$ is coprime to 3 and $a_2$ is coprime to 4. What our lemma says is that the marked numbers correspond to the marked pairs and vice versa.↵
↵
↵
↵
Alternatively, we can use a bit more math notation and say the following.↵
↵
Let A be the set of positive integers not greater than $n_1$ that are coprime to $n_1$, namely↵
↵
<p>↵
↵
$$ A = \left\{ x \in \mathbb{Z} : 1 \leq x \leq n_1 \; \ and \; \ gcd(x, n_1) = 1 \right\}. $$↵
↵
</p>↵
↵
We define B and C in a similar manner↵
↵
<p>↵
↵
$$↵
B = \left\{ x \in \mathbb{Z} : 1 \leq x \leq n_2 \; \ and \; \ gcd(x, n_2) = 1 \right\},↵
$$↵
↵
</p>↵
<p>↵
↵
$$↵
C = \left\{ x \in \mathbb{Z} : 1 \leq x \leq n_1 \cdot n_2 \; \ and \; \ gcd(x, n_1 \cdot n_2) = 1 \right\}.↵
$$↵
↵
</p>↵
↵
Note that by definition $\phi(n_1) = |A|$, $\phi(n_2) = |B|$, and $\phi(n_1 \cdot n_2) = |C|$. Our lemma tells us that there exists [a bijection](https://en.wikipedia.org/wiki/Bijection) between $A \times B$ and $C$. Therefore, $|A \times B| = |C|$. We know that $|A \times B| = |A| \cdot |B| = \phi(n_1) \phi(n_2)$, so $|C| = \phi(n_1) \phi(n_2)$. Using the fact that $|C| = \phi(n_1 \cdot n_2)$, we get ↵
\begin{equation*}↵
\phi(n_1 \cdot n_2) = \phi(n_1) \phi(n_2).↵
\end{equation*} ↵
↵
Note that here $A \times B$ is defined as follows↵
↵
<p>↵
$$↵
A \times B = \left\{ (a, b) : a \in A \; \ and \; \ b \in B \right\}.↵
$$↵
</p>↵
↵
<br>↵
↵
### Evaluating Euler's phi function↵
↵
In order to compute $\phi(n)$ we will exploit the two properties that appeared earlier in this post. Consider the prime factorisation of n↵
\begin{equation*}↵
n = p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} \dots p_k ^ {\alpha_k}.↵
\end{equation*}↵
Note that each of the numbers $p_1 ^ {\alpha_1}, p_2 ^ {\alpha_2}, ..., p_k ^ {\alpha_k}$ is a power of some prime number, so we can easily evaluate $\phi(p_1 ^ {\alpha_1}), \phi(p_2 ^ {\alpha_2}), ..., \phi(p_k ^ {\alpha_k})$ using the first property of our function. Namely,↵
\begin{equation*}↵
\phi(p_1 ^ {\alpha_1}) = p_1 ^ {\alpha_1} — p_1 ^ {\alpha_1 — 1},↵
\end{equation*}↵
\begin{equation*}↵
\phi(p_2 ^ {\alpha_2}) = p_2 ^ {\alpha_2} — p_2 ^ {\alpha_2 — 1},↵
\end{equation*}↵
\begin{equation*}↵
...↵
\end{equation*}↵
\begin{equation*}↵
\phi(p_k ^ {\alpha_k}) = p_k ^ {\alpha_k} — p_1 ^ {\alpha_k — 1}.↵
\end{equation*}↵
Moreover, these number are pairwise coprime, so in order to compute $\phi(p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} ... p_k ^ {\alpha_k})$, we can just take the product of the value of $\phi$ for each of them. We obtain↵
\begin{equation*}↵
\phi(n) = ↵
\end{equation*}↵
\begin{equation*}↵
= \phi(p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} ... p_k ^ {\alpha_k}) =↵
\end{equation*}↵
\begin{equation*}↵
= \phi(p_1 ^ {\alpha_1}) \cdot \phi(p_2 ^ {\alpha_2}) ... \phi(p_k ^ {\alpha_k}) = ↵
\end{equation*}↵
\begin{equation*}↵
= (p_1 ^ {\alpha_1} — p_1 ^ {\alpha_1 — 1})( p_2 ^ {\alpha_2} — p_2 ^ {\alpha_2 — 1} ) \; ... \; (p_k ^ {\alpha_k} — p_1 ^ {\alpha_k — 1}).↵
\end{equation*}↵
↵
Note that this formula is usually given in a slightly different form:↵
\begin{equation*}↵
\phi(n) = n \cdot \left( 1 — \frac{1}{p_1} \right) \cdot \left( 1 — \frac{1}{p_2} \right) \cdot ... \cdot \left( 1 — \frac{1}{p_k} \right).↵
\end{equation*}↵
↵
If you don't immediately see that the two formulas above are the same, you can take time to convince yourself that it is indeed true. It's quite understandable why the latter is usually given. It's quite a beautiful formula in fact. Mathematics at its finest. I personally prefer to look at it this way (and [user:sysia,2022-09-11] does so too).↵
↵
Now, having our formula↵
\begin{equation*}↵
\phi(n) = (p_1 ^ {\alpha_1} — p_1 ^ {\alpha_1 — 1})( p_2 ^ {\alpha_2} — p_2 ^ {\alpha_2 — 1} ) \; ... \; (p_k ^ {\alpha_k} — p_1 ^ {\alpha_k — 1}),↵
\end{equation*}↵
↵
we can easily compute $\phi(n)$ in $O(log \; n)$ time if we know the prime factorisation of n. We don't even need to use fast exponentiation, since the sum $\alpha_1 + \alpha_2 + ... + \alpha_k$ is bounded by $O(log \; n)$. Here is a C++ function that returns $\phi(n)$:↵
↵
~~~~~↵
int phi(int n) {↵
vector<pair<int, int>>divisors = factorize(n); ↵
//pairs {prime number, exponent}↵
↵
int ans = 1;↵
for(auto [prime, exp] : divisors) {↵
int power = 1;↵
for (int i = 1; i<exp; i++){↵
power *= prime;↵
} ↵
ans *= (power * prime - power); // (p^exp - p^{exp-1})↵
}↵
return ans;↵
}↵
~~~~~↵
↵
The bottleneck here is the time complexity of factorisation. We could just use a simple $O(\sqrt{n})$ algorithm or, if you want to deal with really large numbers, you can get more fancy and use [Pollard's rho algorithm](https://cp-algorithms.com/algebra/factorization.html#pollards-rho-algorithm), which should work in $O(n ^ {\frac{1}{4}})$ (this time complexity analysis is heuristic, but the algorithm is quite fast in practice).↵
↵
If you want to compute $\phi(k)$ for every $k$ from 1 up to some integer $n$, then it's possible to make it even faster. Using an idea similar to [the sieve of Eratosthenes](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html), we can precompute an array $sieve$ (0-indexed) of size $n + 1$ so that $sieve_x$ is equal to some prime divisor of $x$ (it doesn't matter which one). ↵
↵
Now, we will compute $phi_i$ for each $i$ from $1$ to $n$. When we compute $phi_i$ for some $i$, we will use the fact the we have already computed $phi_j$ for $1 \leq j < i$. We take some prime divisor $p$ of $i$ from $sieve_i$ and find the greatest power $k$ such that $p ^ k \; | \; i$. We know that $i = p^k \cdot \frac{i}{p^k}$. Moreover, $gcd \left( p^k, \frac{i}{p ^ k} \right) = 1$. Therefore, we can set $phi_i = (p^k - p^{k - 1}) \cdot phi_{\frac{i}{p^k}}$. Here is a C++ function that uses this idea↵
↵
↵
~~~~~↵
vector<int> phi_from_1_to_n(int n) {↵
vector<int>phi(n + 1, 1), sieve(n + 1, -1);↵
↵
for(int i = 2; i <= n; i++) {↵
if(sieve[i] == -1) {↵
sieve[i] = i;↵
for(long long j = 1ll * i * i; j <= n; j += i)↵
sieve[j] = i;↵
}↵
}↵
↵
for(int i = 2; i <= n; i++) {↵
int p = sieve[i], j = i;↵
while(j % p == 0) {↵
phi[i] *= p;↵
j /= p;↵
}↵
//j is now equal to i / p^k↵
phi[i] = (phi[i] / p) * (p - 1) * phi[j];↵
}↵
return phi;↵
}↵
~~~~~↵
↵
An obvious bound for the time complexity of this function is $O(n \, log \, n)$ (with relatively small constant, though). However, I can't prove that there doesn't exist a better bound. If some of you can find a better bound, or can prove that $O(n \, log \, n)$ is the best we can get, I'd love to read about it in the comments.↵
↵
<br>↵
↵
### Practice problems↵
↵
Here is a couple of practice problems. If you know any problems related to this topic that are not mentioned here, you can mention them in the comments.↵
↵
1. [problem:1717E]↵
2. [VJUDGE — GCD — Extreme (II)](https://vjudge.net/problem/UVA-11426) (suggested by [user:18o3,2022-09-12])↵
3. [SPOJ — ETF — Euler Totient Function](https://www.spoj.com/problems/ETF/)↵
↵
<br>↵
↵
### Conclusion↵
↵
That's the end of this post. I hope you benefited from it and, most importantly, liked it. Also, it's my first post here, so any suggestions from you will be appreciated. Lastly, if you know some more interesting properties of Euler's totient function that may come in handy in competitive programming, you can consider sharing them with us in the comments.↵
↵
Have a good day there!↵
↵
