5
$\begingroup$

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$?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ this is good. Here's a general question : math.stackexchange.com/questions/3843281/… $\endgroup$
    – ASP
    Sep 28 '20 at 8:00
  • $\begingroup$ it appears your proof has some pitfalls. How did you deduce that $p\ | \ r-1$ and $q \ | \ s-1$ in case 1? $\endgroup$
    – ASP
    Sep 28 '20 at 12:40
  • $\begingroup$ @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$. $\endgroup$ Sep 28 '20 at 14:35
  • $\begingroup$ Ohh It's much clear now. $\endgroup$
    – ASP
    Sep 28 '20 at 14:47
  • $\begingroup$ any counter examples yet to the general question? $\endgroup$
    – ASP
    Sep 30 '20 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.