If $q$ is prime, then $w=(1+q+q^2)/3$ is a composite integer iff $w$ has a prime divisor less than $\sqrt{w}$ and congruent to $1$ modulo $6$

Question

I have a question regarding prime numbers. Specifically, I wonder if the following is true:

If $q$ is a prime and $w=(1+q+q^2)/3$ is an integer, then $w$ is composite iff $w$ has a prime divisor less than $\sqrt{w}$ and congruent to $1$ modulo $6$.

Edit: The problem appears in this paper.

Answer 1

As @HagenvonEitzen said in the comments $w$ is an integer only if $q\equiv 1\pmod{6}$. Let $q=6k+1$ then $$ w=\frac{q^3-1}{3(q-1)}=\frac{216k^3+108k^2+18k}{18k}=12k^2+6k+1=3k^2+(3k+1)^2 $$ So $w$ is the norm of an Eisenstein integer $W=(3k+1)+k\sqrt{-3}=a+b\omega\in \mathbb{Z}[\sqrt{-3}]$ with $a=2k+1,b=2k$.

Since $\mathbb{Z}[\sqrt{-3}]$ is Euclidean we can factor $W$ into Eisenstein primes. Since $(2k+1,2k)=1$ no rational prime can divide $W$. The other Eisenstein primes have $|z|^2=p$ where $p=3$ or $p\equiv 1\pmod{6}$ is a rational prime. $3\nmid w$ so $w$ is the product of primes congruent to 1 modulo 6.

Either $w$ is prime, $w=p^2$ for some prime $p$, or $w=pv$ is composite with some prime factor $1<p<\sqrt{w}$. In fact if $q=313$ then $w=181^2$, so each case is possible and the claim as stated is not quite correct.

Answer 2

As noted by Hagen von Eitzen $q \equiv 1$ ($\bmod$ $6$). If $q=6n+1$ then

$$ \frac{1+q+q^2}{3}=12n^2+6n+1=\frac{1-(6n+2)+(6n+2)^2}{3}. $$

A prime $\neq 3$ dividing $1-m+m^2$ for some integer $m$ is equal to $1$ $\bmod$ $6$. This is because $1-m+m^2\equiv 0$ expresses that $m$ is a primitive sixth root of unity mod that prime. Since the number above is not divisible by $3$ all its prime divisors must be equal to $1$ $\bmod$ $6$.

Answer 3

In order for $w$ to be an integer, we need that $q$ is a solution of $X^3\equiv 1\pmod 3$. This implies $q\equiv 1\pmod 3$. Also, $q=2$ leads to $w=\frac73$, hence $q$ is odd, i.e. $q\equiv 1\pmod 6$. Let $p$ be a prime factor of $w$. Then $q$ is again a solution of $X^2+X+1\equiv 0\pmod p$, i.e. there are primitive thierd roots modulo $p$, i.e. $p\equiv 1\pmod 3$. Also, $p\ne 2$ as $1+q+q^2$ is odd. Therefore any prime factor of $w$ is $\equiv 1\pmod 6$. Unless $w$ is itself a prime, at least one prime factor is $\le\sqrt w$, with equality if and only if $w$ is the square of a prime. So your conjecture is correct except for possible cases where $w$ is the square of a prime.

A numerical check for $q\le 10^8$ shows only one case where $w=p^2$ occurs, namely $q=313$, $p=181$. In fact the search for solutions of $\frac{1+q+q^2}3=p^2$ leads to the equation $q^2+q+1=3p^2$ or $(p\sqrt 3+q)(p\sqrt 3-q)=q+1$, hence $p\sqrt 3>q$ and $$ p\sqrt 3-q=\frac{q+1}{p\sqrt 3+q}<\frac{q+1}{2q}=\frac12+\frac1{2q}.$$ From this, $p\sqrt 3<q+1$ and hence $$ p\sqrt 3-q=\frac{q+1}{p\sqrt 3+q}>\frac{q+1}{2q+1}=\frac12+\frac1{2(2q+1)}.$$ This makes $\frac{2q+1}{2p}$ quite a good approximation of $\sqrt 3$: $$ \left|\frac{2q+1}{2p}-\sqrt 3\right|<\frac{1}{pq}\approx \frac1{p^2\sqrt 3}.$$ We conclude that $\frac{2q+1}{2p}$ can be found from the continued fraction for $\sqrt 3$, and a short analysis gives us the recursion $p_{n+1}=14p_n-p_{n-1}$ with $p_0=1, p_1=13$ as candidates for $p$ and $q_{n+1}=14q_n-q_{n-1}+6$ with $q_0=1, q_1=22$ as candidates for $q$. Only when both sequences hit a prime, we get a solution.

This quickly produces (once again) the above solution $q=313,p=181$. The next solution found, is $$ q=2288805793,\quad p=2288805793.$$ Thanks to the quick growth of the recursive sequences, I could verify that no other solutions exist with $q<10^{4000}$. With a very crude heuristic (using that $p_n$ and $q_n$ grow exponentially and that the probability of $x$ being prime is $\frac1{\ln x}$), the probability that both $p_n$ and $q_n$ in the above sequence are prime, is $\sim\frac1{n^2}$, so the expected value for the number of solutions is finite and the expected number of solutions with $q>10^{4000}$ is practically zero. So it is plausible that the two solutions found so far might be the only cases where $w$ is the square of a prime ...