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$ Commented May 11, 2014 at 18:24
  • $\begingroup$ @MichaelZieve I can't seem to find a copy online. Can you state the result? $\endgroup$ Commented May 11, 2014 at 18:40
  • $\begingroup$ Google books shows you enough of the book, google points you to free copies. $\endgroup$ Commented 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$ Commented May 11, 2014 at 20:00
  • $\begingroup$ @quid my question was not answered at all. I just have this one book reference $\endgroup$ Commented 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.