Assignment #3

Due Friday, April 23.

To do but not hand in:

p. 50 Ex. 3;

p. 52 Ex. 7, 13;

p. 65 Ex. 3;

p. 67 Ex 5;

p. 74 Ex. 5;

D-2. (Do be sure to try D-2 to see what it is saying.)

To hand in:

p. 49 Ex. 2;

p. 53 Ex. 18;

p. 55 Ex. 1;

p. 65 Ex. 5;

p. 67 Ex. 6;

p. 74 Ex. 6;

Ex. D-1.

Problem D-1. There is a link on the Math 117 home page to an applet that shows which entries in Pascal's triangle are divisible by an integer that you specify. The integer is changed by clicking on Divisor+ or Divisor-. The current integer is shown at the bottom of your browser.

(a) Make the integer a prime $p$, say $p = 5$ or $p = 7$. Which colored dots correspond to the statement of Problem C-2(b)?

(b) Explain why the colored dots in (a) are the top of a triangle. In other words, why are the dots in the triangle colored, and why aren't the dots just outside the triangle colored? (Don't forget the recursive description of binomial coefficients, and think in terms of congruences.)

(c) Below the triangle mentioned in (b) above there are more triangles of the same size. Formulate a divisibility statement that describes the top rows of these triangles. (In other words, state that $p$ divides certain binomial coefficients that depend on the triangle in the row.)

(d) Invent some divisibility statement to describe the top rows of the larger and larger triangles divisible by $p$, just the first one of each size.

Problem D-2. (a) Traditionally, $\pi(n)$ means the number of primes up to $n$. For example, $\pi(10^8)$ (a hundred million) is 5,761,455. What is $\pi(100)$?

Describing the distribution of prime numbers is a very challenging problem. In one sense they seem randomly distributed, but obviously they aren't random since a given integer is either prime or not. The ``density'' of primes (the proportion of integers that are prime) goes down as you look at larger and larger numbers. Gauss (``gowss'', 1777-1855) observed that apparently their density near $n$ is ${\frac{\displaystyle 1}{\displaystyle \log n}}$, in the sense that if you look at a stretch of integers near $n$ about that proportion of them are apt to be prime¹.

(b) The attached sheet shows blocks of primes with various starting values. Does the block starting with 1,000,000 have more primes or fewer than Gauss' density observation predicts? How about the block starting at $10^{100}$? (Primes this large are used in encryption.)

Because of his density observation, Gauss predicted that for large $n$, $\pi(n)$ should be close to $Li(n)$, the ``logarithmic integral'', given by

Li$$(n) = \int _ 2 ^ x {\frac{\displaystyle 1}{\displaystyle \log x}} dx.$$

Using the same ``$\sim$'' notation as in Problem C-1 for a ratio approaching 1, it is easy to show that Li$(n) \sim {\frac{\displaystyle n}{\displaystyle \log n}}$ [you are not asked to do this], so Gauss suspected that $\pi(n) \sim {\frac{\displaystyle n}{\displaystyle \log n}}$. This was proven by other mathematicians in 1896 (the ``Prime Number Theorem'').

(c) For $n = 10^8$, how close to 1 is the ratio of $\pi(n)$ to ${\frac{\displaystyle n}{\displaystyle \log n}}$?

(d) The Riemann Hypothesis (``ree-mahn'', 1826-1866), an unproven conjecture with a million-dollar prize for its solution, states roughly that the error $\vert\pi(n) -$   Li$(n)\vert$ has about half as many decimal digits as $n$, or fewer than that, as $n \rightarrow \infty$. Does this seem plausible for $n = 10^{16}$? Here $\pi(n) =$ 279,238,341,033,925 and Li$(n) =$ 279,238,344,248,557. ... (Notice that the error is an extremely small percentagewise.)