Prove that there are no composite integers $n=am+1$ such that $m \ | \ \phi(n)$

Solution 1:

Partial answer:

Lemma: Let $n=am+1$ where $a\ge1$ and $m\ge2$ are integers. Suppose that $m\mid\phi(n)$ and $a<p$ where $p=\min\{p^*\in\Bbb P:p^*\mid m\}$. If $n$ is not prime then either

• $n$ is of the form $\prod p_i$ where $p_i$ are primes, or

• $n$ is of the form $2^kr$ where $k,r$ are positive integers.

Proof: Suppose that $n$ is composite. First, note that $m$ must be odd as otherwise, $a=1$ which yields $n-1=m$. The condition $m\mid\phi(n)$ forces $n$ to be prime which is a contradiction.

Next, write $n=q^kr$ where $k,r$ are positive integers and $q$ is a prime such that $(q,r)=1$. As $\phi(n)=q^{k-1}(q-1)\phi(r)$ the condition $m\mid\phi(n)$ yields $$q^{k-1}(q-1)\phi(r)=mt\implies aq^{k-1}(q-1)\phi(r)=t(q^kr-1)$$ for some positive integer $t$. It follows that either $k=1$ or $t=q^{k-1}v$ for some integer $v\ne t$. In the latter case, we obtain $$\frac{q^kr-1}{q^{k-1}(q-1)\phi(r)}=\frac{aps}{mt}=\frac at\implies p>\frac{t(q^kr-1)}{q^{k-1}(q-1)\phi(r)}.$$ Combining this with the trivial result $p<q^{k-1}(q-1)\phi(r)/t$ yields $$t<\frac{q^{k-1}(q-1)\phi(r)}{\sqrt{q^kr-1}}\implies v<\frac{(q-1)\phi(r)}{\sqrt{q^kr-1}}.$$ Substituting back into $n=am+1$ gives $$q^kr-1=\frac av(q-1)\phi(r)\implies aq\phi(r)-vq^kr=a\phi(r)-v>\phi(r)\left(a-\frac{q-1}{\sqrt{q^kr-1}}\right)$$ which is positive since $k\ge2$. This yields $a>vq^{k-1}\ge vq$. Since $p$ is the least prime divisor of $m$, we have $p\le q-1$, unless $q=2$ or $q-1=v$.

Evidently, the first case contradicts $a<p$, so $k=1$. This means that $n$ must be of the form $\prod p_i$ where $p_i$ are primes. The condition $m\mid\phi(n)$ gives $\prod(p_i-1)=bm$ for some positive integer $b$, and substituting this into $n=am+1$ yields $$a=b\frac{\prod p_i-1}{\prod(p_i-1)}.$$ When $m$ is even, we have $a<p\implies a<2$ which implies that $m=\prod p_i-1$. Further, $$b<\frac{2\prod(p_i-1)}{\prod p_i-1}<2\implies m=\prod(p_i-1).$$ The only way that $\prod p_i-1=\prod(p_i-1)$ is when $\prod p_i$ is prime, which solves the problem. Finally, notice that $m$ is odd only when $b=2^{\nu_2(\prod(p_i-1))}d$ for some positive integer $d$, so the condition $a<p$ yields $$2^{\nu_2(\prod(p_i-1))}d\frac{\prod p_i-1}{\prod(p_i-1)}<\frac{p_j-1}{2^{\nu_2(p_j-1)}}$$ for some prime $p_j\mid\prod p_i$.

The second case $q=2$ implies that $n=2^kr=am+1$ where $m\mid\phi(r)$; that is, for some positive integer $g$ we have $g(2^kr-1)=a\phi(r)$.

The third case $q-1=v$ forces $m=\phi(r)$, so $m=1$. This is a contradiction as there is no prime $p$ that can divide $m$.

Solution 2:

Introduction

First, let the prime factorization of $m$ and $n=am+1$ be: $$m=\prod_{i=1}^k p_i^{a_i} \quad \quad \quad n=\prod_{i=1}^l q_i^{b_i}$$ where $p_1$ is the least prime factor of $m$. Since $\gcd(m,am+1)=1$, all $p_i$'s and $q_i$'s are pairwise distinct. Using this, we have: $$m \mid \phi(n) \implies \prod_{i=1}^k p_i^{a_i} \mid \prod_{i=1}^l(q_j-1)q_j^{b_j-1} \implies \prod_{i=1}^k p_i^{a_i} \mid \prod_{i=1}^l(q_i-1)$$ If there exists a prime $q_j>p_1$ such that $\gcd(m,q_j-1)$, then we would have: $$\phi(am+1) \geqslant \prod_{i=1}^k (q_i-1) \geqslant (q_j-1)m \geqslant p_1m$$ which is a contradiction. We also arrive at a similar contradiction if we assume that $b_j>1$ for any $q_j>p_1$. Thus, we can conclude that: $$am+1=M\prod_{i=1}^s r_i$$ where $r_i>p_1$ are primes and $M$ has all prime factors less than $p_1$. As we know that $m \mid \prod (r_i-1)$, it follows that we have $am+1 > Mm$. Thus, $p_1 > a \geqslant M$. If there exists a prime $p_j \mid m$, such that $p_j^{a_j+1} \mid \phi(n)$, then: $$\phi(am+1) \geqslant p_jm \geqslant p_1m > am+1$$ which is obviously a contradiction. Thus, we must have $p_j^{a_j} \mid \mid \phi(n)$ and as a consequence, $s \leqslant \sum a_i$. We can solve particular cases using these facts.

The case $m=p^t$

When $m$ is a perfect prime power, we can take $m$ to be odd. We must have $r_i \equiv 1 \pmod{p}$. We know that we have $p^t \mid \mid \prod (r_i-1)$. The equation becomes: $$ap^t+1 = M\prod_{i=1}^s r_i \implies M \equiv 1 \pmod{p}$$ Since $M<p$ this forces $M=1$. Next, we can write $r_i=p^{b_i}Q_i+1$ where $p \nmid Q_i$. We know that $\sum b_i = t$. $$ap^t+1 = \prod_{i=1}^s (p^{b_i}Q_i+1) \implies ap^t > p^t \cdot \prod Q_i \implies a > \prod_{i=1}^s Q_i$$ The strict inequality is ensured since $s>1$ i.e. $n$ is not prime. WLOG assume $b_1 \leqslant b_2 \leqslant \cdots \leqslant b_s$. Let $c=b_1=b_2=\cdots = b_x<b_{x+1}$. Taking the equation modulo $p^{c+1}$ gives: $$p^c\sum_{i=1}^x Q_i \equiv 0 \pmod{p^{c+1}} \implies p \mid \sum_{i=1}^x Q_i \implies \sum_{i=1}^x Q_i>a>\prod_{i=1}^x Q_i$$ However, since all $r_i$ are odd, all $Q_i$ must be even (since $p$ is odd). This would yield a contradiction since all $Q_i > 1$ and thus, the above inequality of sum being greater than product cannot hold. Thus, $n$ cannot be composite.

The case $m=pq$

Subcase $1$ : $s=1$ $$apq+1=Mr$$ Since $pq \mid (r-1)$, we have $M \equiv 1 \pmod{pq}$ and thus, $M=1$. However, this gives $n=Mr=r$ which is prime.

Subcase $2$ : $s=2$ $$apq+1=Mr_1r_2$$ Let $p \mid (r_1-1)$ and $q \mid (r_2-1)$. Moreover, let $p<q$. Writing $r_1=pQ_1+1$ and $r_2=qQ_2+1$ gives: $$apq+1=M(pqQ_1Q_2+pQ_1+qQ_2+1) \implies (a-MQ_1Q_2)pq+1=M(pQ_1+qQ_2+1)$$ Since the RHS is positive, this gives $a-MQ_1Q_2 \geqslant 1$. We have: $$pq < MQ_1Q_2 \bigg(\frac{p}{Q_2}+\frac{q}{Q_1}+\frac{1}{Q_1Q_2}\bigg) \implies q < \frac{p+1}{Q_2}+\frac{q}{Q_1} < \frac{q}{Q_1}+\frac{q}{Q_2} \leqslant q$$ This is a contradiction. Thus, $n$ cannot be composite.