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 https://math.stackexchange.com/questions/3843195/let-n-apq1-prove-that-if-pq-phin-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.

This question was originally asked in the Mathematics site, https://math.stackexchange.com/questions/3843281/prove-that-there-are-no-composite-integers-n-am1-such-that-m-phin. On recommendation by the users, it has been asked here.

Answer 1

I believe the claim in question may not hold, although it seems to be tricky to construct a counterexample.

Nevertheless, under the replacement of $b_i^{(n-1)/q_i}\not\equiv 1\pmod{n}$ with $\gcd{(b_i^{(n - 1)/q_i} - 1, n)} = 1$, Theorem 1 is correct and represents a partial case of the generalized Pocklington primality test. In fact, here rather than requiring $a<p$, it is enough to require that $a<m$ or $a<\sqrt{n}$.

From practical perspective, if it happens that $b_i^{(n-1)/q_i}\not\equiv 1\pmod{n}$ but $\gcd{(b_i^{(n - 1)/q_i} - 1, n)} > 1$ then this gcd gives a non-trivial divisor of $n$.

Correspondingly, the given proof of Theorem 1 is easy to make work: instead of concluding that $m\mid\phi(n)$ and relying on the unproved claim, one can show that $m\mid (r-1)$ for every prime divisor $r\mid n$, implying that $n$ does not have prime divisors below $\sqrt{n}$ and thus it must be prime.