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 $\varphi (n,a)$ (recall Definition 21.1.7) for various composite $n$ between $10$ and $100$ for $a=2,3,4$ and compare to $\varphi (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 \mathrm{\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 \mathrm{\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 $\underset{x\to \mathrm{\infty }}{lim}\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.7 to show that $\underset{x\to \mathrm{\infty }}{lim}\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^{\prime }>g^{\prime }$ for $x\ge x_0\text{,}$ then $f>g$ for $x\ge x_0$ as well. See any calculus textbook for review of how derivatives work.

11.

Verify that $3.394\frac{n}{\log (n)}<\frac{4n}{\log (2n+1)}$ for $n>1000\text{.}$ (See the previous problems; you will need to verify that the derivative of $\frac{\log (n)}{\log (2n+1)}$ is positive in that range.) Also confirm that $\frac{n}{\log (n)}$ is increasing .