Prove that there are no composite integers $n=am+1$ such that $m \ | \ \phi(n)$ 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
 A: 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$.
A: 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.

A: 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.
