Proof for operations algorithms

[C0nfused]

Hi everybody,
I would like to find proofs for the algorithms that we use to calculate sums,products,quotients... For example I would like to see how the long division algorithm is proved. Do you know any sites that have such proofs? Any help would be appreciated
Thanks

 

[Galileo]

Hmm, try here:
http://www.cut-the-knot.org/blue/Euclid.shtml

 

[C0nfused]

Thanks for your answer, but i didn't actually find any answer to my question

 

[matt grime]

Work it out for yourself - the long division on is very easy, the others even easier and all rely, essentially, on the distributive nature of arithmetical operations - there really is nothing to "prove".

 

[arildno]

It can be relevant to remember that what we call a "division" algorithm, is a way to rewrite a
fraction a/b into its equivalent decimal representation.

On way of doing this, is by "guessing" the coefficients $$c_{n}$$ in the problem:
$$a=b*\sum_{i=-\infty}^{M}c_{i}10^{i}$$
Be observant of how the different steps in this guessing procedure occurs in a systematic manner in the ordinary algorithm.

 

[C0nfused]

Thanks for your answer. I think ,as matt grime mentioned, they are mostly based on the distributive property. I will also check your method arildno

 

[john_gabriel]

Division Theorem and Proof of Long Division Algorithm

This theorem was discovered for division involving integers in the form a/b where a is greater than b. The cases where a = b or a < b are uninteresting.

Many do not understand this simple theorem and it can be seen masquerading as the division algorithm in almost every learning institute. In truth, this has nothing to do with radix systems, nor does it define long division.

I am going to illustrate why the long division algorithm works for the number abc/d where a,b,c and d are single digit integers and d is not zero. Assume that abc is represented in base 10.

abc/d = (10ab + c)/d = 10ab/d + c/d


Now let ab/d = q + r/d so that 10(ab/d) = 10(q+r/d)
where r is a remainder. Note that q and r will always be single digits.

Then we have:
abc/d = 10(q + r/d) + c/d
= 10q + 10r/d + c/d

but 10r/d+ c/d = rc/d (since both r and c are single digits)

So abc/d = 10q + rc/d

This explains why we use the remainder of division as the significant digit for the next quotient in our long division process. For example, 120/8: 12 divided by 8 is 1 remainder 4. Then 40/8 = 5.

Now let rc/d = k + t/d where t is a remainder. Note that k will always be a single digit.

To see how this works, try 120/8 by substituting a=1 b =2 c=0 and d=8.

120/8 = (10(12) + 0)/8 = 10(12)/8 + 0/8

but 12/8 = 1 + 4/8 => 10(12/8) = 10(1+4/8)

120/8 = 10(1+4/8) + 0/8
= 10 + 40/8 + 0/8

but 40/8 + 0/8 = 40/8

So 120/8 = 10 + 40/8 = 10 + 5 = 15

Now back to the division theorem. What does it say exactly?

Given a/b, we can find unique integers q and r such that a = bq + r where r is the remainder of division. It is redundant to state that r < b but greater than or equal to 0. Since r is a remainder of the quotient a/b, it follows that it must be less than b.

Similar logic is used in defining an alogorithm for division of abcd/ef or other quotients.

 

[john_gabriel]

Long Division Algorithm

The following is a revision of the previous post:

This theorem was discovered for division involving integers in the form a/b where a is greater than b. The cases where a = b or a < b are uninteresting.

Many do not understand this simple theorem and it can be seen masquerading as the division algorithm in almost every learning institute. In truth, this does not rely only on the properties of radix systems, nor does it define long division.

I am going to illustrate why the long division algorithm works for the number abc/d where a,b,c and d are single digit integers and d is not zero. Assume that abc is represented in base 10.

abc/d = (10ab + c)/d = 10ab/d + c/d

Now let ab/d = q + r/d so that 10(ab/d) = 10(q+r/d)
where r is a remainder.

Then we have:
abc/d = 10(q + r/d) + c/d
= 10q + 10r/d + c/d

but 10r/d+ c/d = rc/d

since r is shifted left through multiplication by 10

So abc/d = 10q + rc/d

This explains why we use the remainder of division as the significant digit for the next quotient in our long division process. For example, 120/8: 12 divided by 8 is 1 remainder 4. Then 40/8 = 5.

Now let rc/d = k + t/d where t is a remainder. Note that k will always be a single digit.

To see how this works, try 120/8 by substituting a=1 b =2 c=0 and d=8.

120/8 = (10(12) + 0)/8 = 10(12)/8 + 0/8

but 12/8 = 1 + 4/8 => 10(12/8) = 10(1+4/8)

120/8 = 10(1+4/8) + 0/8
= 10 + 40/8 + 0/8

but 40/8 + 0/8 = 40/8

So 120/8 = 10 + 40/8 = 10 + 5 = 15

Now back to the division theorem. What does it say exactly?

Given a/b, we can find unique integers q and r such that a = bq + r where r is the remainder of division. It is redundant to state that r < b but greater than or equal to 0. Since r is a remainder of the quotient a/b, it follows that it must be less than b.

Similar logic is used in defining an alogorithm for division of abcd/ef or other quotients. The basic idea is to remember that when the product of the remainder by a multiple of 10 is added to the remaining digits, the multiple of 10 disappears, e.g.

10a + c = ac
10ab + c = abc
100a + c = a0c
100ab + c = ab0c

This is the reason why we simply prefix the remaining quotient digits by the remainder and repeat the process. This is the essence of the long division algorithm. The algorithm is altered slightly in the following examples:

12564/20 and 12564/11

In the first example, we start with 100abc and in the second example, we start with 1000ab, since 125 > 20 and 12 > 11. Thus, it can be seen that the algorithm changes slightly but the basic idea is the same.