 # 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 P1, P2, P3...Pn. Now take the product of all these prime numbers and increase by 1, you get A=P1xP2xP2…Pn+1. Dividing A by P1 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 P1, P2, P3...Pn 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