Thread: Divisibility Problem: Generating x to get integer y's in a linear equation

I've been helping students with graphing linear equations in the standard form lately, and I was wanting to come up with a way to figure out what values we could put in for one variable and get an integer for the other.

We're looking at , where a,b,c are known integers.

Alternately,

So I need to find such that for all

I've never taken a number theory course, so please use an explanation that'll make sense to me. Thanks.

Hello, beebe!

Here is an elementary (very primitive) approach.

I've been helping students with graphing linear equations in the standard form lately.
I wanted a way to figure out what values we could put in for one variable and get an integer for the other.

We're looking at , where are known integers.

It's best if I use a specific equation.







. .





. .














. . .

it's not always possible.

for example take:

2x + 6y = 5

the integer on the LHS will always be even, but 5 is odd.

if, however, gcd(a,b) = 1, it WILL be possible to find suitable x.

the equation c - ax = nb (for SOME n, not for EVERY n, which clearly cannot be the case) is the same as:

c = ax (mod b) <---this means EXACTLY the same thing as c - ax = nb.

in the case that gcd(a,b) = 1 there WILL be some integer k with ka = 1 (mod b).

if gcd(a,b) = 1, there are integers r and s with: ra + sb = 1 (the integers r and s can be found by using repeated division, using the euclidean algorithm:

for example:

gcd(3,8) = 1

8 = 2*3 + 2
3 = 1*2 + 1
2 = 2*1 + 0

from the second equation we get:

1 = 3 - 2. from the first we get: 2 = 8 - 6, so:

1 = 3 - 2 = 3 - (8 - 6) = 3 - (8 - 2*3) = 3 - 8 + 2*3 = (1+2)*3 - 8 = 3*3 + (-1)*8, so r = -1, and s = 3).

but ra + sb = 1 is the same as: ra = 1 + (-s)b, or ra = 1 (mod b) (these two things are THE SAME, just "different ways of saying it").

so the "k" we were looking for earlier is "r".

now if c = ax (mod b), then:

kc = (ka)x (mod n)

kc = (1)x (mod b)

kc = x (mod b) <--these x will work. we can, if you prefer, write these numbers as:

x = kc + nb.

*********

following Soroban's example, let's do this for 8x - 3y = 7. here a = 8, b = 3 and c = 7.

note that gcd(3,8) = 1 (see above), and we established that (-1)*8 + 3*3 = 1. so the "k" we want is k = -1.

this gives us:

x = (-1)(7) + 3n = -7 + 3n as our possible x's. since "n" can be any integer, we can re-write this as:

x = -1 + -6 + 3n = -1 + 3(n - 2). if n runs through all the integers, so does m = n - 2, so we have:

x = -1 + 3m, m in Z.

subbing back in for y:

8(3m - 1) - 3y = 7

24m - 8 - 3y = 7

3y = 24m - 8 - 7

y = -5 + 3m, m in Z.

**********

a number-theorist (working mod 3) would probably prefer to write:

ax = c (mod b)
x = ca^-1 (mod b)

working mod 3, the equation becomes:

2x = 1 (mod 3)
x = 2 (mod 3) (since 2*2 = 4 = 1 (mod 3) (4 is 1 more than a multiple of 3)).

so x = 3m + 2

this answer may LOOK different, but since 2 - (-1) = 3, which is a multiple of 3, 2 = -1 mod 3. if you actually start "plugging in" different value for m, you get:

3m - 1 = {......-7,-4,-1,2,5,8,....}

3m + 2 = {......-4,-1,2,5,8,11,....}

these are the same integers just "shifted 3 over".

*********

this answer may seem "less intuitive" than Soroban's. people often regard modular arithmetic as "something abstract and complicated". it's not, but perhaps i am not doing it justice, here. ok, you know that:

c - ax has to be a multiple of b, for y to be an integer. this means that we are concerned with how well c - ax "lines up" with the "multiples of b".

so when we say: "b divides c - ax" what we mean is: when we divide c - ax by b, we get a remainder of 0.

modular arithmetic is "the arithmetic of remainders". it turns out that:

"the remainder of the sum (when divided by b) is the sum of the remainders (up to a multiple of b)"

"the remainder of the product is the product of the remainders (up to, again, a multiple of b)".

remainders REPEAT every b integers, so we have fewer of them to deal with (the "numbers" are smaller). and they are VERY handy when investigating "what divides what".

this rich "remainder structure" is woven into the integers as part and parcel of what they ARE.

********

short version: pick "b" carefully, if you want to make examples. choosing "b" so that a and b have a common prime factor may go very badly.

Thank you. Both replies were very helpful.