Find all positive integers X and Y such that:
- X divides Y+5, and:
- Y divides X+3
Prove that there are no others.
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
Proof of completeness without solution
