# Numbers: Prime Numbers/
_{Reductio ad Absurdum}

A **prime number** is a natural number that can only be
divided by 1 and itself.
Also remember that 1 is not a prime number! Thus the first few prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

The following fact is the foundation of a lot of number theory---that
part of mathematics that investigates natural numbers, prime numbers, and divisibility:

**Theorem 5:** Every natural number is uniquely
the product of some prime numbers.

Really large numbers are very difficult and time consuming to factor.

**Theorem [Euclid]:** There are infinitely many prime
numbers.

**Proof: **
Again we use the
**"Reductuo Ad Absurdum"** method.
Assume there are only finitely many prime numbers
P_{1}, P_{2}, P_{3}...P_{n}.
Now take the product of all these prime numbers and
increase by 1, you get
A=P_{1}xP_{2}xP_{2}…P_{n}+1.
Dividing A by P_{1} leads to remainder 1, the same
for the other n prime numbers, thus none of the prime numbers divides A.
Since A must have a unique factorization into prime numbers,
the only remaining possibility is that A itself prime, which is
a contradiction to the assumption that
P_{1}, P_{2}, P_{3}...P_{n} are all
the prime numbers (note that A is larger than all these).
That means that the opposite of the assumption
must be true.

"Reductio ad absurdum, which Euclid loved so much,
is one of a mathematician's finest weapons.
It is a far finer gambit than any chess gambit: a chess player may offer
the sacrifice of a pawn or even a piece, but a mathematician offers the game."

**G.H. Hardy**

### Further Reading:

### Exercises

- a) Express the numbers 12, 15, 162, and 120 as product of prime factors.

b) Is the number 654321 prime?
- Is the number 123456789 prime? Describe the method you would use to attack the
problem if you had time enough, even if you don't.
- a) Are there three consecutive prime numbers?

b) How many multiples of the number 39 are prime? Why?
- Show that the five consecutive numbers 6·5·4·3·2+2,
6·5·4·3·2+3, 6·5·4·3·2+4,
6·5·4·3·2+5, 6·5·4·3·2+6
are all non-prime.

b) What are the smallest five consecutive non-prime numbers?
- Show that there are arbitrarily large stretches of consecutive
numbers all of them being non-prime.