5
$\begingroup$

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} 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 \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} 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}$.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Aeryk
    Oct 5 at 17:02
  • $\begingroup$ 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}$? $\endgroup$
    – LSpice
    Oct 5 at 17:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – LSpice
    Oct 5 at 17:19
  • 1
    $\begingroup$ Perhaps you can check approaches to Agoh-Giuga conjecture, which if I'm not mistaken deals with the particular case $x=p$. $\endgroup$ Oct 5 at 17:42
  • 1
    $\begingroup$ @LSpice, True Theorem 1 requires an effective estimate for $x_{max}$. $\endgroup$
    – ASP
    Oct 5 at 18:29
5
$\begingroup$

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 \begin{equation} P(x) = x^4 +x^3 +x^2 +x+1. \end{equation} 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$

$\endgroup$
3
  • 3
    $\begingroup$ Original post on the unproven result : mathoverflow.net/questions/403542/… $\endgroup$
    – ASP
    Oct 7 at 12:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – ASP
    Oct 8 at 9:12
  • 1
    $\begingroup$ 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$? $\endgroup$
    – ASP
    Oct 17 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.