Each of x and y is a positive integer such that: x² – 5y² = 1.

Prove that x*y is always divisible by 12.

This is a classic 'Pell' Equation, of the form x^2-ny^2=1.

There is a good resource for solving them here: http://www.alpertron.com.ar/QUAD.HTM

The fundamental solution is then {(p=9, q=20) u (r=4  s=9) v} which can be used as explained in the above website to generate all other solutions of the equation. There is also a very good article here http://www.ams.org/notices/200202/fea-lenstra.pdf explaining the concept in more detail (by coincidence it also refers to the same equation  x²–5y²=1).

The recurrence relation could then be used to confirm the claim; but there is a more elementary method:

Assume x is even and=2n. Then 4n^2-1=5y^2 and 5y^2 is worth 3(mod4). But 5y^2 is worth {0,1}(mod 4) for all y, a contradiction. So x is odd.

(x+1)(x-1) = 5y^2, and either 3 divides x, or it divides y, since one of (x-1), x, or (x+1) is divisible by 3.

(x+1)(x-1) = 5y^2. Since x is odd,  (x+1) is even and (x-1) is even, so y is divisible by 4.

Hence x*y is divisible by 12. QED

Edited on December 4, 2010, 1:03 am

Posted by broll on 2010-12-03 04:49:42