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

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 Let $n=apq+1$. Prove that if $pq \ | \ \phi(n)$ 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.

On recommendation by the users, this question has been asked on the MathOverflow site, https://mathoverflow.net/questions/373497/prove-that-there-are-no-composite-integers-n-am1-such-that-m-phin

• If it took research paper to even solve a special case, then this question might be better suited for mathoverflow Commented Sep 30, 2020 at 10:52
• @supinf, let's not neglect the possibility that someone could come up with a beautiful short proof or find a counterexample.
– ASP
Commented Sep 30, 2020 at 11:44
• I saw, I think I am close to proving it, on the general case, and would like to make my own paper. Thanks. I will notify you
– user799688
Commented Sep 30, 2020 at 12:03
• @user140242 I understood it as "$a$ and $m$ are positive integers and $m>1$" and not "$a>1$ and $m>1$ are positive integers". Commented Oct 1, 2020 at 8:38
• One other thing is that if you do later post your question on MathOverflow, please make sure to add a link in your question text here to that other question, and in the MathOverflow question back to this one. This will help to avoid people duplicating efforts on one site which has already been done on the other site. Commented Oct 2, 2020 at 3:05

Lemma: Let $$n=am+1$$ where $$a\ge1$$ and $$m\ge2$$ are integers. Suppose that $$m\mid\phi(n)$$ and $$a where $$p=\min\{p^*\in\Bbb P:p^*\mid m\}$$. If $$n$$ is not prime then either

• $$n$$ is of the form $$\prod p_i$$ where $$p_i$$ are primes, or

• $$n$$ is of the form $$2^kr$$ where $$k,r$$ are positive integers.

Proof: Suppose that $$n$$ is composite. First, note that $$m$$ must be odd as otherwise, $$a=1$$ which yields $$n-1=m$$. The condition $$m\mid\phi(n)$$ forces $$n$$ to be prime which is a contradiction.

Next, write $$n=q^kr$$ where $$k,r$$ are positive integers and $$q$$ is a prime such that $$(q,r)=1$$. As $$\phi(n)=q^{k-1}(q-1)\phi(r)$$ the condition $$m\mid\phi(n)$$ yields $$q^{k-1}(q-1)\phi(r)=mt\implies aq^{k-1}(q-1)\phi(r)=t(q^kr-1)$$ for some positive integer $$t$$. It follows that either $$k=1$$ or $$t=q^{k-1}v$$ for some integer $$v\ne t$$. In the latter case, we obtain $$\frac{q^kr-1}{q^{k-1}(q-1)\phi(r)}=\frac{aps}{mt}=\frac at\implies p>\frac{t(q^kr-1)}{q^{k-1}(q-1)\phi(r)}.$$ Combining this with the trivial result $$p yields $$t<\frac{q^{k-1}(q-1)\phi(r)}{\sqrt{q^kr-1}}\implies v<\frac{(q-1)\phi(r)}{\sqrt{q^kr-1}}.$$ Substituting back into $$n=am+1$$ gives $$q^kr-1=\frac av(q-1)\phi(r)\implies aq\phi(r)-vq^kr=a\phi(r)-v>\phi(r)\left(a-\frac{q-1}{\sqrt{q^kr-1}}\right)$$ which is positive since $$k\ge2$$. This yields $$a>vq^{k-1}\ge vq$$. Since $$p$$ is the least prime divisor of $$m$$, we have $$p\le q-1$$, unless $$q=2$$ or $$q-1=v$$.

Evidently, the first case contradicts $$a, so $$k=1$$. This means that $$n$$ must be of the form $$\prod p_i$$ where $$p_i$$ are primes. The condition $$m\mid\phi(n)$$ gives $$\prod(p_i-1)=bm$$ for some positive integer $$b$$, and substituting this into $$n=am+1$$ yields $$a=b\frac{\prod p_i-1}{\prod(p_i-1)}.$$ When $$m$$ is even, we have $$a which implies that $$m=\prod p_i-1$$. Further, $$b<\frac{2\prod(p_i-1)}{\prod p_i-1}<2\implies m=\prod(p_i-1).$$ The only way that $$\prod p_i-1=\prod(p_i-1)$$ is when $$\prod p_i$$ is prime, which solves the problem. Finally, notice that $$m$$ is odd only when $$b=2^{\nu_2(\prod(p_i-1))}d$$ for some positive integer $$d$$, so the condition $$a yields $$2^{\nu_2(\prod(p_i-1))}d\frac{\prod p_i-1}{\prod(p_i-1)}<\frac{p_j-1}{2^{\nu_2(p_j-1)}}$$ for some prime $$p_j\mid\prod p_i$$.

The second case $$q=2$$ implies that $$n=2^kr=am+1$$ where $$m\mid\phi(r)$$; that is, for some positive integer $$g$$ we have $$g(2^kr-1)=a\phi(r)$$.

The third case $$q-1=v$$ forces $$m=\phi(r)$$, so $$m=1$$. This is a contradiction as there is no prime $$p$$ that can divide $$m$$.

• I've read through the rest of your answer and have $2$ more questions. First, with "... since $p$ is the least prime divisor of $m$, we also have $p\le q-1$ ...", there's the possibility that $p \mid \phi(r)$. What you've shown is that there's no prime factor $q \gt p$ which can have more than one factor in $n$, but I don't see how this excludes possibly smaller factors than $p$ occurring more than once. The second issue is in your final inequality, I don't understand what your $p_c$ is. Commented Oct 3, 2020 at 20:16
• I don't understand what your statement "The smallest divisor of $ab/c$ is at most $a$ (under trivial constraints)" has to do with my comment, e.g., since the smaller $p_i \mid n = am + 1$ have no direct connection with $a$ or $m$. Thanks for clarifying your $p_c$, now called $p_j$. This seems to be one of the primes where $p \mid p_j - 1$, so you may wish to make this clear. Also, thanks for providing feedback in your multiple replies. However, I've spent more time working with your answer than I want to, so please understand why if I don't respond to any additional replies from you. Commented Oct 4, 2020 at 3:43
• @JohnOmielan Remember that $p$ divides $m$ not $n$. But your comment is useful as you have pointed out the flaw: the case $q=2$ means that $m=\phi(r)/v$ so $p$ cannot be less than $q-1$. Notice that this case is similar to the $n=\prod p_i$ case as the integer $g$ as updated in my answer must absorb all the powers of $2$ just like with $b$. Commented Oct 4, 2020 at 10:01
• In your proof to show that $k=1$, you showed that $p \le q-1$ to arrive at a contradiction. However there's a fatal error in the proof. Since $p$ is a divisor of $m$ and $m \ | \ \phi(n)$ we have $p \ | \ \phi(n)=q^{k-1}(q-1) \phi(r)$. Because $p$ is prime, $p$ divides at least one of the factors : $q$, $q-1$ or $\phi(r)$. In your proof you have assumed that $p$ divides the factor $q-1$ to arrive at $p \le q-1$. You haven't considered the case when $p \ | \ \phi(r)$
– ASP
Commented Oct 4, 2020 at 13:10
• That is not a correct example. Remember that $p$ is the least prime divisor. So when we have $q-1=4$ and $\phi(r)=12$, the correct $p$ is $2$, and evidently $p\le q-1$ and $p\le\phi(r)$. I am not saying that $p\mid a$ and $p\mid b$. I am saying that $p\le a$ and $p\le b$. I hope this is clearer now. Commented Oct 4, 2020 at 14:11

## Introduction

First, let the prime factorization of $$m$$ and $$n=am+1$$ be: $$m=\prod_{i=1}^k p_i^{a_i} \quad \quad \quad n=\prod_{i=1}^l q_i^{b_i}$$ where $$p_1$$ is the least prime factor of $$m$$. Since $$\gcd(m,am+1)=1$$, all $$p_i$$'s and $$q_i$$'s are pairwise distinct. Using this, we have: $$m \mid \phi(n) \implies \prod_{i=1}^k p_i^{a_i} \mid \prod_{i=1}^l(q_j-1)q_j^{b_j-1} \implies \prod_{i=1}^k p_i^{a_i} \mid \prod_{i=1}^l(q_i-1)$$ If there exists a prime $$q_j>p_1$$ such that $$\gcd(m,q_j-1)$$, then we would have: $$\phi(am+1) \geqslant \prod_{i=1}^k (q_i-1) \geqslant (q_j-1)m \geqslant p_1m$$ which is a contradiction. We also arrive at a similar contradiction if we assume that $$b_j>1$$ for any $$q_j>p_1$$. Thus, we can conclude that: $$am+1=M\prod_{i=1}^s r_i$$ where $$r_i>p_1$$ are primes and $$M$$ has all prime factors less than $$p_1$$. As we know that $$m \mid \prod (r_i-1)$$, it follows that we have $$am+1 > Mm$$. Thus, $$p_1 > a \geqslant M$$. If there exists a prime $$p_j \mid m$$, such that $$p_j^{a_j+1} \mid \phi(n)$$, then: $$\phi(am+1) \geqslant p_jm \geqslant p_1m > am+1$$ which is obviously a contradiction. Thus, we must have $$p_j^{a_j} \mid \mid \phi(n)$$ and as a consequence, $$s \leqslant \sum a_i$$. We can solve particular cases using these facts.

## The case $$m=p^t$$

When $$m$$ is a perfect prime power, we can take $$m$$ to be odd. We must have $$r_i \equiv 1 \pmod{p}$$. We know that we have $$p^t \mid \mid \prod (r_i-1)$$. The equation becomes: $$ap^t+1 = M\prod_{i=1}^s r_i \implies M \equiv 1 \pmod{p}$$ Since $$M this forces $$M=1$$. Next, we can write $$r_i=p^{b_i}Q_i+1$$ where $$p \nmid Q_i$$. We know that $$\sum b_i = t$$. $$ap^t+1 = \prod_{i=1}^s (p^{b_i}Q_i+1) \implies ap^t > p^t \cdot \prod Q_i \implies a > \prod_{i=1}^s Q_i$$ The strict inequality is ensured since $$s>1$$ i.e. $$n$$ is not prime. WLOG assume $$b_1 \leqslant b_2 \leqslant \cdots \leqslant b_s$$. Let $$c=b_1=b_2=\cdots = b_x. Taking the equation modulo $$p^{c+1}$$ gives: $$p^c\sum_{i=1}^x Q_i \equiv 0 \pmod{p^{c+1}} \implies p \mid \sum_{i=1}^x Q_i \implies \sum_{i=1}^x Q_i>a>\prod_{i=1}^x Q_i$$ However, since all $$r_i$$ are odd, all $$Q_i$$ must be even (since $$p$$ is odd). This would yield a contradiction since all $$Q_i > 1$$ and thus, the above inequality of sum being greater than product cannot hold. Thus, $$n$$ cannot be composite.

## The case $$m=pq$$

Subcase $$1$$ : $$s=1$$ $$apq+1=Mr$$ Since $$pq \mid (r-1)$$, we have $$M \equiv 1 \pmod{pq}$$ and thus, $$M=1$$. However, this gives $$n=Mr=r$$ which is prime.

Subcase $$2$$ : $$s=2$$ $$apq+1=Mr_1r_2$$ Let $$p \mid (r_1-1)$$ and $$q \mid (r_2-1)$$. Moreover, let $$p. Writing $$r_1=pQ_1+1$$ and $$r_2=qQ_2+1$$ gives: $$apq+1=M(pqQ_1Q_2+pQ_1+qQ_2+1) \implies (a-MQ_1Q_2)pq+1=M(pQ_1+qQ_2+1)$$ Since the RHS is positive, this gives $$a-MQ_1Q_2 \geqslant 1$$. We have: $$pq < MQ_1Q_2 \bigg(\frac{p}{Q_2}+\frac{q}{Q_1}+\frac{1}{Q_1Q_2}\bigg) \implies q < \frac{p+1}{Q_2}+\frac{q}{Q_1} < \frac{q}{Q_1}+\frac{q}{Q_2} \leqslant q$$ This is a contradiction. Thus, $$n$$ cannot be composite.

As mentioned if $$2 \mid m$$ then $$p=2$$ and $$a=1$$.

So we consider the case $$m$$ odd and $$p \ge 3$$

$$m= \prod_\limits{i=1}^k q_i^{a_i}$$ with $$q_i$$ prime and $$p=q_1

$$n=1+am=\prod_\limits{j=1}^r p_j^{k_j}$$ with $$p_j$$ prime

we take $$p_1$$ so that $$q_1 \mid (p_1-1)$$

$$\phi (n)=\prod_\limits{j=1}^r p_j^{k_j-1}(p_j-1)=bm$$

$$m=\frac{\prod_\limits{j=1}^r p_j^{k_j-1}(p_j-1)}{b}$$

if $$p_j \mid m$$ then $$n=1 \bmod p_j$$ therefore it must be $$p_j \not \mid m$$

then $$b=c\prod_\limits{j=1}^r p_j^{k_j-1}$$ , $$c \ge 1$$

$$n=1+am=1+a \frac{\prod_\limits{j=1}^r p_j^{k_j-1}(p_j-1)}{b}=\prod_\limits{j=1}^r p_j^{k_j}$$

therefore

$$a=b \frac{\prod p_j^{k_j}-\displaystyle 1}{\prod p_j^{k_j-1}(p_j-1)}=c\prod p_j^{k_j-1} \frac{\prod p_j^{k_j}-\displaystyle 1}{\prod p_j^{k_j-1}(p_j-1)}$$

but $$\frac{\prod p_j^{k_j}-\displaystyle 1}{\prod p_j^{k_j-1}(p_j-1)}>1$$

then if exists $$k_j \geq 2$$ for some $$j$$ with $$q_i \mid (p_j-1)$$

$$a>p_j>(p_j-1)>q_i \geq q_1=p$$

in this case $$n$$ composite number and $$a>p$$

therefore we have to analyze the cases in which $$k_j =1$$ for each $$j$$ with $$q_i \mid (p_j-1)$$

therefore

$$n=n_1 \prod_\limits{j=1}^t p_j \text{ where some } q_i \mid (p_j-1) \text{ and } n_1 \ge 1 \text{ with } q_i \not\mid \phi (n_1)$$

Case 1

$$m \mid \phi(p_1)$$ then $$m \mid (p_1-1)$$

$$p_1=1+fm$$ , $$f \ge 2$$

as demonstrated in the case $$n=1+apq$$

$$n=1+am=ep_1$$ with $$e \ge 1$$

$$e(fm + 1) = am + 1$$

$$(ef)m + e = am + 1$$

$$e - 1 = (a - ef)m$$

then $$m \mid e - 1$$, but $$m \gt a \ge ef$$ so $$e \lt m$$, then $$e = 1$$

therefore in this case it must be $$n = p_1$$ prime and $$am = \phi(p_1)=fm$$ .

Case 2

$$m \not\mid (p_1-1)$$

$$n=p_1p_2$$

$$m=q_1d_1d_2$$

$$q_1d_1 \mid (p_1-1)$$ , $$d_1 \ge 1$$

$$d_2 \mid \phi(p_2)$$ , $$d_2 > q_1$$

$$d_2 \not\mid (p_1-1)$$

$$p_1=1+fq_1d_1$$ , $$f \ge 2$$

$$n=1+am=1+aq_1d_1d_2=p_2(1+fq_1d_1)$$

$$aq_1d_1d_2=p_2-1+p_2fq_1d_1$$

$$q_1d_1(ad_2-p_2f)=p_2-1$$

then $$q_1d_1 \mid (p_2-1)$$

$$p_2=1+gq_1d_1$$ , $$g \ge 2$$

$$n=1+aq_1d_1d_2=(1+gq_1d_1)(1+fq_1d_1)=1+fq_1d_1+gq_1d_1+fgq_1^2d_1^2$$

$$a= \frac{f+g+fgq_1d_1}{d_2}$$

but $$\phi (p_2)=gd_1q_1$$ and $$d_2 \mid gd_1q_1$$

but $$d_2 \not\mid (p_1-1)$$ then $$d_2 \not\mid q_1d_1$$ and $$d_2 \mid g$$

then $$d_2 < g$$ and $$a= \frac{f+g+fgq_1d_1}{d_2}>\frac{fgq_1d_1}{d_2}>\frac{fgq_1d_1}{g}>fq_1d_1>q_1$$

in this case $$n$$ composite number and $$a>p$$

Case 3

$$m \not\mid (p_1-1)$$

$$n=1+am=n_1 \prod_\limits{j=1}^t p_j \text{ where for each p_j there is some } q_i \text{ with } q_i\mid (p_j-1)$$

$$q_i \not\mid \phi (n_1)$$

$$p_j=1+b_jq_{i_1}\dots q_{i_{m_j}}$$ with $$b_j\ge 2$$

$$\phi(n_1)=c$$

$$\phi(n)=\phi(n_1) \prod(p_j-1)=\phi(n_1) \prod (b_jq_{i_1}\dots q_{i_{m_j}})=cbm$$

but $$\frac{n-1}{\phi(n)}=\frac{am}{cbm}>1$$

then $$cb= \phi(n_1) \prod b_j with $$b \ge 2^{a_1+\dots +a_k}$$

but $$n=n_1 \prod_\limits{j=1}^t(1+b_jq_{i_1}\dots q_{i_{m_j}})=1+am$$

and $$\prod_\limits{j=1}^t(1+b_jq_{i_1}\dots q_{i_{m_j}})=(1+b_1q_{i_1}\dots q_{i_{m_1}}+\dots+\prod_\limits{j=2}^t(b_jq_{i_1}\dots q_{i_{m_j}})+\prod_\limits{j=1}^t(b_jq_{i_1}\dots q_{i_{m_j}}))$$

then $$m(a-n_1b)=-1+n_1(1+b_1q_{i_1}\dots q_{i_{m_1}}+\dots+\prod_\limits{j=2}^t(b_jq_{i_1}\dots q_{i_{m_j}}))$$

from which $$(a-n_1b)> 0$$

then $$a>n_1b$$

$$m<-1+n_1(1+b_1q_{i_1}\dots q_{i_{m_1}}+\dots+\prod_\limits{j=2}^t(b_jq_{i_1}\dots q_{i_{m_j}})$$

but each addend $$\prod(b_jq_{i_1}\dots q_{i_{m_j}})<\frac{bm}{q_{i_k} \prod b_k}<\frac{bm}{q_12^{s_k}}$$ with $$q_{i_k} \not=q_{i_1}\not=\dots\not= q_{i_{m_j}}$$ and $$b_k \not= b_j$$

then $$m<\frac{n_1bm}{2q_1}(1+\sum\frac{1}{2^{s_k-1}})<\frac{n_1bm}{q_1}<\frac{am}{q_1}$$

therefore $$a>q_1$$ and this contradicts the initial condition $$a

Let $$n=am+1, m|φ(n), a,m>1, a is the least factor of $$m$$.

Let $$n$$ be a composite number with prime factorization

$$n=p_1^{e_1} p_2^{e_2 }\dots p_k^{e_k}$$

Without loss of generality, let $$p_1 \lt p_2 \lt \dots < p_k$$.

$$φ(n)=n(1-{1 \over p_1} )(1-{1 \over p_2} )…(1-{ 1 \over p_k} )$$

$$=p_1^{e_1} p_2^{e_2}\dots p_k^{e_k} {(p_1-1) \over p_1 } {(p_2-1) \over p_2 }…{(p_k-1) \over p_k }$$

$$=p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} (p_1-1)(p_2-1)…(p_k-1)$$

Since $$m | φ(n)$$, we can write for some integer $$t$$,

$$φ(n)=mt=p_1^{e_1-1} p_2^{e_2-1}\dots p_k^{e_k-1} (p_1-1)(p_2-1) \dots (p_k-1)$$

$$⇒m= {(p_1^{e_1-1} p_2^{e_2-1}…p_k^{e_k-1} (p_1-1)(p_2-1)…(p_k-1)) \over t}$$

The terms $$(p_2-1),…,(p_k-1)$$ in the numerator are all even since $$p_2,…,p_k$$ are primes. For the case of $$p_1 = 2$$, $$p_1-1 = 1$$.

We can write for integer $$r_1, r_2, \dots, r_k$$,

$$m={ p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k 2^k \over t}$$

$$t$$ must be of the form $$2^k c$$ where $$c$$ divides $$p_1^{e_1-1} p_2^{e_2-1}\dots p_k^{e_k-1} r_1 r_2 \dots r_k$$. Also note that if $$p_1$$ is 2, $$p_1^{e_1-1}$$ must be a factor of $$c$$. Otherwise the least factor of $$m$$ will be 2 and $$p = 2$$ which causes $$a = 1$$ since $$a by definition. However, $$a>1$$ by definition.

$$m={p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2 \dots r_k \over c}$$

$$n=am+1=a{p_1^{e_1-1} p_2^{e_2-1}…p_k^{e_k-1} r_1 r_2…r_k \over c}+1$$

By definition, $$p$$ is the least divisor of $$m$$. The maximum value that $$p$$ can take is $$p_k$$ since $$r_j. By definition, $$a. Note that $$c$$ will have common factors with $$a{ p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k 2^k}$$, but cannot be exactly $${ p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k 2^k}$$. If it were the case, $$m = 1$$ which conflicts with the assumption $$m>1$$. So, the factors of $$c$$ must have at most $$e_j - 1$$ exponent for the prime factor $$p_j$$ for all $$1 \le j \le k$$.

So, we have

$$n=p_1^{e_1 } p_2^{e_2 } \dots p_k^{e_k} = a{p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k \over c}+1$$

Let $$p_u$$ be the smallest prime that is the common factor of $${p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r_1 r_2…r_k \over c}$$ and $$n$$. $$p_u$$ exists since we have proved that the maximum exponent of prime factor $$p_j$$ of $$c$$ is less than $$e_j - 1$$.

Taking modulo $$p_u$$, we get

$$0≡1 \mod p_u$$

This is impossible. Therefore $$n$$ must be prime.

• Why does such a $p_u$ exist? Maybe it could happen that they have no common factor? Commented Oct 6, 2020 at 18:15
• Also it is not clear to me why $p_1-1$ should be even. Commented Oct 6, 2020 at 18:17
• @supinf: Please see edits made above. $p_u$ exists because $c$ cannot be exactly the numerator as it would cause $m = 1$. $p_1 -1$ does not have to be even, but that happens only when $p_1$ is 2 and $p_1 - 1$ is $1$ and $r_1 = 1$. If $p_1$ is 2, $p_1^{e_1-1}\times 2^k$ must be a factor of $c$ and the rest of the proof stays intact.
– vvg
Commented Oct 7, 2020 at 2:57
• Your assumption that $p \le p_k$ is wrong. take $n=175=6 \bullet 29 +1$ with $a=6$, $m=29$ and $p=29$.The largest prime divisor of $n=p_k=7$. Clearly $p>p_k$.
– ASP
Commented Oct 7, 2020 at 4:37
• @davidjones: The definition of $p$ is it is the least prime divisor of $m$ (not $n$). $p_k$ is the largest prime divisor of $m$. So,$p \le p_k$.
– vvg
Commented Oct 7, 2020 at 4:45