# Are there finitely many primes $x$ such that for a fixed odd prime $p$, $n=x^{p-1}+x^{p-2}+\dotsb + x+1$ is composite and $x \mid \phi(n)$?

Let $$$$n =x^{p-1}+x^{p-2}+\dotsb + x+1$$$$ where $$x$$ and $$p$$ are odd primes.

If $$p$$ is set to $$5$$, it appears $$x=5$$ is the only prime $$x$$ such that $$n$$ is composite and $$x \mid \phi(n)$$ (verified up to $$x \le 2\cdot 10^6$$). Setting $$p$$ to $$7$$, we get only two values of $$x$$; $$x=7$$ and $$x = 281$$.

If $$x$$ is allowed to take composite values, it appears there are infinitely many $$x$$ such that $$x \mid \phi(n)$$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let $$$$n =x^{p-1}+x^{p-2}+\dotsb + x+1$$$$ where $$x$$ and $$p$$ are odd primes. For a fixed odd prime $$p$$, there are finitely many primes $$x$$ such that $$x \mid \phi(n)$$ with $$n$$ composite.

If Conjecture 1 is true, then, for a fixed prime $$p$$, there exists an upper bound $$x_\text{max}$$ such that $$x \nmid \phi(n)$$ for all $$x>x_\text{max}$$ with $$n$$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $$x^{p-1}+x^{p-2}+\dotsb + x+1$$ with $$x > x_\text{max}$$.

Theorem 1

Assuming Conjecture 1. Let $$n =x^{p-1}+x^{p-2}+\dotsb + x+1$$ where $$x$$ and $$p$$ are odd primes with $$x>x_\text{max}$$. If there exists a positive integer $$b$$ such that $$b^{n-1} \equiv 1 \pmod n$$ and $$b^{(n-1)/x} \not\equiv 1 \pmod n$$ then $$n$$ is prime.

Proof. Assuming Conjecture 1, we have $$x \mid \phi(n)$$ if and only if $$n$$ is prime. Assume $$n$$ is composite. Using the properties of order of an integer, one can deduce that $$ord_nb \mid (n-1) /x$$. It follows that if $$n$$ is composite then $$b^{(n-1)/x} \equiv 1 \pmod n$$, contradicting our hypothesis. Therefore $$n$$ must be prime.

Note: As $$x$$ is prime then $$x \mid \phi(n)$$ implies $$n = (ux+1)(vx+1)$$ for some non negative integers $$u$$, $$v$$ with $$ux+1$$ prime. It can also be shown that $$n = (sp+1)(tp+1)$$ for some non negative integers $$s$$, $$t$$ with $$sp+1$$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $$ux+1 \mid n$$ then $$ux+1 \mid \frac{ u^{p}+1} {u+1}$$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $$x_\text{max}$$.

• It should be noted that your $n$ as constructed is a base-$x$ repunit. Repunits have a deep history of study that perhaps can be tapped into to answer the Conjecture. Oct 5, 2021 at 17:02
• Your title seems to ask about the number of $n$'s, whereas your body seems to ask about the number of $x$'s. Is it clear that they are both finite, or both infinite? Also, your title requires that $n$ is composite (with no assumption on $x$), whereas your body seems to require instead that $x$ is prime (with no assumption on $n$). \\ Finally, doesn't the usefulness of Theorem 1 require not just knowing that Conjecture 1 is true, but having an effective estimate for $x_\text{max}$? Oct 5, 2021 at 17:12
• One more thing: TeX note: please use $x \mid \phi(n)$ x \mid \phi(n) instead of $x\ |\ \phi(n)$ x\ |\ \phi(n); and $b^{n - 1} \equiv 1 \pmod n$ b^{n - 1} \equiv 1 \pmod n instead of $b^{n - 1} \equiv 1$ (mod $n$) $b^{n - 1} \equiv 1$ (mod $n$). I have edited accordingly. Oct 5, 2021 at 17:19
• Perhaps you can check approaches to Agoh-Giuga conjecture, which if I'm not mistaken deals with the particular case $x=p$. Oct 5, 2021 at 17:42
• @LSpice, True Theorem 1 requires an effective estimate for $x_{max}$.
– ASP
Oct 5, 2021 at 18:29

Here's a proof of Conjecture 1 for the case $$p=5$$. The proof depends on the truth of the following overwhelmingly true unproven result :

Let $$$$P(x) = x^4 +x^3 +x^2 +x+1.$$$$ Then all positive integers $$x$$ such that $$P(x)$$ has a proper divisor congruent to 1 modulo $$x$$ are given as follows :

Let $$r(m)=m^2 +m-1$$ and $$q(m) = (r(m) +2)^2 - 2$$, where $$m$$ is a positive integer. For a particular positive integer $$m$$, define sequences $$A_n, B_n$$ as follows:

$$A_1 = m^3+2m^2 +2m$$ , $$A_2 = q(m)A_1+r(m)$$, $$A_n = q(m)A_{n-1}-A_{n-2}+r(m)$$

$$B_1 = m^5+2m^4 +3m^3 + 3m^2 +m$$ , $$B_2 = q(m)B_1+r(m)-m$$, $$B_n = q(m)B_{n-1}-B_{n-2}+r(m)$$

Then all positive integers $$x$$ such that $$P(x)$$ has a proper divisor congruent to 1 modulo $$x$$ are given by $$x=A_n$$ and $$x=B_n$$, $$n\ge 1$$, $$m \ge 1$$.

It can be shown by induction that $$A_n$$ and $$B_n$$ are always composite except when $$m=1$$ and $$n=1$$ in which case $$x=A_1=5$$ is prime.

If the unproven result here is true (very likely the case), then Conjecture 1 is settled for the case $$p=5$$. (Having no proper divisor congruent to 1 modulo $$x$$ for all primes $$x>5$$ implies $$x \nmid \phi(P(x))$$ for all composites $$P(x)$$, $$x >5$$ prime)

There's no reason to believe that the case $$p=5$$ is special. Conjecture 1 is most likely true for all odd primes.

ADDED (Compositeness of $$A_n$$ and $$B_n$$)

For $$n \equiv 0, 1 \ (\mathrm{mod} \ 3)$$, it can be shown by induction that $$m$$ divides $$A_n$$ and $$B_n$$. And when $$n \equiv 2 \ (\mathrm{mod \ 3})$$, one can prove that $$m+1$$ divides $$A_n$$ and $$B_n$$. Therefore it's clear that $$A_n$$ and $$B_n$$ are composite if $$m>1$$.

The remaining case $$m=1$$ is interesting. When $$m=1$$, $$A_n$$ and $$B_n$$ are a product of two sequences i.e $$A_n = f_n\cdot g_n$$ where $$f_1=1 , f_2 = 3, f_n = 3f_{n-1}-f_{n-2}$$ and $$g_1=5 , g_2 = 12, g_n = 3g_{n-1}-g_{n-2}$$.

Similarly $$B_n = f_n\cdot g_n$$ but with initial values changed; $$f_1 = 2, f_2= 5$$ and $$g_1 = 5, g_2 = 14$$

So $$x = A_1 = 5$$ is the only prime $$x$$ such that $$P(x) =x^4 +x^3 +x^2 +x+1$$ contains a proper divisor congruent to $$1$$ modulo $$x$$

• Original post on the unproven result : mathoverflow.net/questions/403542/…
– ASP
Oct 7, 2021 at 12:16
• The proof of the case $p=5$ required finding a complete set of positive integers $x$ such that $P(x)$ contains at least one proper divisor congruent 1 modulo $x$ and then showing that $x$ is composite for all $x >5$. For $p>5$, we do not have such a set of positive integers $x$ at our disposal and finding it will most likely be very difficult. Proving or disproving Conjecture 1 will therefore require a clever technique that does not require foreknowledge of the set of positive integers $x$ with this property.
– ASP
Oct 8, 2021 at 9:12
• I have finally proved the case $p=5$ without relying on the unproven result. I have even got interesting results for the more general case $P(x) =x^4+c_1x^3 +c_2x^2 +c_3x+1$, thanks to a paper suggested by one of the users here. Are there any other papers that investigate divisors of $P(x) = x^n+c_1x^{n-1}+\cdots + c_{n-1}x+1$, $n \ge 5$, that are congruent to $1$ modulo $x$?
– ASP
Oct 17, 2021 at 15:24