Prove that there are no composite integers $n=am+1$ such that $m \ | \ \phi(n)$ Let $n=am+1$ where $a $ and $m&gt;1$ are positive integers and let $p$ be the least prime divisor of $m$. Prove that if $a&lt;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&gt;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&gt;1$ are positive integers and let $p$ be the least prime divisor of $m$ with $a&lt;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
Partial answer:
Lemma: Let $n=am+1$ where $a\ge1$ and $m\ge2$ are integers. Suppose that  $m\mid\phi(n)$ and $a&lt;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&gt;\frac{t(q^kr-1)}{q^{k-1}(q-1)\phi(r)}.$$ Combining this with the trivial result $p&lt;q^{k-1}(q-1)\phi(r)/t$ yields $$t&lt;\frac{q^{k-1}(q-1)\phi(r)}{\sqrt{q^kr-1}}\implies v&lt;\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&gt;\phi(r)\left(a-\frac{q-1}{\sqrt{q^kr-1}}\right)$$ which is positive since $k\ge2$. This yields $a&gt;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&lt;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&lt;p\implies a&lt;2$ which implies that $m=\prod p_i-1$. Further, $$b&lt;\frac{2\prod(p_i-1)}{\prod p_i-1}&lt;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&lt;p$ yields $$2^{\nu_2(\prod(p_i-1))}d\frac{\prod p_i-1}{\prod(p_i-1)}&lt;\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$.
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&lt;q_2&lt; \dots &lt;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)}&gt;1$
then if exists $k_j \geq 2 $ for some $j$ with $q_i \mid (p_j-1)$
$a&gt;p_j&gt;(p_j-1)&gt;q_i \geq q_1=p$
in this case $n$ composite number  and $a&gt;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 &gt; 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 &lt;  g$  and $a= \frac{f+g+fgq_1d_1}{d_2}&gt;\frac{fgq_1d_1}{d_2}&gt;\frac{fgq_1d_1}{g}&gt;fq_1d_1&gt;q_1$
in this case $n$ composite number  and $a&gt;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}&gt;1$
then $cb= \phi(n_1) \prod b_j &lt;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)&gt; 0$
then $a&gt;n_1b$
$m&lt;-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}})&lt;\frac{bm}{q_{i_k} \prod b_k}&lt;\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&lt;\frac{n_1bm}{2q_1}(1+\sum\frac{1}{2^{s_k-1}})&lt;\frac{n_1bm}{q_1}&lt;\frac{am}{q_1}$
therefore $a&gt;q_1$ and this contradicts the initial condition  $a&lt;q_1$