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

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

## Related Questions

### Examples of $aleph_0$-categorical nonhomogeneous structures

2  Asked on November 3, 2021

### Extending a holomorphic vector bundle: a reference request

1  Asked on November 3, 2021 by alex-gavrilov

### Closed walks on an $n$-cube and alternating permutations

2  Asked on November 3, 2021 by bryanjaeho

### Bounded non-symmetric domains covering a compact manifold

1  Asked on November 3, 2021 by diverietti

### Residues in several complex variables

2  Asked on November 3, 2021 by bananeen

### What kinds of papers does the Indiana University Mathematics Journal publish?

1  Asked on November 3, 2021

### Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?

0  Asked on November 3, 2021 by guy-crouchback

### Which field extensions do not affect Chow groups?

0  Asked on November 3, 2021 by mikhail-bondarko

### Reference for topological graph theory (research / problem-oriented)

7  Asked on November 3, 2021

### Is a direct sum of flabby sheaves flabby?

1  Asked on November 3, 2021

### Algebraicity of a ratio of values of the Gamma function

1  Asked on November 3, 2021 by jecl

### Classification of subgroups of finitely generated abelian groups

2  Asked on November 3, 2021

### An enumeration problem for Dyck paths from homological algebra

1  Asked on November 3, 2021

### Circular track riddle

1  Asked on November 3, 2021

### Fundamental group of a compact branched cover

2  Asked on November 3, 2021

### How do you know that you have succeeded-Constructive Quantum Field Theory and Lagrangian

2  Asked on November 3, 2021

### Does Morita theory hint higher modules for noncommutative ring?

3  Asked on November 3, 2021

### Bounding the smallest eigenvalue of a matrix generated by a positive definite function

1  Asked on November 3, 2021 by rajesh-d