## Saturday, September 23, 2006

### Pell. Topic: NT. Level: AIME/Olympiad.

Problem: (2000 Putnam - A2) Prove that there exist infinitely many integers $n$ such that $n, n + 1, n + 2$ are each the sum of the squares of two integers. [Example: $0 = 0^2 + 0^2$, $1 = 0^2 + 1^2$, $2 = 1^2 + 1^2$.]

Solution: Consider the Pell Equation

$x^2-2y^2 = 1$.

It is well-known that this equation has an infinite number of positive integer solutions $(x,y)$. This can be derived using truncated continued fractions representation of $\sqrt{2}$ (see here). So if we let $n = 2y^2 = y^2+y^2$, we have

$n+1 = x^2+0^2$

$n+2 = x^2+1^2$,

completing the problem. QED.

--------------------

Comment: This was one of the official solutions to the problem, even though all you had to know was that Pell Equations have an infinite number of solutions. There is a constructive solution to the problem as well, based on choosing certain $n$.

--------------------

Practice Problem: Find the constructive solution (i.e. all numbers of the form $n = f(k)$ work for some function $f$).