Skip to main content
Logo image

Exercises 21.5 Exercises


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{.}\)


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.


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).


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.


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.


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


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.


Show that if \(n>1000\) then
\begin{equation*} \frac{\log(2)+1}{\log(n)}<\frac{2}{\log(2)+\log(n)}=\frac{2}{\log(2n)} \end{equation*}
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 21  for review of how derivatives work.


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 .