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

Home > Just Math
Squarely Divisible? (Posted on 2009-12-31) Difficulty: 1 of 5
Can there exist three integers p, q and r with 2 ≤ p < q < r, that satisfy each of the following conditions?

(i) p2 -1 is divisible by each of q and r, and:

(ii) r2 -1 is divisible by each of p and q.

No Solution Yet Submitted by K Sengupta    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Relatively speaking (solution) | Comment 1 of 2
No, this is not possible.

Lemma) x divides y2 -1 only if x and y are relatively prime.  This is because if they had any common factors, that common factor would divide y2 evenly, so it could not divide y2 -1 evenly.

Proof) Assume that p, q and r exists.

Since r2 -1 is divisible by q,  q and r do not share a common factor.

Since q & r both divide p2 -1, and since they have no common factors, then q*r <= p2 -1, since they at most have all factors of p2 -1 accounted for between them, without any overlap.  But q and r are both > p, so q*r >p*p > p2 -1, so a contradiction exists.

Therefore, p, q and r do not exist.  

  Posted by Steve Herman on 2010-01-02 21:45:23
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information