Do you remember the “long division” you once learned in grade school? Even though it seems now a rather quaint method to the microchip wielding man of today, long division is actually a very powerful procedure. It allows one to very efficiently determine the internal fractal structure of integers without introducing the cumbersome aspects of floating point arbitrary precision.
What we call Long Division is actually the Division Algorithm developed thousands of years ago in ancient Greece. The Division Algorithm is not really an algorithm as much as it is part of a theorem which assures the ability to divide integers and natural numbers known as Euclid’s Division Lemma.
But first, some basics. I will step you through the Division Algorithm.
Suppose you want to find out how many times a number “goes into” another number. For example, imagine that you have 128,654 grains of rice that you wish to distribute to 12 people. So then the question becomes, how many times can 12 be divided among 128,654.
In this case, we refer to 12 as the divisor, to 128,654 as the dividend and the number of times that 12 can be divided among 128,654 as the quotient. When the divisor can not be distributed equally to the dividend, the left over balance is referred to as the remainder.
Long Division (ie. the Euclid’s Division Algorithm) is a procedure that can be used to determine the quotient and remainder for a given divisor and dividend.
Here is how it works:
Arrange the divisor and dividend as shown below.
We address the dividend starting from its significant-most digit.
In other words, we start from the left side of the dividend and perform the long division procedure working from left to right.
We first ask ourselves whether 12 can be distributed evenly to 1.
When we realize it cannot and that 12 requires at least 12 in order to be distributed, we mark a zero in the quotient and we expand our consideration of the dividend one position to the right (which is 2). So now we are considering 12.
We now ask how many times can 12 be distributed to 12?
The answer is that 12 can be given to 12 exactly one time with nothing remaining. We express this by arranging our mathematical statement as shown below.
We then expand our consideration of the dividend out to the third digit (which is 8), asking how many times can 12 be distributed to 8? Since 8 is smaller then 12, 12 cannot be distributed among 8 and so we mark a zero in the quotient. Also, because we are considering the 8, we “bring it down” into the working area of the mathematical statement as shown below.
Since 12 cannot be distributed among 8, we expand our consideration of the dividend to include the fourth number (which is 6) by bringing it down into the working area of the mathematical statement. We then arrange our mathematical statement as shown below.
We now ask, how many times can 12 be distributed to 86?
The answer is that 12 can be given to 86 seven times with a remaining balance of 2. We express this by arranging our mathematical statement as shown below.
Next we ask how many times can 12 be distributed to 2?
Since 12 cannot be distributed among 2, we expand our consideration of the dividend to include the fifth number (which is 5) by bringing it down into the working area of the mathematical statement. We then arrange our mathematical statement as shown below.
Next we ask how many times can 12 be distributed to 25?
The answer is that 12 can be given to 25 two times with a remaining balance of 1. We express this by arranging our mathematical statement as shown below.
Next we ask how many times can 12 be distributed to 1?
Since 12 cannot be distributed among 1, we expand our consideration of the dividend to include the sixth number (which is 4) by bringing it down into the working area of the mathematical statement. We then arrange our mathematical statement as shown below.
Next we ask how many times can 12 be distributed to 14?
The answer is that 12 can be given to 14 one time with a remaining balance of 2. We express this by arranging our mathematical statement as shown below.
So now we have found out that if we have 128,654 grains of rice to distribute evenly to 12 people, each person would receive 10,721 grains of rice (our quotient) and that there would also be 2 grains of rice left over (our remainder).
If we wanted to be very precise, we would then determine how many portions to split the remaining 2 grains of rice up evenly amongst the 12.
Since we have run out of digits in our integer dividend, we now must add a decimal point and continue the long division procedure as shown below. Since we are free to add as many zeros to the right of the decimal point as we wish without changing the value, we can continue long division indefinitely. Therefore, it is said that we may continue producing numbers in the quotient to any arbitrary degree, a quality known as arbitrary precision.
So then, let’s continue.
Next we ask how many times can 12 be distributed to 20?
The answer is that 12 can be given to 20 one time with a remaining balance of 8. We express this by arranging our mathematical statement as shown below.
Since 12 cannot be given to 8, we add another zero and “drop it down” as shown below.
Next we ask how many times can 12 be distributed to 80?
The answer is that 12 can be given to 80 six times with a remaining balance of 8. We express this by arranging our mathematical statement as shown below.
With the remainder again being 8, we see that the solution will repeat 6 in the quotient forever.
Thus, the quotient for 128,654 / 12 = 10,721.1|6|
The above has been a particular example of long division. Now let’s consider the general procedure of long division.
Suppose we wish to divide an integer a by a positive integer d.
Let a = anan-1…a1a0 in decimal representation.
Since a has n+1 digits, the long division will have n+1 steps as each digit of the dividend generates exactly one step and gives exactly one digit of the quotient.
At step i, we do this:
Look for the largest integer qi so that d × qi does not exceed Bi, where Bi is defined as follows:
Bn = an and
Bi = 10(Bi+1 – d × qi+1) + ai, 0 ≤ i < n.
Write qi to the right of qi+1in the quotient row.
After we reach i = 0, what remains is r, the remainder.
Why does long division work?
In the long division procedure, the dividend must equal the sum of the remainder and all the numbers that have been subtracted.
But the numbers subracted are d×qi with place value 10i. So
a = (d × qn)10n +(d × qn-1)10n-1 + … + (d × q1)101 + (d × q0) + r, where 0 ≤ r < d
= d × (qn10n + qn-110n-1 + … + q1101 + q0) + r
= d × qnqn-1…q1q0 + r
= d × q + r, 0 ≤ r < d.
Here is where we need Euclid’s Lemma.
According to it, q and r must be unique. That is, the q we have found in the long division is indeed the one and only value possible, namely the quotient of a when divided by d.
Now that we know why long division works, it is easy to extend to dividends that are not integers.
Suppose a = 758.9 and d =5. Then a/5 = (1/10)(7589/5) so that we carry out the long division involving two integers and then divide the answer by 10 which is accomplished by moving the decimal point left.
Finally, noting that the Division Algorithm is valid in any base, we can extend these arguments to any base just as well as we can for base 10.
Below is an example of Euclid’s Division Algorithm in action.
Euclid's Division Algorithm in Animation
More about Euclid’s Division Lemma
The Division Lemma of Euclid assures us that each result obtained at every step of the Division Algorithm is absolutely the correct unique value for every possible dividend-divisor pair.
Here is how Euclid derived the Lemma:
For example, if you are given 13 and required to divide it among 4
Figure 15. - Euclid's Division Lemma, Step 1
Euclid thought about this in terms of 13 small spheres.
Figure 16. - Euclid's Division Lemma - Step 2
He then imagined the spheres being partitioned into 3 groups of 4 with 1 remaining ungrouped sphere left over.
Figure 17. - Euclid's Division Lemma - Step 3
Next Euclid arranged these spheres into the following mathematical relationships.
Figure 18. - Euclid's Division Lemma - Step 4
Then Euclid considered a wider set of data points.
In the examples included in figure 19 below, let’s refer to:
all of the dividends as ‘a‘
all of the divisors as ‘b‘
all of the quotients as ‘q‘
all of the remainders as ‘r‘
Figure 19. - Euclids Division Lemma - Step 5
Careful analysis begins to reveal that a pattern is emerging. We are getting unique combinations of quotients and remainders for any given pair of dividends and divisors. Furthermore, we see that in every case, remainder r is always greater then or equal to zero, but is always less then divisor b.
Figure 20. - Euclids Division Lemma - Step 6
Thus, Euclid’s Division Lemma may be stated as:
Given integers a, b with b > 0, there exist unique integers q, r
with 0 ≤ r < b such that a = bq + r.
To really be sure that the combinations are unique however, we need proof. So here it is:
Proof of Euclid’s Division Lemma is given as follows.
The proof consists of two parts — first, the proof of the existence of q and r, and second, the proof of the uniqueness of q and r.
Part 1: Existence of q and r
Consider the set:
We claim that S contains at least one non-negative integer. There are two cases to consider.
1) If a is non-negative, then choose n = 0.
2) If a is negative, then choose n = ab.
In both cases, a – nb is non-negative, and thus S always contains at least one non-negative integer. This means we can invoke the Well-Ordering Principle, and deduce that S contains a least non-negative integer r. By definition, r = a – nb for some n. Let q be this n. Then, by rearranging the equation, a = qb + r.
It only remains to show that 0 ≤ r < |b|. The first inequality holds because of the choice of r as a non-negative integer. To show the last (strict) inequality, suppose that r ≥ |b|. Since b ≠ 0, r > 0, and again b > 0 or b < 0.
If b > 0, then r ≥ b implies a-qb ≥ b. This implies that a-qb-b ≥0, further implying that a-(q+1)b ≥ 0. Therefore, a-(q+1)b is in S and, since a-(q+1)b=r-b with b>0 we know a-(q+1)b<r, contradicting the assumption that r was the least non-negative element of S.
If b < 0, then r ≥ -b implies that a-qb ≥ -b. This implies that a-qb+b ≥0, further implying that a-(q-1)b ≥ 0. Therefore, a-(q-1)b is in S and, since a-(q-1)b=r+b with b<0 we know a-(q-1)b<r, contradicting the assumption that r was the least non-negative element of S.
In either case, we have shown that r > 0 was not really the least non-negative integer in S, after all. This is a contradiction, and so we must have r < |b|. This completes the proof of the existence of q and r.
Part 2: Proof of the uniqueness of q and r
Suppose there exists q, q’ , r, r’ with 0 ≤ r, r’ < |b| such that a = bq + r and a = bq’ + r’ . Without loss of generality we may assume that q ≤ q’ .
Subtracting the two equations yields: b(q’ – q) = (r – r’ ).
If b > 0 then r’ ≤ r and r < b ≤ b + r’ , and so (r – r’ ) < b. Similarly, if b < 0 then r ≤ r’ and r’ < -b ≤ -b + r, and so -(r – r’ ) < -b. Combining these yields |r – r’ | < |b|.
The original equation implies that |b| divides |r – r’ |; therefore either |b| ≤ |r – r’ | or |r – r’ | = 0. Because we just established that |r – r’ | < |b|, by trichotomy we may conclude that the first possibility cannot hold. Thus, r = r’ .
Substituting this into the original two equations quickly yields bq = bq’ and, since we assumed b is not 0, it must be the case that q = q’ proving uniqueness.
–
The question then occurs to me. Is it possible to further generalize Euclid’s Division Lemma using Foundational Mathematics? Can we, when armed with the ordering clarity offered by The Foundational Mathematics, develop a method based on it to allow us, like a mathematical spider, to glide effortlessly and steadfast over the seemingly infinite labyrinthine web of numbers?
With this goal in mind, I have produced the following charts.
The first chart shows the unique euclidean lemma value matrix which I have generalized using Foundational Mathematics for ranges:
Dividend (a) = 1 for Divisors (b) = 0 through 9
Dividend (a) = 2 for Divisor (b) = 0 through 9
Dividend (a) = 3 for Divisor (b) = 0 through 9
Dividend (a) = 4 for Divisor (b) = 0 through 9
Dividend (a) = 5 for Divisor (b) = 0 through 9
Dividend (a) = 6 for Divisor (b) = 0 through 9
Dividend (a) = 7 for Divisor (b) = 0 through 9
Dividend (a) = 8 for Divisor (b) = 0 through 9
Dividend (a) = 9 for Divisor (b) = 0 through 9
Figure 21. - Petty Foundational Division Lemma for a equals 1 through 9
To see my work which led to these charts, review the follow document:
http://www.singularics.com/docs/petty-foundational-lemma-sequences_draft.pdf
Note that zero and nine are the Alpha and Omega. The end is the beginning. This is an expression of infinity.
9 is the intention of Mind to either constructively expand (multiply if the expansion in spatial) or to destructively contract (divide is the contraction is spatial).
3 and 6 are the force of Mind’s intention (extending thus from 9) exerted upon the conscious field as a vibratory pressure of light.
1, 2, 4, 8, 7 and 5 are the archetypal vibrations of form, shepherded through space and time, arranging themselves with respect to one another in accordance with the laws of polarized force and sacred geometry.
zero and nine are the alpha and the omega
Note also that every incrementing number that occurs where the spiral intersects with radials always compresses back to the radial’s initial value. For example, 546 is on the 6 radial because 5+4+6=15 and we then compress 15 as 1+5=6.
To develop a working understanding of this and other Foundational Mathematics concepts, please refer to my earlier writings:
http://www.alexpetty.com/2010/01/09/the-true-foundation-of-arithmetic/
Focus particularly on this rectangular table showing radial compression in base 10:
http://www.alexpetty.com/wp-content/uploads/2010/01/fae2016_small.png
You may also wish to review this circular version of the table:
http://www.alexpetty.com/wp-content/uploads/2010/01/fns-circle-chart-round-1×1.png
To see this principle at work in numerous other bases (indeed any arbitrary base), please review my earlier writing:
http://www.alexpetty.com/2010/08/23/the-effect-of-base-on-numeric-fields/
Can this characteristic of numbers help us more deeply understand what it means to divide?
Can we say that for any arbitrarily sized divisor, that “Foundational Radial Compression” assures that we can rely on the values listed in figure 21 for the general case?
.:.
n
t
m)
