# Prime Divisors of the $x \mapsto 2x+1$ Recursion

The Cohen-Lenstra statistics describe how often a prime divides the class number of quadratic number field $\mathbb{Q}[\sqrt{d}]$

$$\mathbb{P}\big[h(d) \not\equiv 0\; (\mod p) \big] = \prod_{k \geq 2}\left( 1 - \frac{1}{p^k}\right)$$

As can be seen in Section 6.3 of this Number Theory course by Andrew Granville.

I would like to know if there is a similar conjecture for the continued fraction convergents of $1 + \sqrt{2}$. Notice that

$$\sqrt{2}+1 = 2 + \frac{1}{\sqrt{2}+1} = [2,2,2,\dots]$$

Therefore, the convergents of the continued fraction can be generated by recursion

$$\frac{1}{1}, \frac{2}{1}, \frac{5}{3}, \frac{12}{7}, \frac{29}{17}, \dots$$

In particular, the numberators satisfy the recursion $a_{n+1} = 2 a_n + a_{n-1}$, and it seems likely the divisibility properties of this number should be "random".

The distribution of the primes dividing $a_n$ satisfy pattern like Cohen-Lenstra?

• This has nothing to do with Cohen-Lenstra. You're talking about prime divisors of a recursive sequence -- for instance, see the book "Recurrence Sequences" by Everest, van der Poorten, Shparlinski and Ward. – Michael Zieve May 11 '14 at 18:24
• @MichaelZieve I can't seem to find a copy online. Can you state the result? – john mangual May 11 '14 at 18:40
• Google books shows you enough of the book, google points you to free copies. – Michael Zieve May 11 '14 at 19:51
• @MichaelZieve In the process of Googling the book I found a variety of papers - honestly I cannot believe what I am reading. – john mangual May 11 '14 at 20:00
• @quid my question was not answered at all. I just have this one book reference – john mangual May 11 '14 at 23:25

The divisibility properties of the numbers defined by $a_{n+1}=2a_n+a_{n-1}$ (and $a_1=1$ and $a_2=2$) are not random. One reason for this is that this sequence has the very non-random property of being eventually periodic mod $N$, for every integer $N$. In particular, since $$a_n = \frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}},$$ we see that if $p$ is an odd prime then $a_n\equiv 0\pmod{p}$ if and only if $n$ is a multiple of the order of $$\frac{1+\sqrt{2}}{1-\sqrt{2}} = -(1+\sqrt{2})^2$$ in the multiplicative group of $\mathbf{F}_p(\sqrt{2})$. (Note that the order of this element does not depend on the choice of a square root of $2$ in $\mathbf{F}_{p^2}^*$.) Therefore if $p$ is an odd prime then $$\mathbb{P}\bigl[a_n\equiv 0\pmod{p}\bigr] = \frac{1}{c_p}$$ where $c_p$ is the order of $-(1+\sqrt{2})^2$ in $\mathbf{F}_{p^2}^*$. For completeness, I note that the terms of the sequence $(a_n)$ alternate in parity, so that half of them are even and half are odd.
The next question is to understand the distribution of the numbers $c_p$, where $p$ is an odd prime. This connects with the number field analogue of Artin's primitive root conjecture. First consider primes $p$ with $p\equiv 1\pmod{8}$: for such primes, both $-1$ and $2$ are squares in $\mathbf{F}_p^*$, so that also $-(1+\sqrt{2})^2$ is a square and thus $c_p\mid (p-1)/2$. It is expected that there are infinitely many primes $p\equiv 1\pmod{8}$ for which $1+\sqrt{2}$ generates $\mathbf{F}_p^*$ (so that $c_p= (p-1)/2$), and further there is a heuristically predicted (positive) value for the density of such primes $p$. Similar remarks apply when $p\equiv -1\pmod{8}$. Next if $p\equiv 3\pmod{8}$ then $2$ is a nonsquare in $\mathbf{F}_p^*$, but every unit in $\mathbf{Z}[\sqrt{2}]$ has norm $\pm 1$ and hence its image in $\mathbf{F}_{p^2}^*$ has order dividing $2(p+1)$, so that $c_p\mid (p+1)$. Further, there is a heuristically predicted (positive) value for the density of the set of primes $p\equiv 3\pmod{8}$ for which $c_p=(p+1)$. Again, similar remarks apply when $p\equiv -3\pmod{8}$. These heuristic predictions have been proved under the assumption of suitable Generalized Riemann Hypotheses. For references, see Pieter Moree's comprehensive survey on Artin's primitive root conjecture, which contains a wealth of further information.