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

2 Asked on November 3, 2021

1 Asked on November 3, 2021 by alex-gavrilov

0 Asked on November 3, 2021 by mohammad-golshani

2 Asked on November 3, 2021 by bryanjaeho

1 Asked on November 3, 2021 by diverietti

ag algebraic geometry complex geometry cv complex variables homogeneous spaces symmetric spaces

2 Asked on November 3, 2021 by bananeen

ag algebraic geometry analytic geometry complex geometry cv complex variables

1 Asked on November 3, 2021

0 Asked on November 3, 2021 by guy-crouchback

0 Asked on November 3, 2021 by mikhail-bondarko

ag algebraic geometry birational geometry chow groups motives reference request

7 Asked on November 3, 2021

at algebraic topology gn general topology graph theory gt geometric topology reference request

1 Asked on November 3, 2021

1 Asked on November 3, 2021 by jecl

algebraic number theory analytic number theory nt number theory

2 Asked on November 3, 2021

1 Asked on November 3, 2021

co combinatorics homological algebra rt representation theory

2 Asked on November 3, 2021

ag algebraic geometry at algebraic topology complex geometry reference request

2 Asked on November 3, 2021 by rohil-prasad

dg differential geometry differential topology gt geometric topology mg metric geometry

2 Asked on November 3, 2021

mp mathematical physics pr probability quantum field theory schwartz distributions

3 Asked on November 3, 2021

higher category theory morita equivalence morita theory noncommutative algebra noncommutative rings

1 Asked on November 3, 2021 by rajesh-d

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir