Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
First note that $w$ is an integer iff $q\equiv 1\pmod 3$ and in that case it follows that $q\equiv 1\pmod 6$. Also, $w$ can have at most one prime divisor $>\sqrt w$. So what you conjecture is that for prime $q\equiv 1\pmod 3$, $(1+q+q^2)/3$ is not the product of primes $\equiv -1\pmod 6$ and is not the square of a prime. – Hagen von Eitzen Jul 3 '13 at 6:32
up vote 6 down vote accepted

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.

share|cite|improve this answer

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$.

share|cite|improve this answer

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 ...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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