2
$\begingroup$

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?

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

3 Answers 3

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – The Masked Avenger
    Commented Oct 16, 2014 at 19:43

You must log in to answer this question.

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