Division Algorithm: Understand Unique c & d

[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?

 

[Ray Vickson]

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?

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.

 

[chimath35]

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

 

[rikblok]

...or maybe I don't know what unique means?

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.

 

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

 

[rikblok]

Yup, that's how I read it.

 

[chimath35]

end thread

 

[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

 

[Ray Vickson]

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

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.

 

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

 

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

 

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

 

[chimath35]

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

 

[Ray Vickson]

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

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