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

elementary-number-theorynumber theoryprimality-testprime numbers

Let $p$ and $q$ be distinct odd primes and $a$ be a positive integer with $a<p<q$. 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$?

Best Answer

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{equation}\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}\end{equation}\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{equation}\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}\end{equation}\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{equation}\begin{aligned} e(fpq + 1) & = apq + 1 \\ (ef)pq + e & = apq + 1 \\ e - 1 & = (a - ef)pq \end{aligned}\end{equation}\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.

Related Question