Numbers: Natural Numbers/ Algorithms and Proof


"If numbers aren't beautiful, I don't know what is."
Paul Erdös

When people are asked what mathematicians do, the usual answer is that "they work with numbers". Although mathematicians nowadays feel slightly insulted by this answer, and many would deny they ever touch something so mundane as numbers, there is still a certain amount of truth in this answer. Historically mathematics begins with numbers and shapes---geometry, and investigating numbers and shapes is what mathematicians did over centuries.

To be more presise, early cultures usually don't know decimal numbers, not even fractions, but start with natural numbers. These are the numbers 1, 2, 3, 4, ... . Of course, when you start counting you need them. Some say the number 0 would also belong to the natural numbers, but historically the "0" comes much later, only about 600BC arabian mathematicians introduced it. That's also reasonable: If you have no cow, then you don't need a number to express that sad fact. And the negative numbers are also not natural.

For practical purposes, addition and multiplication were soon invented. If you have 34 sheep on the North meadow and 51 on the South meadow, how many do you have together? Or if each of your ship requires 17 sailors, and you have 7 ships, how many sailors do you need. The same with subtraction, although there were suddenly questions without an answer, like the famous: "You see three men enter a house. After that, five leave the house. How many are in the house?" If you have 36 cows and give your neighbor 13 cows, you have 24 of them, but what if you would give your neighbor 50 cows? The same with division. You can divided your 36 cows evenly on your three children, but not your 85 sheep. Of course, this is where fractions are required, and they emerged here as well, but still mathematicians began to investigate why certain numbers can be divided by some numbers. Maybe mathematics began to loose the total connection with practical purposes at that point, and something as impractical as prime numbers resulted. Or can prime numbers be applied somewhere?


This concept, as well as the concept of prime numbers, only applies to natural numbers. We say that a natural number A divides a natural number B

We also say that A is a divisor of B, and B can be divided by A, or B is a multiple of A. For example, 2 divides 4 but 2 does not divide 5.

Since every divisor of a number is less or equal than the number, every number n can only have at most n divisors. For instance, the divisors of 15 are 1, 3, 5, and 15. The divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24. Every number n (except 1, where both coincide) has at least two divisors---1 and n. Numbers with only two divisors are called prime numbers and investigated later.

Group Activity:So every natural number n has at least 2 and at most n divisors. Are there numbers with exactly 3 divisors? Are there numbers n with n/2 divisors? How many of them are there? Try to answer these and similar questions. Use the technique of looking on small cases. Write down the numbers from 1 to 20 and for each of these numbers the number of divisors. This is your data set. Then find the numbers in your data obeying the properties in question. If you find some, try to find out what properties these numbers have.

Different from divisors, every natural number has infinitely many multiples. These multiples of n are exactly n, 2·n, 3·n, 4·n, ... .

A number is a common divisor of two other numbers if it is a divisor of both. In the same way, a number is a common multiple of two numbers if it is a multiple of both. For instance, 6 is a common divisor of 36 and 60. 12 a another common divisor of 36 and 60. The numbers 10, 100, 1000, 10000, ... are all common multiples of 2 and 5.

Since every number has only finitely many divisors, two given numbers a and b also have only finitely many common divisors. Therefore there is a smallest and a largest among them. The largest one is especially interesting and is called the greatest common divisor of a and b and written as GCD(a,b). For instance, GCD(36,60)=12, since the common divisors of 36 and 60 are the numbers 1, 2, 3, 6, 12.

Multiples behave a little different. We have infinitely many common multiples, thus there is no largest one of them. But since all these common multiples are natural numbers, there still must be a smallest one of them, a least common multiple, denoted by LCM. Take LCM(6,9)=18 as example.

Group Activity:Is there some relation between these concepts? Take two numbers (let's say less than 100, to keep things doable) and find all divisors and multiples of a, all divisors and multiples of b, all common divisors and all common multiples of a and b, and also GCD(a,b) and LCM(a,b). Make a four column table with a, b, GCD(a,b), LCD(a,b). What do you observe? Maybe someone observes something when we collect data from different groups?

Theorem: For every two natural numbers n and m, GCD(n,m)·LCM(n,m)=n·m.

Euclid's Algorithm

Group Activity:Try to find GCD(275352,8712). If that was to easy try to find GCD(1689352,1170915).

You may have observed that the GCD of two numbers can be found if you can factor both numbers into prime numbers, but this factorization itself is less than easy for large numbers. Still we may want to be able to find the GCD of two arbitrary numbers fast. The question is how? This problem was resolved by the famous Greek mathematician Euclid. He gave a procedure, a method, how to find the GCD of any two numbers in reasonable time.

Example: Replace the values in the a and b fields by your values (Note b>a). Press the "division" button to get the remainder r. Press the "Replace" button to replace b by a and a by r. Press these division and replace buttons until you get a remainder of 0.
b:   a:      
bi:   ai:   ri:       GCD:

Euclid's Algorithm (procedure) for computing the GCD.
The input are two natural numbers a < b. We divide b by a and get a remainder r. If this remainder is not equal to 0, we rename a as b1, rename r as a1, and divide b1 by a1 to get another remainder r1. We continue until eventually we must (since r > r1 > r2 ...) obtain a remainder rm=0 (when dividing bm by am). The last nonempty remainder rm-1 is the GCD of a and b.

There is also a version of this algorithm to find common units of two straight lines. We check how often the shorter one fits into the larger one. Then we proceed with the remaining part (remainder) and the former shorter line, and so on. Different from above, the process doesn't have to terminate and could in principle go on forever (if there is no common unit length contained in both lengths).

By the way, how would we find the LCM of two numbers quickly?

What is a proof?

Is the square of an even number always even? Note that is not sufficient to present a list of examples like 22=4, 62=36, 182=364, 1022=10404. It could be true in most cases, with a few unknown exceptions.

Why would we even care? If somebody faces an even number and wants to know whether ist square is even or not, why should he or she not just square it and look at the result? Well, with the theorem known to be true, the square does not have to be computed, we would know that the square is even even before. More important, theorems are building blocks of other theorems. We will later see that we need this fact, that the square of all even numbers are even and the squares of all odd numbers odd, in the proof of the Theorem that the square root of 2 is not rational. In the proof, we don't look at concrete numbers but rather on variables which could be any numbers. Therefore we need the validity of our theorem also for any, for arbitrary numbers.

Theorem 1: The square of every even number is even.

Proof:Let n be an even natural number. Remember that this means that there is another natural number m such that 2·m=n. Then n2=(2·m)2=4·m2= 2·(2·m). Since 2·m is again a natural number, this means that 2 is a divisor of n2, therefore n2 is again even.

Note how the proof didn't deal with concrete numbers. Rather the variable n was introduced, with arbitrary but even value. A statement like "The square of 14256 is even", although true, is not considered to be a general mathematical theorem. It lacks the generality. Mathematical theorems usually make statements about infinitely many numbers or mathematical objects.

Next we wonder about squares of odd numbers. First we would get data, meaning square some small odd numbers to get some idea. Obviously, since 12=1, 32=9, 52=25, 72=49, 112=121, it seems that the square of an odd number must also be odd. Isn't it true that if n2=n· is even, then n also has to be even? Or isn't it even true that a product can only be even if one of the factors is even? Yes, it is, and maybe we proof this fact first, since we would need it as building block of the odd squares theorem:

Theorem 2: If a product of natural numbers n·m is even, then n or m (or both must be even as well.

Proof:... ...

Class Activity: We can rephrase Theorem 2 as follows: If n divides the product n·m, then 2 divides n or m (or both). Can this be generalized? Is it true for all natural numbers k, n, and m that if k divides the product n·m, then it must also divide either n or m (or both)?

Theorem 3: The square of every odd number is odd.

Proof:Using Theorem 2, the proof is rather easy. The method of proof is called "Reductuo Ad Absurdum", you assume the opposite of what you want to prove correct and show that this assumption logically leads to something obviously wrong.
Let n be an odd number, and assume its square n2=n·n is not odd, meaning, it is even. By Theorem 2, then n or n is even. But n cannot be even and odd at the same time, we have a contradiction. That means that the opposite of the assumption must be true, therefore n2 is odd.

Here is another theorem with proof:

Theorem 4: The sum of two even natural numbers is always even.
Assume we have any two even numbers n and m. By definition, there must be other natural numbers a and b such that n=2·a and m=2·b. But then n+m = 2·a+2·b = 2(a+b). As a sum of natural numbers, a+b is also natural, thus n+m is divisible by 2.

How are Theorems obtained? This is the most frequent way:

  1. Experiments: What we first need is data. Therefore, even though we want to get statements about all (infinitely many) numbers (or more general, about infinitely many mathematical objects), we have to look at few, concrete examples first. Usually these are small numbers (or objects), since large ones are too difficult to handle.
  2. Finding Pattern in Data: This is sometimes harder than it sounds now. You have some data but don't even know what to look for. Suddenly seeing a pattern is an act requiring creativity.
  3. Conjecture: The statement that seems to be true, looking at the data, has to be formulated. Without a proof, it is still a conjecture.
  4. Proof: After a formal proof has been done, and is checked by other mathematicians, the statement is "true" and can from then on be build as base for other theorems.

The first proof

Hippocrates of Chios (not that Hippocrates) gave the first deductive proof. It is about the area of a moon-shaped shape.

Further Reading:


  1. a) Find GCD(437,621).
    b) Find LCM(359,2349).
    c) Find GCD(2007,1548).
  2. a) What is GCD(67,161)?
    b) What is GCD(5n+2,12n+5), for arbitrary natural n? If you heve problems doing it, get data first. Do it for n=13, n=14, n=15, n=16, ... until you get an idea.
  3. Assume GCD (42,n) = 14, LCM(42,n) = 420. Find n.
  4. A rectangular field of dimensions 18 × 24 meters should be divided into squares (all of them of the same siize). How many squares do you need?
  5. A rectangular field of dimensions 18 × 24 meters should be divided into squares, but now different sizes are possible. How many squares do you need?
  6. You want to build a square using many rectangles of dimensions 6 cm × 15 cm each. How many of these rectangles are needed?
  7. Is the following true: If a natural number k divides the product n·m, then it must also divide either n or m (or both). If its is not true in general, for which k is it true?