Factoring the sequence ${10}^{2n}+10^{n}+1$

Question

While I am waiting for the basketball NBA game between Cleveland Cavaliers and Golden State Warriors to begin I sort of played with the sequence $a_n={10}^{2n}+10^{n}+1$ in a way that I looked for the prime factors for small values of $n$.

For $n=1$ we have $111=3 \cdot 37$.

For $n=2$ we have $10101=3 \cdot 7 \cdot 13 \cdot 37$

For $n=3$ we have $1001001=3 \cdot 333667$

For $n=4$ we have $100010001=3 \cdot 7 \cdot 13 \cdot 37 \cdot 9901$

For $n=5$ we have $10000100001=3 \cdot 31 \cdot 37 \cdot 2906161$

For these small values of $n$ we see that $a_n={10}^{2n}+10^{n}+1$ have no repeated prime factors, in other words, for these small values of $n$ every prime number in the factorization occurs with an exponent $1$.

I am interested in the following:

What is the smallest value of $n$ for which $a_n={10}^{2n}+10^{n}+1$ has repeated prime factor?

Answer 1

For $n=14$ you get $$10^{28}+10^{14}+1=3\times7^2\times13\times37\times43\times127\times1933\times2689\times459691\times10838689,$$ and checking the smaller values of $n$ shows that this is the smallest that will do.

Answer 2

$a_n$ is divisible by $p^2$ if $x = 10^n$ is a solution of $x^2 + x + 1 \equiv 0 \mod p^2$. We may assume $p$ is not $2$ or $5$, so $x$ is coprime to $p$. Now $4 (x^2 + x + 1) = (2x + 1)^2 + 3$, so $2x + 1$ must be a square root of $-3$ mod $p^2$. If $p$ is an odd prime (other than $3$) for which $-3$ is a quadratic residue, i.e. $p \equiv 1 \mod 6$, then there are two square roots of $-3$ mod $p^2$, and thus two solutions of $x^2 + x + 1 \equiv 0 \mod p^2$ in $[1, \ldots, p^2-1]$. There may or may not be $n$ for which $10^n$ is one of these values: if there is, such $n$ will repeat according to the order of $10$ in the multiplicative group mod $p^2$.

For example, $x^2 +x+1 \equiv 0 \mod 7^2$ iff $x \equiv 18, 30 \mod 7^2$; $10^n \equiv 18 \mod 7^2$ for $n \equiv 28 \mod 42$ and $10^n \equiv 30 \mod 7^2$ for $n \equiv 14 \mod 42$, where $42$ is the order of $10$ mod $7^2$.

The first few values of $n$ for which $10^{2n}+10^n+1$ is divisible by the square of a prime turn out to be $14$, $26$, $28$ and $37$, for which $10^{2n}+10^n + 1$ is divisible by $7^2$, $13^2$, $7^2$ and $37^2$ respectively.