素数の存在について

数列 ${a_n}$ を、初項 $a_1 = 2$、漸化式
$
a_{n+1} = a_n^2 - a_n + 1 \quad (n = 1, 2, 3, \ldots)
$
によって定める。このとき、以下の問いに答えよ。

(1)$p$ を $5$ 以上の素数とし、$k$ を整数とする。
合同式
$
x^2 + x + 1 \equiv 0 \pmod p
$
が整数解 $x = k$ を持つとき、$p \equiv 1 \pmod 3$ となることを証明せよ。

(2)任意の自然数 $n$ に対して、$a_n$ を割り切る素因数 $q$ は、$q = 2$、$q = 3$、または $q \equiv 1 \pmod 6$ のいずれかであることを示せ。
さらに、これを用いて「$p \equiv 1 \pmod 6$ を満たす素数 $p$ は無限に存在する」ことを証明せよ。