Long Division and Euclid’s Lemma

Do you remember the “long division” you once learned in grade school? Long division allows one to efficiently determine the internal structure of integers with arbitrary precision without introducing the cumbersome aspects of floating point decimals.

What we call Long Division is actually the Division Algorithm developed thousands of years ago in ancient Greece. The Division Algorithm is part of a theorem which assures the ability to divide integers and natural numbers known as Euclid’s Division Lemma.

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 than 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 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 = a_na_n-1…a₁a₀ 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 q_i so that d × q_i does not exceed B_i, where B_iis defined as follows:

B_n = a_n and

B_i = 10(B_i+1 – d × q_i+1) + a_i, 0 ≤ i < n.

Write q_i to the right of q_i+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×q_i with place value 10ⁱ. So

a = (d × q_n)10ⁿ +(d × q_n-1)10^n-1 + … + (d × q₁)10¹ + (d × q₀) + r, where 0 ≤ r < d

= d × (q_n10ⁿ + q_n-110^n-1 + … + q₁10¹ + q₀) + r

= d × q_nq_n-1…q₁q₀ + 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.

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

Euclid thought about this in terms of 13 small spheres.

He then imagined the spheres being partitioned into 3 groups of 4 with 1 remaining ungrouped sphere left over.

Next Euclid arranged these spheres into the following mathematical relationships.

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‘

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.

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

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

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.

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?

.:.