1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Division algorithm

  1. Mar 23, 2014 #1
    So, the division algorithm states that if a and b are integers with a>0 then there exist c and d integers such that

    0<=d<a

    b=ac+d

    d and c are unique

    Now I don't understand d and c being unique. For example 4*3 + 3 = 15 where a=4 c=3 d=3 b=15
    c and d are not unique, or maybe I don't know what unique means?
     
  2. jcsd
  3. Mar 23, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    15 = 5*3 + 0, with 'remainder' d = 0. In your example, the remainder was d = 3, which is not strictly less than 3 as was required in the theorem.
     
  4. Mar 23, 2014 #3
    I don't get it. I divided 15 by 4; so this theorem doesn't work for all numbers?
     
  5. Mar 23, 2014 #4
    Did you expect c ≠ d? That's not what unique means. It just means that there is only one combination of c and d. So c=3, d=3 is a solution for a=4, b=15 (ie. 15/4 = 3 + 3/4), and there are no other combinations of c and d that also work.
     
  6. Mar 23, 2014 #5
    So all I should really take from this theorem is that given two integers (b>0) there is always one and only one solution for c and d I take it......
     
  7. Mar 23, 2014 #6
    Yup, that's how I read it.
     
  8. Mar 23, 2014 #7
    end thread
     
    Last edited: Mar 23, 2014
  9. Mar 23, 2014 #8
    Sorry nevermind c must be the gcf here so I guess I should take out of it that if an int. divides the gcf then it also divides a and b
     
  10. Mar 23, 2014 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    No; the theorem works perfectly well, but only if you do not mis-use it. Your example did NOT have d < a, and that is why it does not apply to your example. For example, if I divide 17 by 3 I have 17 = 3*5 + 2, with remainder 2 < 3. The theorem guarantees that if I write 17 = 3*q + r, with integers q,r ≥ 0 and r < 3, then I absolutely must have q = 5 and r = 2; no other two will work.
     
  11. Mar 23, 2014 #10
    Thanks, so like I said it only works in some cases. I guess it would be useful somewhere but it seems limited, this theorem.
     
  12. Mar 23, 2014 #11
    I honestly think it is just kind of confusing the fact it only works sometimes, but that is just me. Then again it worked fine in my example so I don't get why the restriction is there.
     
  13. Mar 23, 2014 #12
    I am still looking at this perplexed as if there is a hole in the theorem. I don't get the d<a in my example there still only exists one unique pair.
     
  14. Mar 23, 2014 #13
    LOL! Wow, we got each other confused!! Look at my example d is less than a.
     
  15. Mar 23, 2014 #14

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You need to use the quote button when you respond; otherwise there is no way to tell which message you are replying to. I cannot figure out who or what is confusing you.

    To avoid confusion, let's use a standard notation: we want the division ##n/d##, where ##n,d## are non-negative integers and ##d > 0##. (Here, I use 'n' for numerator and 'd' for denominator.) The theorem says there are two unique integers ##q \geq 0## (the quotient) and ##r \: (0 \leq r < d)## (the remainder) such that
    [tex] \frac{n}{d} = q + \frac{r}{d},\\
    \text{or }\\
    n = q d + r[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Division algorithm
  1. Division Algorithm (Replies: 3)

Loading...