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

Looking at prime numbers $p_i $ of the form $n^2+n+1$ and the derived expression

$$1 - \prod_{i=1}^{j}\frac{(p_i-1)}{p_i}$$

it seems (I do not claim it and do not see why it should be true) that the numerators of these numbers (in lowest terms) beyond 1 may contain only prime factors that are themselves factors of numbers of the form $n^2+n+1.$ It is true for

$$1, 3, 43, 1381, 8689, 642937, 7812553,$$

and I cannot verify it for the next element, 1,655,913,643. (Note: the sequence $p_i$ may be finite.) Am only asking in case there is an elementary reason for this that I do not see. Thanks.


share|cite|improve this question
1655913643 has the divisors 67, 773 and 31973 – Dominic Michaelis Feb 15 '13 at 15:09
Suppose $n^2 + n + 1 = 67$. Then, $n(n + 1) = 66 = 2 \times 3 \times 11$ (I replied to the previous comment; I will think of something else). – J.H. Feb 15 '13 at 15:14
@daniel, I thought you were asking whether these factors are of this form. Notice that $67 \mid 29^2 + 29 + 1$. However, if you consider $(n + 1/2)^2 \equiv -3/4\ (773)$, then $-3 \times 580$ should be a quadratic residue modulo $773$. However, I computed the Jacobi symbol $(-3 \times 580 \mid 773) = -1$. In other words, there is no $n$ such that $773 \mid n^2 + n + 1$. – J.H. Feb 15 '13 at 15:36
up vote 8 down vote accepted

A prime $p$ is a factor of a number of the form $n^2+n+1$ if and only if $p \neq 2 \pmod 3$ :

$3$ is a factor of $1^2+1+1 = 3$
If $p \neq 3$, then $(n^2+n+1)(n-1)=n^3-1$, thus $p$ is a factor of some $n^2+n+1$ if and only if it is a factor of $n^3-1$ where $n \neq 1 \pmod p$, which is equivalent to the existence of a nontrivial cube root of $1$ in $\Bbb Z/p \Bbb Z$. Since $(\Bbb Z/p \Bbb Z)^*$ is a cyclic group of order $p-1$, there is one if and only if $p-1 \equiv 0 \pmod 3$.

Since $773 \equiv2 \pmod 3$, it is not a factor of a number of the form $n^2+n+1$

share|cite|improve this answer
Very nice approach. :) – J.H. Feb 15 '13 at 15:40

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.