All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Dozen Divisibility Dilemma (Posted on 2010-12-02)
Each of x and y is a positive integer such that: x2 – 5y2 = 1.

Prove that x*y is always divisible by 12.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Possible solution | Comment 1 of 4

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  x2–5y2=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

 Search: Search body:
Forums (0)