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

2 comments:

  1. Can anyone post a link to some learning material about Pell equations, one showing the techniques to solve them?

    ReplyDelete
  2. The MathWorld link up there has quite a bit of info... otherwise just Google it.

    BTW, sorry for comments not showing up immediately; I need to moderate them or else I'll get loads of spam.

    ReplyDelete