Weekly Summary

• Week 1 (April 2):
  • Introduction
  • What are primes?
  • Finding primes by the sieve method
  • Homework:
    • Read the Prime Pages link and write down three things found of interest to you.
    • On the geoboard [paper version], experiment to see what primes occur as areas of slanted squares. In other words, what primes are the sum of two squares of integers? Can you guess a criterion?
• Week 2 (April 9, Prof. Blasius):
  • Unique factorization
  • Number of divisors of n
  • gcd
  • p|mn => p|m or p|n
  • Homework:
    • Find the integer up to 1000 that, in your opinion, has the most divisors. What are your reasons?
• Week 3 (April 16):
  • Discussion of homework
  • Euclid's proof that there are infinitely many primes
  • Warmup: Counting back and forth on the fingers of one hand, starting with your thumb, on which finger do you get to 1000? To 1,000,000?
  • Division with remainders, in the form n = qm + r.
  • Congruences
  • Integers modulo 6; integers modulo 7.
  • What is special about integers modulo a prime?
  • Fermat's little theorem: If p is prime and p doesn't divide m, then m ^p-1 has remainder 1 when divided by p.

    Examples for p = 7:

    • 1 ⁶ = 1 already
    • 2 ⁶ = 64, which has remainder 1 when divided by 7
    • 3 ⁶ = 729, which has remainder 1 when divided by 7
    • 4 ⁶ = 4096, which has remainder 1 when divided by 7
    • 5 ⁶ = 15625, which has remainder 1 when divided by 7
    • 6 ⁶ = 46656, which has remainder 1 when divided by 7
  • Homework:
    • Give six illustrations of Fermat's little theorem for p prime, and three illustrations of examples where p is not prime and the theorem fails.
• Week 4 (April 23):
  • Review +, * modulo 5
  • "Casting out 9's" has easy explanation as arithmetic modulo 9.
  • Working modulo 4, see easily why a ² + b ² can have remainder only 0, 1, or 2. This explains why primes of the form p = 4n + 3, such as 3, 7, 11, and 19, do not appear as areas of slanted squares on the geoboard.
  • More on Fermat's little theorem (above): examples, how to compute them more easily, and why this theorem is true.
  • Fact that modulo any prime p, there is some "generator" g (often 2) such that 1, g, g ² , g ³ , etc. run through all the nonzero "boxes" of the integers modulo p. Example: modulo 7, the powers of 2 don't run through all nonzero possibilities, but the powers of 3 do, so 3 is a generator.
  • Homework:
    • Find four illustrations of generators modulo various primes. (To keep it interesting, don't use p = 2, 3, 5.)
• Week 5 (April 30):
  • Generators:
    • Compare notes on generator examples
    • Discussion of how list of power of non-generators cycles 1, g, ..., 1 with a cycle length that divides p-1 .
    • Can use to get simpler test for whether g is a generator: Just test g to exponents that are p-1 divided by a prime. Example: For p = 101, p-1 = 100, which has prime factors 2, 5, so just check exponents 100/2 and 100/5, i.e., g ⁵⁰ (mod 101) and g ²⁰ (mod 101).
  • Diffie-Hellman key exchange:
    Alice and Bob publicly agree on a large prime p and generator g .
    Alice picks a secret random integer a and emails Bob g ^a (mod p) .
    Bob picks a secret random integer b and emails Alice g ^b (mod p) .
    Alice computes c = (g ^{b ) a} mod p .
    Bob computes c = (g ^{a ) b} mod p .
    By algebra, both should have the same secret c , even though it was never sent by email.
    If someone intercepts their email, from knowing g ^a (mod p) or g ^b (mod p) it would be hard to find a or b if p is large.
  • Euclidean algorithm:
    See handout--but first example is messed up.
    Actually, the example comes out interestingly either way.
  • Homework:
    • Find the first prime p after 10,000 and the lowest generator for it. (Use calculator facility on web page.)
    • Same for the first prime q after 10,000,000.
    • Use p and its generator to do a Diffie-Hellman exchange with me by email.
    • Do the two versions of the first example of the Euclidean algorithm, correcting the table both ways. These are gcd(221,247) and gcd(221, 255).
• Week 6 (May 7)
  • More on the Euclidean algorithm: See handout D.
    
    • Running the Euclidean algorithm writing just one column.
    • Carrying along the information needed to get gcd(a,b) as a linear combination of a and b .
    • Using gcd(a,p) to find the inverse of a modulo p .
    • Using an inverse to do a division such as 4/9 modulo a prime.
  • Mersenne and Fermat primes
    • Review of algebra for factoring x ⁿ - 1 for any n and x ⁿ + 1 with n odd.
    • When we put an integer a for x , we see that in many cases the result is not prime. To get a prime, only certain kinds of a and n work:
      • If a ⁿ - 1 is prime, a has to be 2 and n itself has to be prime.
      • We discussed a = 2 and saw that if a ⁿ + 1 is prime then n has no odd factor and so must be a power of 2.
    • A Mersenne prime is a prime of the form 2 ^p - 1 .
    • A Fermat prime is a prime of the form 2 ^{2 m} + 1 .
    • Not all integers of these forms are prime; see the handout.
  • Homework:
    • Give one example of using the Euclidean algorithm to find an inverse modulo a prime.
    • Give an example of a division problem modulo a prime, such as 4/9.
    • Find two integers up to 100 that you think take the most steps to find their gcd using the Euclidean algorithm.
    • Think about a ⁿ + 1 for a greater than 2 . Can you get a prime this way? Are there any obvious restrictions on n to have the result be a prime?
• Week 7 (May 14)
  • Intuition for large numbers
    • Various examples of quantities in the range 10,000 to 10,000,000,000,000 (10 trillion)
    • Ways in which our ordinary intuition for numbers may be misleading when applied to huge numbers.
      
      • Example: sqrt(n) seems not too small in comparison with n when n is in the range 10 to 100, but notice that square root of n is a millionth of n when n is one trillion.
        
      • Example: For integers up to 1000, the integers with fewer than three digits are prominent in our minds because they are the most familiar. But for integers up to 10¹⁰⁰, 99 percent of them have at least 99 digits.
    • Examples of how primes thin out in high number ranges.
  • Homework:
    • Find some examples of your own for numbers in various ranges up to 10 trillion.
    • Find the number of primes among the first 30 numbers past 30; past 300; past 3000; past 3,000,000. (Notice that in each case, only 8 numbers are eligible, when you consider divisibility by 2, 3, and 5.)
• Week 8 (May 21)
  • Another surprise for large numbers: The graph of log(x) looks rectangular!
  • More on rates of growth: y = 2 ^x grows so fast that at an appropriate scale, when x is still on the paper, y is in distant galaxies!
  • Gauss conjectured that the "density" of primes near n is 1/log(n) on the average.
  • The distribution of primes:
    • pi(x) means the number of primes less than or equal to x .
    • The prime number theorem says that pi(n) is about what you get by treating the graph of log(x) like a rectangle, specifically, pi(n) is approximately n/log(n) . The approximation gets better and better percentagewise as n gets larger and larger, approaching 100%. This has been proved.
    • Gauss had a more careful approximation based on "integrating" 1/log(x) (using calculus), to take account of what happens for small values of x where the graphs of log(x) and 1/log(x) are not rectangular. The result is called Li(n) , meaning "logarithmic integral".
      This approximation to pi(x) is really quite good. Exactly how good is a big question.
  • Homework:
    • Based on Gauss' density approximation, predict the number of primes in each block of 30 numbers that you looked at before, and see how close the actual count it.
    • Read the article on Riemann posted on a door across the hall from the classroom.
• Week 9 (May 28)
  • More discussion of the error in the Li(n) . One version of the Riemann Hypothesis is that the error of Li(n) as an approximation to pi(n) is no more than some constant times n ^1/2 log(n) . There is a $1 million prize for proving this. Remember, for huge numbers, the square root is much, much smaller than the number itself.
  • Warmup on series using geometric series. How do we find the sum, when the series converges?
  • The zeta function is defined for ordinary numbers x > 1 by ζ(x) = 1/1 ^x + 1/2 ^x + 1/3 ^x + ... . We discussed how &zeta:(x) can also be expressed using a product of geometric series, one for each prime.
  • Homework:
    • Sum 1 + .1 + (.1) ² + ... .
    • By analogy with our discussion of geometric series, evaluate x = sqrt(1 + sqrt(1 + ...) ) , assuming that this makes sense.
    • Expand the product of just the first two geometric series involved in the zeta function.
    • Visit three web sites and write one sentence about each:
      • Complex geometric series
      • The complex Riemann Zeta Function
      • Graph of ζ
• Week 10 (June 4)
  • Understanding addition and multiplication of complex numbers.
  • Theme: Complex numbers as taking the blinders off.
    • First example: cube roots of 1
    • Second example: region of convergence of a geometric series.
  • The challenge of visualizing a function of complex numbers.
  • Third example: the complex Riemann ζ function
  • The Riemann Hypothesis in terms of the "roots" of ζ in the "critical strip". Are they all on the middle line?
  • No homework!