Let $\phi(n)$ be Euler's totient function, and $A(m)$ be the number of solutions of $\phi(x)=m$. Let $p, q$ always be prime.
Note: Theorem 1 follows from Theorem 2 by induction on $k$, where we start with $A(10)=2$ and $A(2)=3$. The central idea of the proof is based on Chen's Theorem, which states the following:
Then, the author breaks this theorem into two scenarios:
Thus, at least one of them must be true.
For any of the cases, we look at the "trivial solutions," i.e.
Therefore, we must show that the number of pairs $(p,q)$ that make such solutions non-trivial must be $\ll X/\log^2 X$. The method to obtain such a bound is a collaboration of sieve theory and several bounds related to the prime factors of $p-1$. After all, the cases that are more difficult are the ones with $(n,q)=1$, $(n,pq)=p$, or $q$ and $(n,pq)=1$.
Let's introduce some notations before further developing the logic. Let $P^+(n)$ denote the largest prime factor of $n$ and $P^-(n)$ denote the smallest prime factor of $n$. Let $\omega(n)$ and $\Omega(n)$ count the # of distinct prime factors of $n$ and the # of prime factors counted according to multiplicity, respectively. Let $\Omega(n, U, T)$ denote the # of prime factors $p$ of $n$ s.t. $U \le p < T$ counted according to multiplicity.
We now introduce the lemma of the so-called "Fundamental Lemma of Brun's Sieve".
This follows directly from Lemma 1 by considering the case $\varpi | E$ and bounding the $\varpi | E$ terms.
This is the main theorem in "On the normal number of prime factors of $p-1$ and some related problems concerning Euler's $\phi$-function" by Paul Erdős.
For $\exp((\log \log X)^2) \le y \le X$, let $G(y)$ denote the number of $s \le y$ with $P^+(s) \le y^{10/\log \log X}$. Let $n$ denote a number with $P^+(n) \le W := y^{10/\log \log X}$, and set $\alpha = 1 - \frac{20 \log \log X}{\log y}$. Then
\[ G(y) \le \sum_{n \le y} \left(\frac{y}{n}\right)^\alpha < y^\alpha \sum_{n=1}^\infty n^{-\alpha} \le \frac{y}{(\log X)^{20}} \prod_{p \le W} (1 - p^{-\alpha})^{-1} \ll \frac{y}{(\log X)^{20}} \exp\left(\sum_{p \le W} p^{-\alpha}\right). \]By PNT, $\sum_{p \le W} p^{-\alpha} \le (1+o(1)) \int_2^W t^{-\alpha} d\left(\frac{t}{\log t}\right) \le 2 \log \log X$ for sufficiently large $X$. Thus $G(y) \ll y/(\log X)^{18}$, the number in the Lemma is
\[ \ll \sum_{s \leq X} \frac{X}{s} = X \int \frac{1}{t} dG(t) \ll \frac{X}{(\log X)^{10}}. \tag*{$\square$} \]Using Lemma 2, we can bound the number of primes $q \in (X/2, X]$ with $s=qm+1$ prime, and $dq+1$ is also a prime with $d,m$ fixed. And this is exactly what happens when $q|n$, $q^2 \nmid n$, and $\phi(n/q)=qm$ have a non-trivial solution, i.e., we have $dq+1 | \phi(n)$, where $dq+1$ is prime. Take $d$ sufficiently large such that $d > 2\alpha_i$ where $\phi(\alpha_i)=m$ for $i=1,\dots,k$. Then it leaves us to check the case $(n,q)=1$ where $\phi(n)=q(q-1)m$, since if $q^2|n$, then $n$ is one of the trivial solutions.
The case (i) then follows from Lemma 5.
We remove the cases, as in Lemma 4, for $q-1$, which has such a divisor $s$. For $\phi(n)=mq(q-1)$, $r$ prime with $r|n$ and $r|q-1$. Write $r=1+q s_0$ and $w_0 = \phi(n/r)$. For some factorization of $m=m_1 m_2$, where $m_1 | s_0$ and $m_2 | w_0$. Fix $m_1, m_2$ and let $s=s_0/m_1$ and $w=w_0/m_2$ so that $sw=q-1$. Therefore, it suffices to bound pairs of $(s,w)$ for which $y/2-1 \le sw \le y$ where $wm_2$ is a totient function, subject to the conditions:
\[ ws+1 = q, \quad (ws+1)mb+1 \text{ is prime}, \quad (ws+1)sm_1+1 = r \text{ is prime}. \]For some bounded $s$, we can apply Lemma 2 with $s$ fixed and satisfying the above conditions, which are prime numbers. However, for a certain range of $s$, we need to fix $w$ in some intervals. It follows that for a fixed $w$, by applying Lemma 2 and its remark, we have a quadratic function; thus, we need to deal with the Legendre symbols.
The proof of Lemma 6 is based on several previous Lemmas.
The Prime Number Theorem in Arithmetic Progression tells us that if $z \ge Q^{\log \log Q}$, then
\[ \pi(z; n, a) = \frac{z}{\phi(n) \log z} (1 + O((\log Q)^{-b})) \]for some absolute constant $b$, $a < b < 1$. Since $-\frac{1}{2} \le h \le \frac{1}{2}$, we look at the sum over $\frac{1}{\varpi} \leg{D}{\varpi}$. Let $D=D_1 D_2$ where $D_2$ is the largest positive odd divisor of $D$. Then
\[ \leg{D}{\varpi} = (-1)^{(\varpi-1)(D_2-1)/4} \leg{D_1}{\varpi} \leg{\varpi}{D_2} = i_\varpi \leg{\varpi}{D_2}, \]where $i_\varpi \in \{-1, 1\}$ depends only on $\varpi$ modulo 8. Thus, we sum over residue classes modulo $8D_2$ of $\varpi$, and we are left with an error term of $O(\frac{\log \log Z}{(\log Q)^b}) = O(1)$.
From these two lemmas, combined with Lemma 3, we can bound the case in which we have a quadratic function for modulo $\varpi$. This completes the proof of Theorem 2 in the case (i).
For case (ii), the steps and Lemmas are similar.
We now introduce an important lemma relating to the distribution of the prime factors of $q-1$. For brevity, write $E(z) = \exp\{(\log x)^z\}$.
By Lemma 4, $\#\{p \le y : P^+(p-1) \le y^{1/\log \log x}\} < y(\log x)^{-10}$. For the remaining $p$, let $q = P^+(p-1)$ and $p-1 = qa$. For fixed $a$, by Lemma 2,
\[ \#\{q \le y/a : qa+1 \text{ prime}\} \ll \frac{y}{a} \frac{\log \log x}{\log^2(y/a)}. \]Let $I_j = [E(j\delta), E((j+1)\delta)]$, $t = (\delta+\delta^2)\log \log x - 1$. Since $1_{\{\Omega(a, I_j) \ge t\}} \le (1+\delta)^{-t} (1+\delta)^{\Omega(a, I_j)}$, then
\[ B_j = \sum_{a \le x} \frac{(1+\delta)^{\Omega(a, I_j)}}{a} \ll (\log x)^{(\delta+\delta^2)\log(1+\delta)} \prod_{p \in I_j} \dots \ll (\log x)^{1-0.9\delta^3}. \]Thus, it completes the proof. ◼
Now, we begin to analyze the situation in case (ii). Let $s=1+pqm$ such pairs of $(p,q)$. The author first removes certain parts from $X$ so that he can bound the number of distinct prime divisors for $\phi(n)=mpq(p-1)(q-1)$. Then, by imposing some additional conditions on the set of $(p,q)$ in the set $B$ with $|B| \gg X/\log^2 X$, $s \in (X/2, X]$, and $p,q \in [X^{1/10}, X^{1/2}]$. Let $B$ denote additional conditions that combine with similar steps as for the previous remaining set. We obtain a bound for $(n,q)=1$, allows us to bound the case $(n,pq)=p$ or $q$. Note that one of the additional conditions being imposed is the prime factor distribution condition for $p-1$ in some fixed interval, as stated in Lemma 9.
Case $(n,pq)=1$: Let $E_j = \exp\{(\log x)^{1-j\delta}\}$, where $\delta=1/N$ and $N$ depend on $m$ being large. For the prime divisors of $n \ge E_{N-1}$, without loss of generality, we assume they divide $n$ to the first power. Let $r_1, \dots, r_M$ be the prime factors of $n$ satisfying $(M \le N)$ $P^-(r_i^*) > E_{N-1}$ where $r_i^* := \frac{r_i-1}{(r_i-1, pq)}$. Then
\[ r_1^* \dots r_M^* w^* = m(p-1)(q-1) \]where $w = \phi\left(\frac{n}{r_1 \dots r_M}\right)$, $w^* = \frac{w}{(w, pq)}$. Thus, by considering the number of solutions to the above equation, we bound the number of pairs of $(p,q)$. Define $r_i$ ordered by $P^+(r_i^*) \in I_{j_i}$ and such that $1=j_1 \le j_2 \le \dots \le j_M$. Since $j_i \in [1, N-1]$, $N$ depends on $m$, we may fix $j_1, \dots, j_M$ with choices of $O(1)$. We then further partition the prime factors of $p-1, q-1$ into each interval $I_j$ ($1 \le j \le N$).
Then, for step $j$, we consider the relation between $I_{j_i}$ and $I_j$ for each prime factor in the interval $I_j$ while fixing the smaller factors $< E_j$. Note that the factors of $p-1, q-1$ and $r_i^*$ must satisfy the condition where $p-1, q-1$ and $r_i^*$ are primes (in the sieve context), so that we can apply the sieve in Lemma 2. Moreover, since $p|r_i-1$ and $q|r_{i'}-1$ for $i, i' \in [1, M]$, this gives a quadratic form, so we apply some bounds related to the Legendre symbol, which are similar to Lemma 6. Therefore, after computing the possible factors for $p-1, q-1$ and $r_i^*$ in each step $j$, we obtain the bound for the solution set for
\[ r_1^* \dots r_M^* w^* = m(p-1)(q-1) \]i.e., the bound for $(p,q) \in B$ with $(n, pq)=1$. This completes the proof of Theorem 1.