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?

  • 4
    $\begingroup$ 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. $\endgroup$ May 11, 2014 at 18:24
  • $\begingroup$ @MichaelZieve I can't seem to find a copy online. Can you state the result? $\endgroup$ May 11, 2014 at 18:40
  • $\begingroup$ Google books shows you enough of the book, google points you to free copies. $\endgroup$ May 11, 2014 at 19:51
  • $\begingroup$ @MichaelZieve In the process of Googling the book I found a variety of papers - honestly I cannot believe what I am reading. $\endgroup$ May 11, 2014 at 20:00
  • $\begingroup$ @quid my question was not answered at all. I just have this one book reference $\endgroup$ May 11, 2014 at 23:25

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .