Number Theory: Long Division Works.

4 min readJun 9, 2019

I am sure we are all familiar with good ol’ long division with remainder from primary school. And now we return to this concept that we took for granted and prove that it is actually a valid way of doing things.

Example: Calculate 35 ➗6 with the remainder.

Sol: To solve this we pick the largest number such that when we multiply by 6 the remainder is less than 6 but greater then 0.

Thus we choose our quotient, q = 5.

6(5) = 30.

35- 6(5) = 5.

Thus the remainder is 5.

Moving around the equation we get that 35 = 6(5) + 5.

Why can’t we choose q = 4 though? Technically speaking you get a remainder. What’s wrong with a remainder that is greater than or equal to 6?

Well let’s see what happens when we choose our quotient to be 4.

35 = 6(4) + 11. Now we have q = 4, r = 11, where r = remainder.

However, we can just rewrite the equation in the following manner.

35 = 6(4) + 11= 6(4) + (6 + 5) = 6(4) + 6 + 5 = 6(4) + 6(1) + 5 = 6(4+1) + 5 = 6(5) + 5

Thus they are the same thing. But usually when were are dividing we are trying to see how much of the divisor (6) fits into a dividend (35).

The above manipulation suggests a general way to express division where we have a remainder we will call it ‘r’ from now on, such that 0 ≤r < divisor.

We we also call the divisor ‘b’ from now own. So the condition becomes 0≤r<b. Notice that the equality is strict. Because if r ≥b then we can always perform the above regrouping operation.

Thus we finally get our first theorem.

Ex: a = 35, b = 6. Then q = 5, r =5 as we saw earlier.

Before we prove this recall the floor operator. ⌊ x⌋ = rounds_down(x)

Ex: ⌊ 5.0122⌋ =5

Ex: ⌊ 5.9999⌋ =5

Ex: ⌊ 5⌋ =5

What is the minimum and maximum of the following function?

Let’s just test some values out.

f(5.0122)= 5.0122 — ⌊ 5.0122⌋ = 0.0122

f(5.9999)= 5.9999 ➖⌊5.9999⌋= 0.9999

f(5) = 5 -⌊ 5⌋ = 0.

Basically the function just expresses the remainder or everything to the right of the decimal. Notice that it can become as large as possible so long as it’s less than 1. Thus the maximum < 1.

For the minimum of the function we can make the function as small as possible by minimizing the value of the right hand side of the decimal. But, what is the smallest value for the right hand side of the decimal point. It’s when we have all 0’s. Thus the minimum of this function is 0.

Thus we have that 0 ≤ x ➖⌊ x⌋ < 1 for any x.

Lemma : 0 ≤ x -⌊ x⌋ < 1 for any x that is a real number.

Pf: Just proved it above.

Now we are going to use this useful fact to show existence of the integers ‘q’ and ‘r’.

Existence Proof of Thm 0.1

There are multiple ways of proving this. The way I am going to do it does not require knowledge of discrete mathematics but do realize this is probably not the standard way you will see it proved in many textbooks or on proof wiki.