Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By Soroban
  • 1 Post By Deveno

Math Help - Divisibility Problem: Generating x to get integer y's in a linear equation

  1. #1
    Junior Member beebe's Avatar
    Joined
    Aug 2011
    Posts
    54

    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 ax+by=c, where a,b,c are known integers.

    Alternately, y=\frac{c-ax}{b}

    So I need to find x\in\mathbb{Z} such that c-ax=nb for all n\in\mathbb{Z}

    I've never taken a number theory course, so please use an explanation that'll make sense to me. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,803
    Thanks
    694

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

    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 ax+by\:=\:c, where a,b,c are known integers.

    It's best if I use a specific equation.

    \text{Suppose we have: }\:8x - 3y \:=\:7

    \text{Solve for }y\!:\;y \:=\:\frac{8x-7}{3} \quad\Rightarrow\quad y \;=\;2x - 2 + \frac{2x-1}{3}\;\;{\color{blue}[1]}

    \text{Since }y\text{ is an integer, }2x\!-\!1\text{ must be a multiple of 3.}

    . . \text{That is, }2x - 1 \:=\:3a,\,\text{ for some integer }a.

    \text{Solve for }x\!:\:x \:=\:\frac{3a+1}{2} \quad\Rightarrow\quad x\:=\:a + \frac{a+1}{2}\;\;{\color{blue}[2]}

    \text{Since }x\text{ is an integer, }a\!+\!1\text{ must be a multiple of 2.}

    . . \text{That is: }a+1 \:=\:2b,\text{ for some integer }b.

    \text{Hence: }\:a \:=\:2b-1


    \text{Substitute into }{\color{blue}[2]}\!:\:x \;=\;(2b-1) + \frac{(2b-1)+1}{2}
    \text{And we have: }\:\boxed{x \;=\;3b-1}


    \text{Substitute into }{\color{blue}[1]}:\:y \:=\:2(3b-1) - 2 + \frac{2(3b-1)-1}{3}
    \text{And we have: }\:\boxed{y \;=\;8b-5}


    \text{The equation }8x-3y \:=\:7\,\text{ has integer solutions:}

    . . . \begin{Bmatrix}x &=& 3b-1 \\ y &=& 8b-5\end{Bmatrix}\;\text{ for any integer }b.
    Thanks from beebe
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Divisibility Problem: Generating x to get integer y's in a linear 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.
    Thanks from beebe
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member beebe's Avatar
    Joined
    Aug 2011
    Posts
    54

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

    Thank you. Both replies were very helpful.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Opinion on proof(Integer divisibility)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 29th 2010, 10:35 PM
  2. Divisibility proof in random integer subset
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 10th 2009, 11:14 AM
  3. generating an equation for a problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 8th 2009, 12:05 PM
  4. Generating Functions and Integer Partitions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 9th 2008, 08:28 AM
  5. Generating a Linear Programming problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 8th 2007, 03:05 PM

Search Tags


/mathhelpforum @mathhelpforum