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

Home > Just Math
Dozen Divisibility Dilemma (Posted on 2010-12-02) Difficulty: 3 of 5
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.)
Some Thoughts 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  x25y2=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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information