MathOverflow Asked by David Jones on January 13, 2021
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.
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}notequiv 1pmod{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}notequiv 1pmod{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 $mmidphi(n)$ and relying on the unproved claim, one can show that $mmid (r-1)$ for every prime divisor $rmid n$, implying that $n$ does not have prime divisors below $sqrt{n}$ and thus it must be prime.
Answered by Max Alekseyev on January 13, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP