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=P1xP2xP2Pn+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

Further Reading:

Exercises

  1. a) Express the numbers 12, 15, 162, and 120 as product of prime factors.
    b) Is the number 654321 prime?
  2. 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.
  3. a) Are there three consecutive prime numbers?
    b) How many multiples of the number 39 are prime? Why?
  4. 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?
  5. Show that there are arbitrarily large stretches of consecutive numbers all of them being non-prime.