Ask A Scientist Mathematics Archive

Author:      yendor
Could someone give me the necessary and sufficient conditions on the non-
zero integers a,b,c such that the graph of ax+by=c contains a point (a',b')
where a' and b' are integers.  Please give an example or two to demonstrate
this.

Response #:  1 of 2
Author:      jlu
But if a' and b' are integers, the c is necessarily an integer.  On the
other hand, if c is an integer, then there are obviously rational (non-inte-
ger) values of a' and b' for which c is not an integer.  I think that the
proposition, as you have stated it, is false.

Response #:  2 of 2
Author:      asmith
I cannot say I understand jlu's point.  Anyway, suppose a = 2, b = 4, and 
c = 3.  Then there cannot be any integer solutions for a', b', because 
ax + by is always even, if x and y are integers, and so can never be equal
to 3.  I believe the necessary and sufficient conditions are that any common
divisor of a and b (such as 2 in the above example) must also divide c
evenly.  If that is true, then the common divisors can be factored out of
the equation, and so one can simply start by assuming a and b have no common
divisors - and there is a well-known result that for any two numbers which
have this property, you can find integers x and y such that ax + by = 1. 
Then just multiply both x and y by c and you have the solution you want.  So
this condition is sufficient.  It is obviously necessary, for the same
reason as in the example above.