Exercises 21.5 Exercises
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.7 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{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 .