Results 1 to 7 of 7

Math Help - division algorithm

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    14

    division algorithm

    I'm having trouble with a problem, in my abstract algebra class, don't know how to even begin...

    Let n be a positive integer. Prove that a and c leave the same remainder when divided by n if and only if a - c = nk for some integer k.

    Now, i understand that the division algorithm basically states a = bq + r. In this case, n would be substituted with b. But, I'm a little confused on how to prove what it's asking for, or if I even understand what it's asking for. Please help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2007
    Posts
    14
    Quote Originally Posted by topsquark View Post
    If a - c = nk then a = nx + r and c = ny + r for integer x, y, and r. Thus
    r = c - ny = a - nx
    c - ny = a - nx
    a - c = nx - ny = n(x - y)

    But x - y is an integer, say k.

    Thus
    a - c = nk.
    I did get to that point, but see, my problem is, I'm not sure that would acctually prove what I want, because in the begginig, you are assuming what you are trying to prove... theres no way you could find it any other way in the end, cuz in the begginig it was your starting assumtion....

    Now you prove it the other way: Assume a - c = nk and show that this gives a = nx + r and c = ny + s means that r = s.
    And I've tried this way, but maybe I'm missing something... but, this is what I got by doing it that way... so far....

    Since a = nx + r and c = ny + s, than filling it in the equation i want to prove, :
    nx + r - ny - s = nk
    but... I still don't know how to isolate the r and the s.... the other integers don't cancel out, I can simplify it a little bit, but I'm not sure how much help it would be to put it in this form:

    r - s = n(y - x + k)

    except for the fact that it resembles the first form, (no with integers but with format) I can't see where to go from here.... *sighs* unless i was able to prove that either n = 0 ( which i didn't think it could be, because it says let n be a positive integer) or I have to prove that y - x + k = 0.....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Quote Originally Posted by fruitbodywash View Post
    I did get to that point, but see, my problem is, I'm not sure that would acctually prove what I want, because in the begginig, you are assuming what you are trying to prove... theres no way you could find it any other way in the end, cuz in the begginig it was your starting assumtion....


    And I've tried this way, but maybe I'm missing something... but, this is what I got by doing it that way... so far....

    Since a = nx + r and c = ny + s, than filling it in the equation i want to prove, :
    nx + r - ny - s = nk
    but... I still don't know how to isolate the r and the s.... the other integers don't cancel out, I can simplify it a little bit, but I'm not sure how much help it would be to put it in this form:

    r - s = n(y - x + k)

    except for the fact that it resembles the first form, (no with integers but with format) I can't see where to go from here.... *sighs* unless i was able to prove that either n = 0 ( which i didn't think it could be, because it says let n be a positive integer) or I have to prove that y - x + k = 0.....
    You are right, I goofed. Let's try this for the forward proof:
    Let a - c = nk. We wish to show that both a and c leave the same remainder when divided by n.

    So
    a = nx + q
    c = ny + r
    where x, y, q, r are unique positive integers (when 0 \leq q,r < n.)

    Thus
    a - c = (nx + q) - (ny + r) = n(x - y) + (q - r)

    But
    a - c = nk
    by hypothesis.

    Thus
    nk = n(x - y) + (q - r)

    Since both q and r are less than n, so is q - r. Thus in order for this equation to be satisfied by integers we must have that k = x - y and 0 = q - r. ie q = r.

    Thus
    a = nx + r
    c = ny + r
    and they leave the same remainder.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2007
    Posts
    14
    Quote Originally Posted by topsquark View Post
    Since both q and r are less than n, so is q - r. Thus in order for this equation to be satisfied by integers we must have that k = x - y and 0 = q - r. ie q = r.

    Thus
    a = nx + r
    c = ny + r
    and they leave the same remainder.

    -Dan
    I'm not sure i follow this.... i mean, i understand that q - r will be less than n, but that might not neccisarrily mean that it has to be zero... n could be say... 2 and q - r is 1... and the less than statement would still hold.... I know we want to prove that q - r = 0, but I can't quit seem to understand that step the gets from point A "nk = n(x - y) + (q - r)" to point B "k = (x - y)"... *sighs* thanks for being patient with me
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2007
    Posts
    14
    eureka!

    ok, i think I got it... let me know if this makes sense...

    Known :
    a = nx + r
    c = ny + s
    0 < n
    0 <= r < n
    0 <= s < n
    r - s < n
    s - r < n

    Ok... now for the rearranging.... using a - c = nk
    a - c = nk ==> (nx + r) - (ny + s) = nk
    ==> nx + r - ny - s = nk ==> r - s = ny - nx + nk
    ==> r - s = n(y - x + k)
    (this next step... is where I'm a little unsure....)
    ==> (r - s)/n = y - x + k = 0 (because... r - s < n... right?)
    ==> k = x - y
    (back to the first equation) a - c = nk
    ==> (nx + r) - (ny + s) = n(x - y)
    ==> nx + r - ny + s = nx - ny
    ==> r - s = 0 ==> r = s ............? is that right?
    ( I think that that is what you were trying to say up there, but I'm just re-itterating it to you to make sure that I understand it)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Quote Originally Posted by fruitbodywash View Post
    eureka!

    ok, i think I got it... let me know if this makes sense...

    Known :
    a = nx + r
    c = ny + s
    0 < n
    0 <= r < n
    0 <= s < n
    r - s < n
    s - r < n

    Ok... now for the rearranging.... using a - c = nk
    a - c = nk ==> (nx + r) - (ny + s) = nk
    ==> nx + r - ny - s = nk ==> r - s = ny - nx + nk
    ==> r - s = n(y - x + k)
    (this next step... is where I'm a little unsure....)
    ==> (r - s)/n = y - x + k = 0 (because... r - s < n... right?)
    ==> k = x - y
    (back to the first equation) a - c = nk
    ==> (nx + r) - (ny + s) = n(x - y)
    ==> nx + r - ny + s = nx - ny
    ==> r - s = 0 ==> r = s ............? is that right?
    ( I think that that is what you were trying to say up there, but I'm just re-itterating it to you to make sure that I understand it)
    As far as I know that will work.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fruitbodywash View Post
    I'm having trouble with a problem, in my abstract algebra class, don't know how to even begin...
    No wonder you are having trouble, you have the home work from
    the elementary number theory class.

    Let n be a positive integer. Prove that a and c leave the same remainder when divided by n if and only if a - c = nk for some integer k.

    Now, i understand that the division algorithm basically states a = bq + r. In this case, n would be substituted with b. But, I'm a little confused on how to prove what it's asking for, or if I even understand what it's asking for. Please help!
    If a and c leave the same remainder when divided by n, then they may be
    written: a=k1 n + r, c=k2 n + r, so a-c = (k1-k2)n, which proves one half of
    the if and only if.

    If a-c=k n, then as we have a=k1 n + r1, c=k2 n + r2 for same k1, k2, 0<=r1<n, 0<=r2<n:

    a-c = (k1-k2)n + (r1-r2),

    so r1-r2= k3 n for some k3, so r1 = k3 n + r2, so a= (k1+k3)n + r2, hence
    r1=r2. Which proves the other half of the if and only if.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The Division Algorithm 2
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 5th 2011, 01:18 PM
  2. Division Algorithm.....
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: June 26th 2010, 07:53 AM
  3. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 01:51 PM
  4. Division Algorithm
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 18th 2009, 04:11 PM
  5. Division Algorithm...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 8th 2008, 09:33 PM

Search Tags


/mathhelpforum @mathhelpforum