Formulas for Primes

Prev: Floating-Point

Sections

• 18-1 Introduction
• 18-2 Willans’s Formulas
• 18-3 Wormell’s Formula
• 18-4 Formulas for Other Difficult Functions

Problems

1. Prove that for any non-constant polynomial $f(x)$ with integral coefficients, $|f(x)|$ is composite for an infinite number of values of $x$.

   Hint: if $f(x_0)=k$, consider $f(x_0+rk)$, where $r$ is an integer greater than 1.

2. Prove Wilson’s theorem: an integer $p>1$ is prime if and only if

   $$(p-1)!\equiv -1(\mathrm{mod}p).$$

   Hint: to show that if $p$ is prime, then $(p-1)!\equiv -1(\mathrm{mod}p)$, group the terms of the factorial in pairs $(a,b)$ such that $ab\equiv 1(\mathrm{mod}p)$. Use Theorem MI of Section 10-16 on page 240.

3. Show that if $n$ is a composite integer greater than 4, then

   $$(n-1)!\equiv 0(\mathrm{mod}n).$$

4. Calculate an estimate of the value of $\theta$ that satisfies Mills’s theorem, and in the process give an informal proof of the theorem. Assume that for $n>1$ there exists a prime between $n^3$ and $(n+1{)}^3$. This depends upon the Riemann Hypothesis, although it has been proved independent of RH for sufficiently large $n$.

5. Consider the set of numbers of the form described in the book, where $a$ and $b$ are integers. Show that 2 and 3 are primes in this set, that is, they cannot be decomposed into factors in the set unless one of the factors is $\pm 1$, a unit. Continue the exercise from the book’s final sentence.