# Homework Help: Division algorithm

1. Mar 23, 2014

### chimath35

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. Mar 23, 2014

### Ray Vickson

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.

3. Mar 23, 2014

### chimath35

I don't get it. I divided 15 by 4; so this theorem doesn't work for all numbers?

4. Mar 23, 2014

### rikblok

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.

5. Mar 23, 2014

### chimath35

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......

6. Mar 23, 2014

### rikblok

Yup, that's how I read it.

7. Mar 23, 2014

### chimath35

Last edited: Mar 23, 2014
8. Mar 23, 2014

### chimath35

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

9. Mar 23, 2014

### Ray Vickson

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.

10. Mar 23, 2014

### chimath35

Thanks, so like I said it only works in some cases. I guess it would be useful somewhere but it seems limited, this theorem.

11. Mar 23, 2014

### chimath35

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.

12. Mar 23, 2014

### chimath35

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.

13. Mar 23, 2014

### chimath35

LOL! Wow, we got each other confused!! Look at my example d is less than a.

14. Mar 23, 2014

### Ray Vickson

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
$$\frac{n}{d} = q + \frac{r}{d},\\ \text{or }\\ n = q d + r$$