Prove that a linear integer combination of two values cannot lie in a given range

271 Views Asked by At

If I am given two values such as $x = 14$ and $y = 21 $ is there any reliable method to prove that the sum of combinations of these numbers can lie in the range $170-174$?

I am assuming it has something to do with the $\operatorname{gcf}(a, b)$ which is $7$. I'm looking for a method more efficient than trying all possible combinations.

2

There are 2 best solutions below

0
On

Since the greatest common divisor of $14$ and $21$ is $7$, any linear combination $14n + 21m$ is divisible by $7$. However, no number between $170$ and $174$ is divisible by $7$, so no linear combination of $14$ and $21$ can be between $170$ and $174$.

0
On

This can be seen as a Diophantine equation $ax + by = c$. The equation can only have solutions if $c$ is a multiple of the greatest common divisor. In this case there are no multiples of $7$(the gcd) in that range so no combinations will exist. Also note that the combinations differ by seven. For example $168$ and $175$ are possible. So this ranged would be a size of $5$ between any solutions.