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

 Squarely Divisible? (Posted on 2009-12-31)
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.)
 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

 Search: Search body:
Forums (0)