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

Home > Just Math
Integer Divisibility Dilemma (Posted on 2014-04-10) Difficulty: 2 of 5
Find all positive integers X and Y such that:
  • X divides Y+5, and:
  • Y divides X+3
Prove that there are no others.

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 Proof of completeness without solution Comment 6 of 6 |
Let's prove the general case where
(1) x divides y + a, all numbers positive integers
(2) y divides x + b, all numbers positive integers

First we prove that x and y cannot both be greater than (a+b).

Assume x and y are both > (a+b) 
Consider the only three cases:

Case 1) x = y

   substituting in equation 2 gives y divides y + b.
   so y must be <= b
   this is a contradiction
Case 2) y > x
   y divides x + b only if y = x+b
   substituting in equation 1 gives x divides x + (a+b)
   so x must <= (a+b)
   this is a contradiction
Case 2) x > y
   x divides y+a only if x = y+a
   substituting in equation 2 gives y divides y + (a+b)
   so y must be <= (a+b)
   this is a contradiction.
Therefore, our initial assumption is wrong and we have proved that x and y cannot both be greater than (a+b).
Using this result, we can determine individual upper limits on x and y:
   y divides x + b, so y <= (a+b) + b
   x divides y + a, so x <= (a+b) + a
In other words, x <= 2a + b and y <= a + 2b
 In our specfic case, a = 5 and b = 3,
 so x <= 13 and y <= 11

Edited on April 11, 2014, 12:27 pm
  Posted by Steve Herman on 2014-04-10 16:39:05

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

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

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