# Let $n=apq+1$. Prove that if $pq \ | \ \phi(n)$ then $n$ is prime.

Let $$p$$ and $$q$$ be distinct odd primes and $$a$$ be a positive integer with $$a. I need to prove that if $$pq \ | \ \phi(n)$$ then $$n$$ is prime. The proof for the trivial case when $$a=2$$ is given below.

Proof. Let $$n=2pq+1$$. Assume $$pq \ | \ \phi(n)$$. We may write $$\phi(n) = cpq$$ for some positive integer $$c \le 2$$. We know that $$\phi(n)$$ is even for all $$n>2$$ therefore we must have $$c=2$$ otherwise $$\phi(n)$$ is odd. $$\phi(n) =2pq=n-1$$ which shows that $$n$$ is prime. This completes the proof for the trivial case $$a=2$$.

How do I prove that the proposition holds for an arbitrary positive integer $$a$$?

The equation for $$n$$ is given as

$$n = apq + 1 \tag{1}\label{eq1A}$$

As you've already indicated, if $$n$$ is prime, then $$\varphi(n) = n - 1 = apq$$, so $$pq \mid \varphi(n)$$.

Consider the opposite direction, i.e., $$pq \mid \varphi(n)$$. With the definition of Euler's totient function, since $$\gcd(pq, n) = 1$$, this means $$pq$$ must divide $$\prod_{p_i \mid n}(p_i - 1)$$, so either $$p$$ and $$q$$ divide $$2$$ different factors, or $$pq$$ divides just $$1$$ factor, among the $$p_i - 1$$ factors, where the $$p_i$$ are the prime factors of $$n$$. Thus, there's two cases to consider.

Case #$$1$$:

Here, $$n$$ is not a prime, with there being two odd primes $$p_{1}$$ and $$p_{2}$$ where

$$p_{1}p_{2} \mid n \implies n = bp_{1}p_{2}, \; b \ge 1 \tag{2}\label{eq2A}$$

$$p \mid p_{1} - 1 \implies p_{1} = cp + 1, \; c \ge 2 \tag{3}\label{eq3A}$$

$$q \mid p_{2} - 1 \implies p_{2} = dq + 1, \; d \ge 2 \tag{4}\label{eq4A}$$

Substituting \eqref{eq3A} and \eqref{eq4A} into \eqref{eq2A}, and equating the result to \eqref{eq1A}, gives

\begin{aligned} b(cp + 1)(dq + 1) & = apq + 1 \\ (bcd)pq + bcp + bdq + b & = apq + 1 \\ bcp + bdq + b - 1 & = (a - bcd)pq \end{aligned}\tag{5}\label{eq5A}

The left side is positive, so the right side must be as well. This means

$$a \gt bcd \tag{6}\label{eq6A}$$

From \eqref{eq6A}, plus that $$c \ge 2$$ from \eqref{eq3A} and $$d \ge 2$$ from \eqref{eq4A}, we also get $$bc \lt \frac{a}{d} \le \frac{a}{2}$$, $$bd \lt \frac{a}{c} \le \frac{a}{2}$$ and $$b \lt a$$. Using this, along with $$p \le q - 2$$, in the left side of \eqref{eq5A} gives

\begin{aligned} bcp + bdq + b - 1 & \lt \frac{ap}{2} + \frac{aq}{2} + a \\ & = a\left(\frac{p + q}{2} + 1\right) \\ & \le a\left(\frac{q - 2 + q}{2} + 1\right) \\ & = a\left(q - 1 + 1\right) \\ & = aq \end{aligned}\tag{7}\label{eq7A}

However, since the left side of \eqref{eq5A} must be equal to a positive multiple of $$pq$$, this gives

$$aq \gt pq \implies a \gt p \tag{8}\label{eq8A}$$

which contradicts the requirement of $$a \lt p$$. Thus, this case is not valid.

Case #$$2$$:

Here, there is an odd prime $$p_{3}$$ where

$$p_{3} \mid n \implies n = ep_{3}, \; e \ge 1 \tag{9}\label{eq9A}$$

$$pq \mid p_{3} - 1 \implies p_{3} = fpq + 1, \; f \ge 2 \tag{10}\label{eq10A}$$

Substituting \eqref{eq10A} into \eqref{eq9A}, and equating the result to \eqref{eq1A}, gives

\begin{aligned} e(fpq + 1) & = apq + 1 \\ (ef)pq + e & = apq + 1 \\ e - 1 & = (a - ef)pq \end{aligned}\tag{11}\label{eq11A}

Since $$pq \mid e - 1$$, but $$pq \gt a \ge ef$$ so $$e \lt pq$$, then $$e = 1$$ is the only possibility. This then gives $$n = p_{3}$$ in \eqref{eq9A}, which means $$n$$ is a prime.

Only case #$$2$$ can apply, with it giving that $$n$$ must be a prime, so this concludes the proof in the opposite direction.

• this is good. Here's a general question : math.stackexchange.com/questions/3843281/…
– ASP
Sep 28 '20 at 8:00
• it appears your proof has some pitfalls. How did you deduce that $p\ | \ r-1$ and $q \ | \ s-1$ in case 1?
– ASP
Sep 28 '20 at 12:40
• @DavidJones The first case comes from the product definition of Euler's totient function. I've added some more details in the answer which might help. In particular, $p$ and $q$ must divide into one or more of the factors of the product. Since they can't divide into $n$ itself, they must divide into the $p_i - 1$ multiplication, where the $p_i$ are prime factors of $n$. There are $2$ cases to consider. Either they divide separate prime factors of $n$, which is my case $1$, or they both divide just one prime factor of $n$, which is my case $2$. Sep 28 '20 at 14:35
• Ohh It's much clear now.
– ASP
Sep 28 '20 at 14:47
• any counter examples yet to the general question?
– ASP
Sep 30 '20 at 7:08