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

Question

Let $n=am+1$ where $a $ and $m>1$ are positive integers and let $p$ be the least prime divisor of $m$. Prove that if $a<p$ and $ m \ | \ \phi(n)$ then $n$ is prime.

This question is a generalisation of the question at Let $n=apq+1$. Prove that if $pq \ | \ \phi(n)$ then $n$ is prime.. Here the special case when $m$ is a product of two distinct odd primes has been proven. The case when $m$ is a prime power has also been proven here https://arxiv.org/abs/2005.02327.

How do we prove that the proposition holds for an arbitrary positive integer integer $m>1 $? ( I have not found any counter - examples).

Note that if $n=am+1$ is prime, we have $\phi(n)= n-1=am$. We see that $m \ | \ \phi(n) $. Its the converse of this statement that we want to prove i.e. If $m \ | \ \phi(n) $ then $n$ is prime.

If this conjecture is true, then we have the following theorem which is a generalisation ( an extension) of Lucas's converse of Fermat's little theorem.

$\textbf {Theorem} \ \ 1.$$ \ \ \ $ Let $n=am+1$, where $a$ and $m>1$ are positive integers and let $p$ be the least prime divisor of $m$ with $a<p$. If for each prime $q_i$ dividing $m$, there exists an integer $b_i$ such that ${b_i}^{n-1}\equiv 1\ (\mathrm{mod}\ n)$ and ${b_i}^{(n-1)/q_i} \not \equiv 1(\mathrm{mod}\ n)$ then $n$ is prime.

Proof. $ \ \ \ $ We begin by noting that ${\mathrm{ord}}_nb_i\ |\ n-1$. Let $m={q_1}^{a_1}{q_2}^{a_2}\dots {q_k}^{a_k}$ be the prime power factorization of $m$. The combination of ${\mathrm{ord}}_nb_i\ |\ n-1$ and ${\mathrm{ord}}_nb_i\ \nmid (n-1)/q_i$ implies ${q_i}^{a_i}\ |\ {\mathrm{ord}}_nb_i$. $ \ \ $${\mathrm{ord}}_nb_i\ |\ \phi (n)$ therefore for each $i$, ${q_i}^{a_i}\ |\ \phi (n)$ hence $m\ |\ \phi (n)$. Assuming the above conjecture is true, we conclude that $n$ is prime.

Taking $a=1$, $m=n-1$ and $p=2$, we obtain Lucas's converse of Fermat's little theorem. Theorem 1 is thus a generalisation (an extension) of Lucas's converse of Fermat's little theorem.

On recommendation by the users, this question has been asked on the MathOverflow site, https://mathoverflow.net/questions/373497/prove-that-there-are-no-composite-integers-n-am1-such-that-m-phin

Answer 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$.

Answer 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.

---

Answer 3

As mentioned if $2 \mid m$ then $p=2$ and $a=1$.

So we consider the case $m$ odd and $p \ge 3$

$m= \prod_\limits{i=1}^k q_i^{a_i}$ with $q_i$ prime and $p=q_1<q_2< \dots <q_k$

$n=1+am=\prod_\limits{j=1}^r p_j^{k_j}$ with $p_j$ prime

we take $p_1$ so that $q_1 \mid (p_1-1)$

$\phi (n)=\prod_\limits{j=1}^r p_j^{k_j-1}(p_j-1)=bm$

$m=\frac{\prod_\limits{j=1}^r p_j^{k_j-1}(p_j-1)}{b}$

if $p_j \mid m$ then $n=1 \bmod p_j$ therefore it must be $p_j \not \mid m$

then $b=c\prod_\limits{j=1}^r p_j^{k_j-1}$ , $c \ge 1$

$n=1+am=1+a \frac{\prod_\limits{j=1}^r p_j^{k_j-1}(p_j-1)}{b}=\prod_\limits{j=1}^r p_j^{k_j}$

therefore

$ a=b \frac{\prod p_j^{k_j}-\displaystyle 1}{\prod p_j^{k_j-1}(p_j-1)}=c\prod p_j^{k_j-1} \frac{\prod p_j^{k_j}-\displaystyle 1}{\prod p_j^{k_j-1}(p_j-1)}$

but $ \frac{\prod p_j^{k_j}-\displaystyle 1}{\prod p_j^{k_j-1}(p_j-1)}>1$

then if exists $k_j \geq 2 $ for some $j$ with $q_i \mid (p_j-1)$

$a>p_j>(p_j-1)>q_i \geq q_1=p$

in this case $n$ composite number and $a>p$

therefore we have to analyze the cases in which $k_j =1$ for each $j$ with $q_i \mid (p_j-1)$

therefore

$$n=n_1 \prod_\limits{j=1}^t p_j \text{ where some } q_i \mid (p_j-1) \text{ and } n_1 \ge 1 \text{ with } q_i \not\mid \phi (n_1)$$

Case 1

$m \mid \phi(p_1)$ then $m \mid (p_1-1)$

$p_1=1+fm$ , $f \ge 2$

as demonstrated in the case $n=1+apq$

$n=1+am=ep_1$ with $e \ge 1$

$e(fm + 1) = am + 1 $

$(ef)m + e = am + 1 $

$e - 1 = (a - ef)m$

then $m \mid e - 1$, but $m \gt a \ge ef$ so $e \lt m$, then $e = 1$

therefore in this case it must be $n = p_1$ prime and $am = \phi(p_1)=fm$ .

Case 2

$m \not\mid (p_1-1)$

$n=p_1p_2$

$m=q_1d_1d_2$

$q_1d_1 \mid (p_1-1)$ , $d_1 \ge 1$

$d_2 \mid \phi(p_2)$ , $d_2 > q_1$

$d_2 \not\mid (p_1-1)$

$p_1=1+fq_1d_1$ , $f \ge 2$

$n=1+am=1+aq_1d_1d_2=p_2(1+fq_1d_1)$

$aq_1d_1d_2=p_2-1+p_2fq_1d_1$

$q_1d_1(ad_2-p_2f)=p_2-1$

then $q_1d_1 \mid (p_2-1)$

$p_2=1+gq_1d_1$ , $g \ge 2$

$n=1+aq_1d_1d_2=(1+gq_1d_1)(1+fq_1d_1)=1+fq_1d_1+gq_1d_1+fgq_1^2d_1^2$

$a= \frac{f+g+fgq_1d_1}{d_2}$

but $\phi (p_2)=gd_1q_1$ and $d_2 \mid gd_1q_1$

but $d_2 \not\mid (p_1-1)$ then $d_2 \not\mid q_1d_1$ and $d_2 \mid g$

then $d_2 < g$ and $a= \frac{f+g+fgq_1d_1}{d_2}>\frac{fgq_1d_1}{d_2}>\frac{fgq_1d_1}{g}>fq_1d_1>q_1$

in this case $n$ composite number and $a>p$

Case 3

$m \not\mid (p_1-1)$

$n=1+am=n_1 \prod_\limits{j=1}^t p_j \text{ where for each p_j there is some } q_i \text{ with } q_i\mid (p_j-1)$

$q_i \not\mid \phi (n_1)$

$p_j=1+b_jq_{i_1}\dots q_{i_{m_j}}$ with $b_j\ge 2$

$\phi(n_1)=c$

$\phi(n)=\phi(n_1) \prod(p_j-1)=\phi(n_1) \prod (b_jq_{i_1}\dots q_{i_{m_j}})=cbm$

but $\frac{n-1}{\phi(n)}=\frac{am}{cbm}>1$

then $cb= \phi(n_1) \prod b_j <a$ with $b \ge 2^{a_1+\dots +a_k}$

but $n=n_1 \prod_\limits{j=1}^t(1+b_jq_{i_1}\dots q_{i_{m_j}})=1+am$

and $\prod_\limits{j=1}^t(1+b_jq_{i_1}\dots q_{i_{m_j}})=(1+b_1q_{i_1}\dots q_{i_{m_1}}+\dots+\prod_\limits{j=2}^t(b_jq_{i_1}\dots q_{i_{m_j}})+\prod_\limits{j=1}^t(b_jq_{i_1}\dots q_{i_{m_j}}))$

then $m(a-n_1b)=-1+n_1(1+b_1q_{i_1}\dots q_{i_{m_1}}+\dots+\prod_\limits{j=2}^t(b_jq_{i_1}\dots q_{i_{m_j}}))$

from which $(a-n_1b)> 0$

then $a>n_1b$

$m<-1+n_1(1+b_1q_{i_1}\dots q_{i_{m_1}}+\dots+\prod_\limits{j=2}^t(b_jq_{i_1}\dots q_{i_{m_j}})$

but each addend $\prod(b_jq_{i_1}\dots q_{i_{m_j}})<\frac{bm}{q_{i_k} \prod b_k}<\frac{bm}{q_12^{s_k}}$ with $q_{i_k} \not=q_{i_1}\not=\dots\not= q_{i_{m_j}}$ and $ b_k \not= b_j$

then $m<\frac{n_1bm}{2q_1}(1+\sum\frac{1}{2^{s_k-1}})<\frac{n_1bm}{q_1}<\frac{am}{q_1}$

therefore $a>q_1$ and this contradicts the initial condition $a<q_1$

Answer 4

Let $n=am+1, m|φ(n), a,m>1, a<p, p$ is the least factor of $m$.

Let $n$ be a composite number with prime factorization

$$n=p_1^{e_1} p_2^{e_2 }\dots p_k^{e_k}$$

Without loss of generality, let $p_1 \lt p_2 \lt \dots < p_k$.

$$φ(n)=n(1-{1 \over p_1} )(1-{1 \over p_2} )…(1-{ 1 \over p_k} )$$

$$=p_1^{e_1} p_2^{e_2}\dots p_k^{e_k} {(p_1-1) \over p_1 } {(p_2-1) \over p_2 }…{(p_k-1) \over p_k }$$

$$=p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} (p_1-1)(p_2-1)…(p_k-1)$$

Since $m | φ(n)$, we can write for some integer $t$,

$$φ(n)=mt=p_1^{e_1-1} p_2^{e_2-1}\dots p_k^{e_k-1} (p_1-1)(p_2-1) \dots (p_k-1)$$

$$⇒m= {(p_1^{e_1-1} p_2^{e_2-1}…p_k^{e_k-1} (p_1-1)(p_2-1)…(p_k-1)) \over t}$$

The terms $(p_2-1),…,(p_k-1)$ in the numerator are all even since $p_2,…,p_k$ are primes. For the case of $p_1 = 2$, $p_1-1 = 1$.

We can write for integer $r_1, r_2, \dots, r_k$,

$$m={ p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k 2^k \over t}$$

$t$ must be of the form $2^k c$ where $c$ divides $p_1^{e_1-1} p_2^{e_2-1}\dots p_k^{e_k-1} r_1 r_2 \dots r_k$. Also note that if $p_1$ is 2, $p_1^{e_1-1}$ must be a factor of $c$. Otherwise the least factor of $m$ will be 2 and $p = 2$ which causes $a = 1$ since $a<p$ by definition. However, $a>1$ by definition.

$$m={p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2 \dots r_k \over c}$$

$$n=am+1=a{p_1^{e_1-1} p_2^{e_2-1}…p_k^{e_k-1} r_1 r_2…r_k \over c}+1$$

By definition, $p$ is the least divisor of $m$. The maximum value that $p$ can take is $p_k$ since $r_j<p_k,∀ 1≤j≤k$. By definition, $a<p$. Note that $c$ will have common factors with $a{ p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k 2^k}$, but cannot be exactly ${ p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k 2^k}$. If it were the case, $m = 1$ which conflicts with the assumption $m>1$. So, the factors of $c$ must have at most $e_j - 1$ exponent for the prime factor $p_j$ for all $1 \le j \le k$.

So, we have

$$n=p_1^{e_1 } p_2^{e_2 } \dots p_k^{e_k} = a{p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k \over c}+1$$

Let $p_u$ be the smallest prime that is the common factor of ${p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k \over c}$ and $n$. $p_u$ exists since we have proved that the maximum exponent of prime factor $p_j$ of $c$ is less than $e_j - 1$.

Taking modulo $p_u$, we get

$$0≡1 \mod p_u$$

This is impossible. Therefore $n$ must be prime.