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

• I don't think if we can prove this unless you assume that the lucas-Lehmer primality test is true , This would be as a result of it Oct 9 '20 at 15:44
• @zeraoulia, could you provide more details on your comment. How does the Lucas-Lehmer primality test imply that this conjecture is true?
– ASP
Oct 9 '20 at 18:00
• There are no counterexamples with $n \leq 10^{9}$. Oct 10 '20 at 16:18
• It's very unlikely that a counterexample exists.
– ASP
Oct 10 '20 at 17:16
• There are no counterexamples with $m \le 10^{10}$.
– ASP
Jan 23 at 20:24

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, it is enough to require that $$a 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.

• The generalised Pocklington's primality test involves gcd checks not equality checks.
– ASP
Oct 17 '20 at 17:14
• it would be nice if you added the proof for the claim that $m \ | \ ( r-1)$ for every prime divisor $r \ | \ n$.
– ASP
Oct 17 '20 at 17:28
• @DavidJones: The proof is given at Wikipedia. Yes, $b_i^{(n-1)/q_i}\not\equiv 1\pmod{n}$ in Theorem 1 needs to be replaced with $\gcd{(b_i^{(n - 1)/q_i} - 1, n)} = 1$ to ensure that $b_i^{(n-1)/q_i}\not\equiv 1\pmod{r}$ for any prime $r\mid 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$. I've added this to my answer. Oct 17 '20 at 18:55
• that's clear now. However am still very positive the claim in the question is most likely to be true.
– ASP
Oct 18 '20 at 12:22