"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

- if B/A is natural, or equivalently
- if B/A has no remainder, or equivalently
- if there is a natural number C such that C·A=B.

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.

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.

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.

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

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.

** 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 b_{1}, rename r as a_{1},
and divide b_{1} by a_{1}
to get another remainder r_{1}.
We continue until eventually we must
(since r > r_{1} > r_{2} ...)
obtain a remainder
r_{m}=0 (when dividing b_{m} by a_{m}).
The last nonempty remainder r_{m-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?

Is the square of an even number always even?
Note that is not sufficient to present a list of examples like 2^{2}=4,
6^{2}=36, 18^{2}=364, 102^{2}=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.

**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 n^{2}=(2·m)^{2}=4·m^{2}=
2·(2·m). Since 2·m is again a natural number, this means that 2 is a divisor
of n^{2}, therefore n^{2} 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 1^{2}=1, 3^{2}=9,
5^{2}=25, 7^{2}=49, 11^{2}=121,
it seems that the square of an odd number must also be odd.
Isn't it true that if n^{2}=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:

**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)?

**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 n^{2}=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 n^{2} is odd.

Here is another theorem with proof:

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:

**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.**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.**Conjecture:**The statement that seems to be true, looking at the data, has to be formulated. Without a proof, it is still a conjecture.**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.

- .............

- a) Find GCD(437,621).

b) Find LCM(359,2349).

c) Find GCD(2007,1548). - 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. - Assume GCD (42,n) = 14, LCM(42,n) = 420. Find n.
- 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?
- 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?
- You want to build a square using many rectangles of dimensions 6 cm × 15 cm each. How many of these rectangles are needed?
- 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?