Prove that there are no composite integers $n=am+1$ such that $m | phi(n)$

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

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,
On recommendation by the users, it has been asked here.

One Answer

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

Add your own answers!

Related Questions

Applications of Set theory vs. model theory in mathematics

0  Asked on November 3, 2021 by mohammad-golshani


Circular track riddle

1  Asked on November 3, 2021


Ask a Question

Get help from others!

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