QR: Magic of Numbers
10/28/02
Outline of lecture by Dick Gross



                             PRIMES


I. REVIEW OF FRIDAY 10/25 LECTURE (c.f. 11.2)
  A. Definition of prime
      - A number p is prime if its only divisors are p and 1.
  B. Definition of composite
      - A number n is composite if it is not prime, i.e.
        it has _more_ divisors than n and 1.
  C. Fundamental FACT about primes
      - If p is a prime number, then when p divides a product ab,
        it must also divide either a or b.

II. PRIMES AND BINOMIAL COEFFICIENTS (c.f. 11.3)
  A. Prime rows of Pascal's Triangle are divisible by that prime:
      - If p is prime, then p divides (p choose k) for all 0 < k < p.
        NOTE: This excludes the cases k=0 and k=p, since
        (p choose 0) = (p choose p) = 1.

III. TESTING FOR PRIMALITY (c.f. 10.3)
  A. Trial Division
      - n is prime if all of the prime numbers less than SQUAREROOT(n)
        fail to divide n.
  B. Sieve of ERATOSTHENES
      - Test the numbers 1, 2, ..., n for primality ALL AT ONCE!
        Simply write down 1, 2,..., n, and mark out the numbers
        divisible by 2, divisible by 3, divisible by 5, ...
        up to numbers divisible by p,
        where p is the smallest prime less than SQUAREROOT(n).
        After you have finished, the survivors will be prime,
        and the marked-out guys will be composite.

IV.  INFINITELY MANY PRIMES (c.f. 10.5)
  A. There are inifinitely many primes.
       - Proof by contradiction.  This is tricky if you aren't used
         to dealing with proofs.  We'll go over it in section, but
         the proof isn't terribly important to us for now.

V.  PRIME DESERTS and TWIN PRIMES (c.f. 10.6)
  A. A prime desert of length k is a string of k consecutive composites.
       1. It is possible to find a prime desert as long as you want.
       2. To construct an example of such a desert, you can use a trick:
            20!+2, 20!+3, ..., 20!+21 is a string of 20 consecutive
            composites, and you can do the same thing for 100 consecutive
            composites, or 1000, or whatever number you want.
  B. Twin primes are primes which differ by 2, like {3,5}, {5,7}, {11,13}.
       - It is widely believed that an infinite number of pairs of
         twin primes exist, but after centuries, no has ever proven it.