# Prime factors of the members of a certain recurrence

It is possible to prove elementarily that there are infinitely many primes that divide some element of the sequence $a_0 = k\ge 0$, $a_n = a_{n-1}^2+ 1$ for all $n\ge 1$ by showing that for all $m$, there exists $C$ that depends only on $m$ s.t. $(a_n, a_{m + n})\le C$ and then showing that this is not possible if there are only finitely many primes that divide it.

However, I don't know of any results that might help prove the following, stronger statement:

For any (finite) set of primes $S$, there are only finitely many solutions to $$n^2 + 1 = m$$ for $m,n$ s.t. $p|mn \Rightarrow p\in S$

How would one prove this?

• Stormer on consecutive smooth numbers. (solving finitely many Pell equations, I think.) – The Masked Avenger Oct 13 '14 at 6:22
• I guess you mean Thue equations (namely $aX^3-bY^3=1$), not Pell equations which can have infinitely many integer solutions. – Noam D. Elkies Oct 13 '14 at 6:25
• @NoamD.Elkies, our friend Don has the Lehmer reference that I did not remember. Perhaps there is an alternative solution using Thue equations? – The Masked Avenger Oct 13 '14 at 16:32

It is even true that the equation $n^2+1=m$ with $p|m\Rightarrow p\in S$ has only finitely many solutions. To see this note that every $m$ satisfying this property can be written as $m=m_1m_2^3$, where $m_1$ has only prime factors in $S$ and is cubefree. In particular $m_1$ comes from a finite set of integers. Hence it suffices to show that for a given $m_1$ the number of integral solutions of $n^2+1=m_1m_2^3$ is finite. But this is a special case of a result by Siegel stating that an elliptic curve has only finitely many integral points.

It is even true that the equation $n+1=m$ (without the square) with $p|mn \Rightarrow p \in S$ has only finitely many solutions in $\mathbb{Z}$ when $S$ is a fixed finite set of primes.

This is an $S$-unit equation, about which there exists a large body of literature. The basic (ineffective) finiteness result, due to Siegel, can be proved by a refinement of the argument mentioned in Jan-Christoph's answer. With somewhat stronger tools from transcendence theory, one can also effectively bound the possible solutions in terms of $S$.

As The Masked Avenger has hinted at, one can find all $n$ for which $n^2+1$ has all prime factors below a given bound by looking among the first several solutions to finitely many Pell equations. Størmer described this method already in 1897. This predates Siegel by thirty years. See also

Lehmer, D. H. (1964). "On a Problem of Størmer". Illinois Journal of Mathematics 8: 57–79. MR 0158849.

(Note that Størmer's method is less pliable than the solutions based on Siegel's theorem; it applies only to $n^2+1$ and a few other polynomials.)

For a modern variant of Størmer, see e.g., http://web.math.pmf.unizg.hr/glasnik/45.2/45(2)-04.pdf

• I suspect that it is more accurate to say "both $n$ and $n^2+1$ have all prime factors below a given bound". However, I haven't read Lehmer's paper nor Stormer's. – The Masked Avenger Oct 16 '14 at 19:43