Number Theory: In Context and Interactive

1.

Consider Wilson's Theorem and consider what will happen to $(j-2)!$ modulo primes and composites (this is Exercise 7.7.8). Use this to prove the bizarre formula in Section 21.1.

2.

Calculate $\phi(n,a)$ (recall Definition 21.1.7) for various composite $n$ between $10$ and $100$ for $a=2,3,4$ and compare to $\phi(n)\text{.}$

3.

Without looking at any links, reconstruct the proof of the infinitude of primes mentioned in the first paragraph of the proof of Fact 21.1.5.

4.

Come up with two functions $f(x)$ and $g(x)$ that both go to infinity as $x\to\infty\text{,}$ such that $f(x)$ is always ahead of $g(x)\text{,}$ but $f$ and $g$ are asymptotic (to each other).

5.

Come up with two functions $f(x)$ and $g(x)$ that both go to infinity as $x\to\infty\text{,}$ but that switch the lead infinitely often and $f$ and $g$ are asymptotic.

6.

Show that the two limits in the Prime Number Theorem are really equivalent. That is, show that if $\lim_{x\to\infty} \pi(x)/Li(x)=1\text{,}$ then the other limit with $x/\log(x)$ is also 1, and vice versa.

7.

Find an arbitrarily long sequence of consecutive composite numbers using factorials.

8.

Come up with two functions $f(x)$ and $g(x)$ such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(f(x))\text{,}$ but they are not asymptotic.

9.

Use Proposition 21.3.5 to show that $\lim_{x\to\infty}\pi(x)/x=0\text{.}$

10.

Show that if $n>1000$ then

To do this, you should compare $2\log(n)$ and $(\log(2)+1)(\log(2)+\log(n))$ and their derivatives for $n=1000$ and up, then divide the two expressions appropriately. You will need to justify the calculus fact that if $f(x_0)> g(x_0)$ and $f'> g'$ for $x\geq x_0\text{,}$ then $f>g$ for $x\geq x_0$ as well. See any calculus textbook for review of how derivatives work.

11.

Verify that $3.394\frac{n}{\log(n)}<\frac{2n}{\log(2n+1)}$ for $n>1000\text{.}$ You will need to verify that the derivative of $\frac{\log(n)}{\log(2n+1)}$ is positive there.