8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – zeraoulia rafik Oct 9 at 15:44
  • $\begingroup$ @zeraoulia, could you provide more details on your comment. How does the Lucas-Lehmer primality test imply that this conjecture is true? $\endgroup$ – David Jones Oct 9 at 18:00
  • 2
    $\begingroup$ There are no counterexamples with $n \leq 10^{9}$. $\endgroup$ – Jeremy Rouse Oct 10 at 16:18
  • 1
    $\begingroup$ It's very unlikely that a counterexample exists. $\endgroup$ – David Jones Oct 10 at 17:16
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The generalised Pocklington's primality test involves gcd checks not equality checks. $\endgroup$ – David Jones Oct 17 at 17:14
  • $\begingroup$ it would be nice if you added the proof for the claim that $m \ | \ ( r-1) $ for every prime divisor $r \ | \ n$. $\endgroup$ – David Jones Oct 17 at 17:28
  • $\begingroup$ @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. $\endgroup$ – Max Alekseyev Oct 17 at 18:55
  • $\begingroup$ that's clear now. However am still very positive the claim in the question is most likely to be true. $\endgroup$ – David Jones Oct 18 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.