What Comes Next: 1, 2, 4, 8, 16, … hint it’s not 32

A Kick in the Discovery

, , ,

Newbie at Number Theory (Part 1): The Division Algorithm

Published by

Valt

on

Today’s a very special day! We’re about to discuss some number theory! It’s important for anyone interested in mathematics to know the basics of number theory. Maybe not to the level of Fermat’s Last Theorem, but definitely enough to know Fermat’s Little Theorem (yes that’s the official name of the theorem).

There are two reasons to learn some number theory. The first is practical, there are a lot of situations where knowing modular arithmetic, some properties of relatively prime integers (numbers that share no factors), or some divisibility rules can come in handy.1 The second reason is for pure enjoyment (for a kick in the discovery one might say)! Number theory is wonderful and so much fun to learn and study! I hope to convey some of this in the next few blogs!

However, to begin we must begin at the beginning! So today, we cover something that is not the most interesting thing in the world, but we need this result to even consider modular arithmetic and therefore important!

We are going to learn about the division algorithm. It basically says you can take any two integers and divide them, DON’T DIVIDE BY ZERO THOUGH. More than that, your answer will be of the form: (Quotient) and (Remainder). In order to prove this statement, we look to well-ordering for help. If you have already read: Induction and Well-Ordering, then you are familiar with well-ordering. If not, go read that blog post first! Jk. Here’s a brief discussion that’s basically cut and pasted from there!

What are Natural Numbers? And why are they Well-ordered?

First, let’s agree on calling the set of counting numbers {1,2,3,4,…} the natural numbers and denote them by a fancy-looking N that’s almost like two N’s written on top of each other: \mathbb{N}. With that taken care of, what would happen if we took some non-empty subset of these numbers? For example, the even numbers {2,4,6,8,…}. Or, maybe {5, 120, 200}. Or, maybe just the number {10}.

Notice how all of the sets have a smallest number in them. The number 2 is the smallest even number, 5 is the smallest number in {5, 120, 200}, and 10 is the smallest number in {10}.

Challenge: Can you think of a non-empty subset of \mathbb{N} that does NOT have a smallest number?

I sure hope not, since the well-ordering principle says you can’t!

Well-Ordering: Every non-empty subset of number(s) from \mathbb{N} contains a smallest number. Simple.

Note that some people consider 0 a natual number. We won’t, but we will denote the natural numbers with zero by \mathbb{N}_0 . And, since \mathbb{N}_0 is basically the same as \mathbb{N} (with zero put into the set), well-ordering still applies to \mathbb{N}_0.

Well-Ordering (Second Version): Every non-empty subset of number(s) from \mathbb{N}_0 contains a smallest number. Simple again.

The Division Algorithm (Intuition)

Do you remember wayyyy back when you learned how to divide two numbers, and your teacher wanted you to write your answer with a remainder? It’s probably been a while since you’ve done this, so let’s do two examples.

If we divide 43 by 10 we should get,

\;43 \div 10 = 4\; R 3.

This is the same as writing,

\;43 = (4\times 10) + 3.

Where we call 4 the quotient and 3 the remainder.

Now let’s use 201 and 26.

\;201 \div 26 = 7\; R 19\;\; or \;\;201 = (7\times 26) + 19.

Basically, you can choose any two natural numbers n and m and then divide them. More than this, you can always find some quotient q and remainder r pair such that 0\leq r < m (if you are doing n\div m). Moreover, again, the quotient and remainder are unique (ie division problems have only one answer)!

Ok, that was a lot to take in. Let’s explain with our example using n = 43 and m=10.

Dividend = (Quotient)x(Divisor) + Remainder

\;\mathbf{43 = (4\times 10) + 3}

43 – Dividend – n

10 – Divisor – m

4 – Quotient – q

3 – Remainder – r

Observe that the remainder 3 is such that 0\leq 3<10 where 10 was our divisor. Also note that the quotient must be 4 and the remainder must be 3 (if it’s in the proper range). No other quotient/remainder pair would work.

Likewise, for 201 and 26, we found \;\underbrace{201}_{n} = (\underbrace{7}_{q}\times \underbrace{26}_{m}) + \underbrace{19}_{r}. With 0\leq 19<26 and no other quotient/remainder other than 7 R19 will work.

This is even true for negative integers! Consider n = -100 and m=12. Then,

\;-100 = (-9\times 12) + 8

Observe that we still have the remainder r=8 that’s positive and less than our divisor 12. Note, if our divisor m is negative, we would want our remainder to be in the range 0\leq r <|m|.

If we can prove that we can divide two positive integers it makes sense that we could generalize to all integers. Thus, we aim to prove the division algorithm for positive integers. Spoiler Alert the proof relies on the well-ordering principle.

The Division Algorithm (Proof)

Ok, let’s state what we aim to show so there is no confusion:

The Division Algorithm: For all natural numbers n and m there exists two unique natural numbers q and r such that,

n = mq + r\; ,\qquad \mathrm{where}\;0\leq r < m .

Where q is called the quotient and r is called the remainder.

How do we prove this? Well, the only tool mentioned, so far, is the well-ordering principle. For this reason, we want to focus on subsets of natural numbers. Let’s rearrange n = mq + r in a way so that we only have to focus on natural numbers or zero, (ie numbers larger than or equal to 0). Since r\geq 0 maybe we should focus on the remainder.2

Proof: (Click in the Discovery)

Let n and m be natural numbers. We break up our proof into two parts: (1) showing q and r exist with the desired properties, and (2) showing q and r are unique. Most of our work will be in step (1).

(1). Existence of q and r

Since we want r\geq 0 let’s consider the set of numbers that we might get as remainders by varying q in n = mq + r :

S = \Big\{ (n-mt) \;\Big|\; n - mt \geq 0 \;\mathrm{and}\;t \;\mathrm{is}\;\mathrm{in}\;\mathbb{N}\;\mathrm{or}\;t=0 \Big\}.

To simplify life, recall \mathbb{N}_0 =\{0,1,2,3,\cdots\} is the set of natural numbers including zero. Thus, our set S is,

S = \Big\{ (n-mt) \;\;\Big|\;\; n - mt \geq 0 \;\mathrm{and}\;t \;\mathrm{is}\;\mathrm{in}\;\mathbb{N}_0 \Big\}.

Since we are considering only when n-mt \geq 0, all the numbers in S are in \mathbb{N}_0. Therefore, S is a subset of \mathbb{N}_0.

For example, with n=43 and m = 10 our set S is,

S = \Big\{\underbrace{43-10(0)}_{t=0}\;,\;\underbrace{43-10(1)}_{t=1}\;,\;\underbrace{43-10(2)}_{t=2}\;,\;\underbrace{43-10(3)}_{t=3}\;,\;\underbrace{43-10(4)}_{t=4}\Big\}\\\;\;\;\;=\Big\{43,\;33,\;23,\;13,\;3\Big\}\\\;\;\;\;=\Big\{3,\;13,\;23,\;33,\;43\Big\}.

Notice how the smallest number in S is the remainder in \;43 = (4\times 10) + 3. Maybe this always happens! Indeed it does! This is our aim of attack! By well-ordering (second version) we can guarantee that there is a smallest number in S and it just so happens that this number is the remainder r we want!

Recall, when using well-ordering, S must be non-empty and a subset of \mathbb{N}_0 . Since we already know that S is a subset of \mathbb{N}_0, all we need to show S must be non-empty by showing there is always at least one number in S. Consider when t=0 . Then n -m(0) = n >0 since n is from \mathbb{N} = \{1,2,3,\cdots\}. Therefore, we now know n is always in S, so the set S is not empty.

We now can use the well-ordering principle (second version) to conclude there is a smallest number in S. Let’s denote this minimum element by something memorable… maybe by the letter r. So, for some choice of t we have n - mt = r in S. Because we are labeling this minimum number in S the letter r let’s also label the choice of t that gives r by the letter q.

We now have: n - mq = r where r is the smallest number in S.

We’re almost there, we’re missing that 0\leq r < m.

Recap, we have constructed the set S to be a subset of numbers from \mathbb{N}_0 = \{0,1,2,3,\cdots\} and have shown that S is not empty (since n is always in S). Therefore, we concluded by well-ordering that there is a smallest number in S and we denoted it r. So for some t=q \in \mathbb{N}_0 we have n-mq = r .

We claim that our choice of labeling the smallest number in S by r was a good thing. The reason is that, as we will prove, 0\leq r < m.

Side Note: Recall the remainder we want must be in the interval, 0\leq r < m . To show that this is the case we will use what’s called a proof by contradiction. We will assume the opposite is true (that r \geq m ) and show this leads to something nonsensical.

Game plan: if r was not in the range 0\leq r < m so that r\geq m. This would mean r is not the remainder we wanted. We will then us this to find some other r'<r in S. This then contradicts that r was supposed to be the smallest number in S.

To this end, let r\geq m and consider what happens if we changed q to q+1 in the expression n - mq=r . Let, r' =r- m\geq0 and we deduce:

n - m(q+1) = \underbrace{n - mq}_{=r} - m = r -m = r'>0.

Since n - m(q+1) =r'>0 is the expression n - mt with t=q+1, it must be that r' is in the set S. But then r isn’t the smallest number in S anymore because 0\leq r'< r. This can’t happen since we chose r to be the smallest number in S. Thus, it must be that 0\leq r < m just like we wanted.

(2) Uniqueness of q and r

Our game plan is to assume there are two different quotient and remainder pairs and show something nonsensical, i.e. a proof by contradiction!

Thus, assume there are numbers q_1,r_1,q_2,r_2 such that,

n = mq_1 + r_1 = mq_2 + r_2

with 0\leq r_1<m and 0\leq r_2<m . Since we are thinking of r_1,r_2 as different numbers let’s choose to label them so that way r_1< r_2 . With some rearranging we see,

m(q_1-q_2)= r_2 - r_1.

Recall that both r_1<r_2<m so that 0\leq r_2 - r_1<m . But q_1 - q_2 is at least 1 (if q_1 - q_2\leq 0 then r_1\geq r_2 a contradiction, and therefore q_1 - q_2\geq 1 ) so we have,

m = m(1) \leq m(q_1-q_2) = r_2 - r_1 < m.

So that m< m is another contradiction! Thus, q_1 = q_2 \;\mathrm{and}\;r_1=r_2 . Concluding the proof.

\square

And just like that, we can divide any two natural numbers n and m.

Closing Remarks.

Consider how important the well-ordering principle is in the proof. Remember, it was used to show that there was a smallest number in our set S which was the remainder we wanted. Well ordering, thank you again for coming in clutch! Or, if you prefer induction then thank you induction (since they are equivalent)!

I know that many of you reading this are thinking, “Why did we have to go through so much work to prove something so obvious?” To that I say, I agree! This seems to be a lot of work for very little pay off.

But there is a reason.

At some point we will start to ask certain questions that end up being answered more easily by using functions or complex numbers instead of integers (just take my word for a moment). When we get to this point we will be confronted with the question, is there an analogous division algorithm for polynomials and complex numbers? If you remember polynomial or synthetic division, you might say `yes there is a division algorithm for polynomials”. You’d be correct! But what about complex numbers: n =a + ib and m =c + id where a,b,c,d are all integers and i=\sqrt{-1}. Can you divide n and m to find some q and r? The answer is a little less obvious huh? If I gave you two specific complex numbers you might find a way to divide them, but could you guarantee that no matter which two complex numbers I gave you, you’d be able to find a way?

I’ll let you ponder if there is a division algorithm for complex numbers, I’ve left enough breadcrumbs that with some time (ok a lot of time) you might be able to convince yourself of the answer. However, you might find it hard to prove your answer.

Any who, back to getting on my soap box.

The crux of the matter is this, by proving the obvious we can develop tools and intuition for the less obvious. The tools we use and the intuition we gain are what we care about here, not necessarily the result since you probably knew how to divide before you read this article anyway.

Lastly, division algorithms show up in many places and in many forms that don’t seem like division. One of these forms is called modular arithmetic. Don’t worry if you are unfamiliar with modular arithmetic, we will cover it soon, but for those who already know modular arithmetic, saying 23 is congruent to 2 (mod 3) is the same thing as saying that 23 has a remainder of 2 when divided by 3.

Remainders are important huh!

Footnote:

  1. For a concrete example, the standard proof for the irrationality of \sqrt{2} uses Euclid’s Lemma, which deals with divisibility. Or, if you know a little group theory one can show that \mathbb{Z}_{nm} \cong \mathbb{Z}_n \times \mathbb{Z}_m if and only if \gcd{(n,m)} = 1. And to understand the proof it helps to know about relatively prime numbers. ↩︎
  2. We will be using some set notation in the following proof and since this is the first part of our number theory journey together, here are the fundamentals:
    (i) A set is a collection of elements, in our case numbers, and is denoted by curly brackets. For example, \{1,2,3\} and \{10,209,314, \cdots\}.
    (ii) When we want to say that a number is in a set, we will denote this by the Greek letter epsilon \in which means ‘is an element of’ or ‘is in the set’. Thus,
    1\in\{1,2,3\} translates to 1 is in the set \{1,2,3\} but since 5 isn’t in this set we would write 5\notin\{1,2,3\} which translates to 5 is not in the set \{1,2,3\}.
    (iii) If our set is described by a rule, we have a more efficient way to denote this set than just listing its elements. For example, the set of all even numbers could be written as \{2,4,6\cdots\} which is fine for a rule that is this easy to communicate. However, when the rule gets more complicated, we want a more efficient way to write it. What we will do is write any of the following,
    \{2,4,6\cdots\} = \{n \;|\;n=2k \;\mathrm{and}\;k\in \mathbb{N} \}=\{n \;:\;n=2k \;\mathrm{and}\;k\in \mathbb{N} \}.
    We would read the above set as the set of numbers n such that n is equal to 2k where k is in the set of natural numbers. Or the set consisting of numbers n where n=2k and k is a natural number. More often than not, you can read the colon : or the vertical line | in the set as the words such that.
    For one final example, consider the set \{2n+1 \;|\;n\in \mathbb{N}\;\mathrm{and}\;n>10 \}.
    is the set of numbers 2n+1 where n is a natural number greater than 10. To find some of it’s elements we simply plug in some values for n from \mathbb{N} that are larger than 10. The first few numbers in this set are,
    \{2n+1 \;|\;n\in \mathbb{N} \;\mathrm{and}\;n>10 \}= \{23, 25, 27, 29, \cdots\}. ↩︎

2 responses to “Newbie at Number Theory (Part 1): The Division Algorithm”

  1. Newbie Number Theory (Part Two): The Euclidean Algorithm – A Kick in the Discovery Avatar
    Newbie Number Theory (Part Two): The Euclidean Algorithm – A Kick in the Discovery

    […] into number theory. For those who haven’t read part one about the division algorithm click here, because we plan to use it! We talk everything Euclidiean, except for Euclidean geometry! We will […]

    Like

    Reply
  2. Newbie Number Theory (Part 5): Modular Arithmetic – A Kick in the Discovery Avatar
    Newbie Number Theory (Part 5): Modular Arithmetic – A Kick in the Discovery

    […] 3 when divided by 10. Similarly, 45 has a remainder of 5 when divided by 10. And if you recall The Division Algorithm from Newbie Number Theory (Part 1) you know that we can always find a […]

    Like

    Reply

Leave a reply to Newbie Number Theory (Part 5): Modular Arithmetic – A Kick in the Discovery Cancel reply