# Sequence involving primes of form $n^2 + n+1$

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.

Thanks.

-
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

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$