Prime Numbers

This page is http://www.math.uic.edu/~lewis/las100/primes.html

Main Questions:

  1. What is prime number?
  2. How many prime numbers are there?
  3. What is proof by contradiction?

Prime Numbers

A positive integer p is a prime number if p is not 0 or 1 and if p is divisible only by 1 and p.

Thus 17 is a prime number since the only factorization of 17 is 17 = 17 × 1. Are 63 and/or 131 prime numbers?

I used MAPLE to calculate the first 100 prime numbers:

Euler's Proof that there are infinitely many primes


This is a proof by contradiction. That is, we shall prove that a STATEMENT is TRUE by assuming that the NEGATION of the STATEMENT is TRUE and reach a contradiction -- i.e. a contradiction of a known fact (result, statement, ...). (See the url link for a more technical explanation).

The STATEMENT to be proved is There are infinitely many positive primes.

Proof: Suppose there are NOT infinitely many primes -- i.e., there are only finitely many positive primes, say K of them. List them all: p1, p2, p3, ... , pK. Now define the positive integer m by

m = p1 × p2 × p3 × ... × pK + 1.

Since m is greater than pj, for all j = 1, ..., K, m is not a prime. Thus, for some j, pj is a factor of m. But then pj is also a factor of

1 = m - (p1 × p2 × p3 × ... × pK).
But then 1/(pj) is an integer which satisfies 0 < 1/(pj) < 1. This is a contradiction (to what true statement?).

Thus our only choice is to conclude that the statement there are NOT infinitely many primes is FALSE -- i.e., the statement There are infinitely many positive primes is TRUE.

Questions

  1. Is the set of primes a countable set?
  2. Can you construct a prime by the formula
    m = p1 × p2 × p3 × ... × pK + 1,
    where p1, p2, p3, ..., pK are prime numbers?
  3. Is it always true that if p1, p2, ..., pK are the first K prime numbers, then
    m = p1 × p2 × p3 × ... × pK + 1,
    is a prime number?

Prime Numbers on the Web

For more information on primes, search the web on Yahoo with the keywords "prime numbers". I found a nice Prime Page by Chris Caldwell of the University of Tennessee at Martin.
Back to Prof. Lewis's LAS 100 home page