# Search square factors in Lucas–Lehmer sequence

I’m interested in some sequences which have no square factor. $$s_i =\begin{cases} 4 & i=0; \\\\ s_{i-1}^2 - 2 & \text{otherwise} \end{cases}$$ This is Lucas–Lehmer primality test sequence. A003010 in OEIS.

when ${s_i}$ has a square factor? I had checked that the sequence has no square factor for i=1,2,...,7

• I edited this by using MythType. I don't know why Tex doesn't work here. Could you help me? what's "TeX ed" – a boy Aug 27 '10 at 2:17
• @a-boy: I was saying that you have "Texed" the question properly. Thats all! – anonymous Aug 27 '10 at 2:20

It seems plausible that there may be no square factors other than $4$, or at least that there are only finitely many primes for which $p^2$ divides $s_n$. A sketchy argument follows:

Set $\tau=2 +\sqrt{3}$. Then $s_n = \tau^{2^n} + \tau^{-2^n}$. We work in the ring $R=\mathbb{Z}[\sqrt{3}]$, where $\tau$ is a unit. So $p^2$ divides $S_n$ if and only if $\tau^{2^{n+1}} \equiv 1 \mod p^2$, where our congruence is in $R$.

Let $p$ be a prime $\geq 5$. Let $U_{p^2}$ be the unit group of $R/p^2 R$. You want to know whether the order of $\tau$ in $U_{p^2}$ is a power of $2$.

There are two cases. First, suppose there is a square root of $3$ mod $p$ (this happens when $p \equiv \pm 1 \mod 12$). This square root will lift to a solution $s$ of $s^2 \equiv 3 \mod p^2$ (we can lift by Hensel's lemma). In this case $R/p^2 \cong \mathbb{Z}/p^2 \oplus \mathbb{Z}/p^2$ and we can identify $\tau$ with the ordered pair $(2 + s, 2 - s)$. Notice that $2-s = (2+s)^{-1}$, so the two halves of the ordered pair have the same order. The unit group of $\mathbb{Z}/p^2$ is cyclic of order $p(p-1)$, and the number of elements whose orders are powers of $p$ is $2^{v_2(p-1)}$, where $v_2(k)$ is the exponent to which $2$ divides $k$. So, heuristically, I would expect the number of $p$ for which $p^2$ divides $s_n$ and there is a square root of $3$ mod $p$ to be something like $$\sum_{p \equiv \pm 1 \mod 12} \frac{2^{v_2(p-1)}}{p(p-1)}.$$

There case where where $p \equiv \pm 5 \mod 12$ is a little trickier but, if I haven't made any mistakes, the similar heuristic estimate is $$\sum_{p \equiv \pm 5 \mod 12} \frac{2^{v_2(p+1)}}{p(p+1)}.$$

Now, here is my point: those sums converge. In fact, $$\sum_{n=1}^{\infty} \frac{2^{v_2(n)}}{n^2}$$ converges to $\pi^2/4$ (exercise!) and the above sums are less than this because they are restricted to just summing over primes. Moreover, the sum numerically looks pretty small.

So the "expected" number of such primes is a small finite quantity, and it wouldn't surprise me if $2$ were the only one.