Infinitely Many Primes in $\mathbb{Z}$§

Theorem 1 (Euclid)

There exists infinitely many prime numbers in $\mathbb{Z}.$

Consider a finite set of primes $P = \{p_1, p_2, \dots, p_n\}.$ Let $N = (p_1p_2\dots p_n) + 1.$

  • If $N$ prime, then $N > p_n.$
  • If $N$ composite, then there must exist some prime $q$ such that $q | N.$ If $q \in P, $ then $q | N - 1.$ Then, $q | N - (N - 1) \implies q | 1,$ which is impossible.

So for any finite set of primes, there will always exist at least one prime not included within the set. Therefore, there exists infinitely many primes.

As the set of primes is a subset of the integers, there exists a countably infinite number of primes.

The equivalent theorem in $k[ x ]$ is that there exists infinitely many monic irreductible polynomials. It becomes trivial if $k$ is infinite, as $\forall a \in k, x - a$ is a monic and irreductible polynomial.

todo: Show that there are infinitely many primes in $k[ x ]$ for $k$ finite.

The Ring $\mathbb{Z}_p$§

These proofs show that there exist infinitely many nonassociate primes. We now want to consider the ring $\mathbb{Z}_p$ where all primes are associate.

Choose $p \in \mathbb{Z}$ prime, let $\mathbb{Z}_p$ denote the set of all rational numbers $a/b$ where $p \nmid b.$ $a/b \in \mathbb{Z}_p$ is a unit if there exists $c/d \in \mathbb{Z}_p$ such that $a/b \cdot c/d = 1.$ Then $ab = cd$ implies $p \nmid a,$ as by construction $p \nmid b$ and $p \nmid d.$ Conversely, any rational $a/b \in \mathbb{Z}_p$ is a unit if $p \nmid a$ and $p \nmid b.$ If $a/b \in \mathbb{Z}_p,$ write $a = p^la’,$ where $p \nmid a’.$ Then $a/b = p^la’/b.$ Thus every element of $\mathbb{Z}_p$ is a power of $p$ times a unit. The only primes in $\mathbb{Z}_p$ have the form $pc/d,$ where $c/d$ a unit. Therefore, all primes in $\mathbb{Z}_p$ are associate.

Exercise: If $a/b \in \mathbb{Z}_p$ is a nonunit, then $a/b + 1$ is a unit.

Sps. that $a/b \in \mathbb{Z}_p$ is a nonunit such that $p | a$ and $p \nmid b.$ Then, $a/b + 1 = (a + b) / b,$ we have that $p \nmid a + b$ and $p \nmid b.$ Therefore, $a/b + 1$ is a unit in $\mathbb{Z}_p.$

From above, we realize the proof provided by Euclid is insufficient to prove that there exists infinitely many primes does not work for every integral domain.

Arithmetic Functions§

Square Free

$a \in \mathbb{Z}$ is square-free iff it is not divisible by the square of any integer greater than $1.$

Proposition 1

If $n \in \mathbb{Z},$ $\exists a, b \in \mathbb{Z}, n = ab^2$ and $a$ square-free.

Consider the prime decomposition of $n = \decomp{p}{a}{i}.$ Then $a_i = 2b_i + r_i,$ where $r_i$ is $0$ or $1$ depending on the parity of $a_i.$ Let $a = \decomp{p}{r}{i}, b = \decomp{p}{b}{i}.$ Therefore, $n = ab^2$ and $a$ square-free.

Using the proposition above, we can provide an alternate proof by Erdos for the infinitude of primes.

Sps. that there exists finitely many primes, $p_1, p_2, \dots, p_\ell,$ where $\ell \in \mathbb{N}.$ Let $n \in \mathbb{N},$ and consider all the natural numbers $m \leq n.$ We can write all these natural numbers as $m = ab^2$ for $a \in \mathbb{N}$ square-free and $b \in \mathbb{N}.$ Then, we see that $a$ must equal to one of the $2^\ell$ numbers $p_1^{\varepsilon_1}p_2^{\varepsilon_2}\dots p_l^{\varepsilon_\ell},$ where $\varepsilon_i \in \{0, 1\}$ and $i = 1, \dots, \ell.$ Notice that $b \leq \sqrt{n},$ then there are at most $2^\ell\sqrt{N}$ numbers satisfying $m = ab^2,$ so we can conclude that $n \leq 2^\ell \sqrt{n},$ which is obviously false for large $N.$

Divisor and Divisor Summatory Functions§

In this section we define $v(n)$ to give the number of positive divisors of $n,$ and $\sigma(n)$ to give the sum of said divisors.

Proposition 2

Consider the prime decomposition for a positive integer $n = \decomp{p}{a}{\ell}.$ Then,

$$ \begin{align} v(n) &= \prod_{i = 1}^{\ell} (a_i + 1)\\ \sigma(n) &= \prod_{i = 1}^{\ell} \Big[\left(p_i^{a_i + 1} - 1\right) / \big(p_i - 1\big)\Big] \end{align} $$

For $v(n),$ notice $m | n$ iff $m = \decomp{p}{b}{\ell}$ and $0 \leq b_i \leq a_i,$ for $i = 1, \dots, \ell.$ Then, the positive divisors of $n$ are one-to-one correspondence with the $n$-tuples $(b_1, b_2, \dots, b_\ell)$ with $0 \leq b_i \leq a_i$ for $i = 1, \dots, \ell,$ and there are exactly $\prod_{i = 1}^{\ell} (a_i + 1)$ such $n$-tuples.

For $\sigma(n),$ notice that $\sigma(n) = \sum \decomp{p}{b}{\ell}$ where the sum is over the set of $n$-tuples as described above. Then, $$ \sigma(n) = \prod_{i=1}^{\ell} \Bigg[\sum_{b_i = 0}^{a_i} p_i^{b_i}\Bigg], $$ which the result follows from by use of the summation formula for geometric series.

Perfect Numbers§

Perfect Number

A positive integer $n$ is a perfect number if it is equal to the sum of its positive divisors, excluding itself.

In terms of our $\sigma(n)$ function, $n$ is perfect if $\sigma(n) = 2n.$

In general if $2^{m + 1} - 1$ is prime, then $2^m\left(2^{m+1} - 1\right)$ is perfect, in fact any even perfect number has this form. Then we can reduce the problem statement of finding perfect numbers into finding Mersenne primes. We know not if there are infinitely many of such numbers nor if there exist any odd perfect numbers.

The multiplicative analogue is as follows: $n$ is multiplicatively perfect if the product of the positive divisors of $n$ is $n^2.$ A number of this kind is cannot be prime nor the square of a prime. Ergo a number $n$ is multiplicatively perfect iff there are exactly two proper divisors.

Möbius $\mu$ Function§

Möbius $\mu$ Function

For $n \in \mathbb{N},$ we define the Möbius function as

$$ \mu(n) = \begin{cases} 1 & \text{ if } n = 1,\\ 0 & \text{ if $n$ not square-free},\\ (-1)^{\ell} & \text{ if $n$ square-free, where } n = p_1p_2\dots p_\ell \end{cases} $$

Proposition 3

$$ \forall n \gt 1, \sum_{d | n} \mu(d) = 0. $$

If $n = \decomp{p}{a}{\ell},$ then

$$ \sum_{d | n} \mu(d) = \sum_{\varepsilon_1, \dots, \varepsilon_\ell}\mu\left(p_1^{\varepsilon_1}\dots p_\ell^{\varepsilon_\ell}\right), $$

where $\varepsilon_i \in \{0, 1\}.$ Thus,

$$ \sum_{d | n} \mu(d) = 1 - \ell + \binom{\ell}{2} - \binom{\ell}{3} + \dots + (-1)^\ell = (1 - 1) = 0. $$

Dirichlet Convolution§

Dirichlet Convolution

Let $f, g : \mathbb{N} \to \mathbb{C},$ the Dirichlet convolution of $f$ and $g$ denoted by $f \star g$ is defined by

$$ f \star g(n) = \sum_{\substack{(d_1, d_2) \in \mathbb{Z}^2\\d_1d_2 = n}} f(d_1)g(d_2) $$

$f\star (g \star h)(n) = (f \star g)\star h(n) = \sum f(d_1)g(d_2)h(d_3)$ for all $3$-tuples $(d_1, d_2, d_3) \in \mathbb{Z}^3$ such that $n = d_1d_2d_3.$

Note: Ireland and Rosen use “Dirichlet Product” and the notation $f \circ g$ instead of “Dirichlet Convolution” and $f \star g.$

Define the Dirichlet identity function $H: \mathbb{N} \to \mathbb{N}$ by $H(1) = 1$ and $H(n) = 0$ for all other $n > 1.$ Then, $f \star H(n) = H \star f = f(n).$ We define $I: \mathbb{N} \to \mathbb{N}$ by $I(n) = 1.$ Then, $f \star I(n) = I \star f(n) = \sum_{d|n} f(d).$

Note: The function $H(n)$ is denoted by some rectangular symbol in the text that I am unable to replicate using $\KaTeX.$ On the Wikipedia article for Dirichlet Convolution they use $\varepsilon(n)$ for this unit function.


$$ I \star \mu = \mu \star I = H $$

$\mu \star I(1) = \mu(1)I(1) = 1.$ If $n \gt 1, \mu \star I(n) = \sum_{d|n}\mu(d) = 0.$ The same method can be applied for $I \star \mu.$

Theorem 2 (Möbius Inversion Theorem)

Let $F(n) = \sum_{d|n} f(d).$ Then, $$f(n) = \sum_{d|n} \mu(d)F(n/d).$$

$F = f \star I,$ thus $F \star u = (f \star I) \star \mu = f \star (I \star \mu) = f \star H = f.$

This shows that $f(n) = F \star \mu(n) = \sum_{d|n}\mu(d)F(n/d).$

Note that we have considered functions $\mathbb{N} \to \mathbb{C},$ but we should notice that the above theorem is valid for any complex functions that take their value in an abelian group.

If the group law in the abelian group is written multiplicatively, Theorem 2 then takes the form: If $F(n) = \prod_{d|n} f(d),$ then $f(n) = \prod_{d|n} F(n/d)^{\mu(d)}.$

Euler’s Totient Function§

Also Euler’s $\varphi$ Function, or Euler’s $\phi$ Function. See also Euler’s Totient Function on my cryptography notes.

Ireland and Rosen use $\phi$ to denote this function, I use $\varphi.$

Euler’s Totient

We use $\varphi(n)$ to denote Euler’s totient function, and it is defined to be the number of integers between $1$ and $n$ that are coprime with $n.$

Proposition 4

$$ \sum_{d|n}\varphi(d) = n. $$

Consider the rational numbers of the form $1/n, 2/n, 3/n, \dots, (n - 1) / n, n/n.$ Reduce each rational into its lowest terms, then the denominators will be divisors of $n.$ If $d|n$ then exactly $\varphi(d)$ of these numbers will have $d$ in the denominator after reducing to lowest terms. Therefore, $\sum_{d|n}\varphi(d) = n.$

Proposition 5

Consider the prime decomposition of $n = \decomp{p}{a}{\ell},$ then

$$ \varphi(n) = n\prod_{i = 1}^{\ell} (1 -(1/p_i)). $$

Since $n = \sum_{d|n}\varphi(d),$ the Möbius inversion theorem implies $\varphi(n) = \sum_{d|n} \mu(d)n/d = n - \sum_{i} n/p_i + \sum_{i \lt j}n/p_ip_j\dots = n\prod_{i = 1}^{\ell} (1 -(1/p_i)).$

Reciprocal Prime Summation§

Primes in $\mathbb{Z}$§

Theorem 3

The summation over all positive primes in $\mathbb{Z},$ $$ \sum \frac{1}{p}, $$ diverges.

Let $p_1, p_2, \dots, p_{\ell(n)}$ be all primes less than $n$ and define $\lambda(n)= \prod_{i=1}^{l(n)}(1 - 1/p_i)^{-1}.$ Since $(1 - 1/p_i)^{-1} = \sum_{a_i = 0}^{\infty} 1/p_i^{a_i},$ we get that

$$ \lambda(n) = \sum\left(\decomp{p}{a}{\ell}\right)^{-1}, $$

where the sum is over all $\ell$-typles of nonnegative integers $(a_1, a_2, \dots, a_\ell).$

Particularly, $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \lt \lambda(n).$ Then $\lim_{n\to\infty} \lambda(n) = \infty,$ which gives rise to yet another proof of the infinitude of primes.

Next, consider $\log\lambda(n),$

$$ \begin{align*} \log \lambda(n) &= -\sum_{i = 1}^{\ell}\log\left(1 - p_1^{-1}\right)\\ &= \sum_{i=1}^{\ell}\sum_{m=1}^{\infty}\left(mp_i^m\right)^{-1}\\ &= p_1^{-1} + p_2^{-1} + \dots + p_1^{-1} + \sum_{i=1}^{\ell}\sum_{m=2}^{\infty}\left(mp_i^m\right)^{-1}. \end{align*} $$

Then we can inspect the inequality,

$$ \sum_{m=2}^{\infty} \left(mp_i^m\right)^{-1} \lt \sum_{m=2}^{\infty}p_i^{-m} = p_i^{-2}\left(1-p_i^{-1}\right)^{-1} \leq 2p_i^{-2}. $$

Which gives us

$$ \log\lambda(n) \lt p_1^{-1} + p_2^{-1} + \dots + p_\ell^{-1} + 2\left(p_1^{-2} + p_2^{-2} + \dots + p_\ell^{-2}\right). $$

We know that the $p$ series for $p = 2$ converges, then it follows that $\sum p_i^{-2}$ converges as well. If $\sum p^{-1}$ converged, then there must exist a constant $M$ such that $\log\lambda(n) \lt M,$ or equivalently $\lambda(n) \lt e^{M}.$ However, we’ve established $\lim_{n\to\infty} \lambda(n) = \infty$ so there cannot exist an $M$ that satisfies this, therefore $\sum p^{-1}$ must diverge.

Primes in $k[ x ]$§

Theorem 4

The sum over all monic irreductible polynomials $p(x) \in k[ x ],$ $$\sum q^{-\deg p(x)},$$ diverges.

Similiarly to the proof for Theorem 3, we can show that for monic polynomials $f \in k[ x ]$ that $\sum q^{-\deg f(x)}$ diverges and that $\sum q^{-2\deg f(x)}$ converges. These follow as there are exactly $q^{n}$ monic polynomials with degree $n$ in $k[ x ].$


$$ \sum_{\deg f(x) \leq n} q^{-\deg f(x)} = \sum_{m = 0}^{n} q^{m}q^{-m} = n + 1 $$

Then, $\sum q^{-\deg f(x)}$ must diverge and

$$ \sum_{\deg f(x) \leq n} q^{-2\deg f(x)} = \sum_{m = 0}^{n} q^{m}q^{-2m} \lt (1 - 1/q)^{-1} $$

converges. The rest of the proof can be derived from the proof for Theorem 3.

Growth of $\pi(x)$§

Lower Bound via Euclid§

From Euclid’s proof of infinite primes, we can derive a lower-bound to the prime counting function.

Proposition 6

For all $x \geq 2,$

$$ \pi(x) \geq \log(\log x). $$

Let $p_n$ be the $n$th prime. Then, any prime that divides $1 + \prod_{i=1}^n p_i$ is distinct from the set of primes $p_1$ to $p_n,$ it follows that $p_{n+1} \lt 1 + \prod_{i=1}^n p_i.$ We get that $p_1 \lt 2^{2^1}, p_2 \lt 2^{2^2}$ and if $p_n \lt 2^{2^n}$ then $p_{n + 1} \leq \prod_{i=1}^{n} 2^{2^i} = 2^{2^{n+1} - 2} + 1 \lt 2^{2^{n + 1}}.$ It follows that $\pi\left(2^{2^n}\right) \geq n.$ For $x \gt e$ we can choose an integer $n$ such that $e^{e^{n - 1}} \lt x \leq e^{e^n}.$ For $n \gt 3$ then $e^{n - 1} \gt 2^n,$ so

$$ \pi(x) \geq \pi\left(e^{e^{n-1}}\right) \geq \pi\left(e^{2^n}\right) \geq \pi\left(2^{2^n}\right) \geq \log(\log x). $$

The proof shows that the result is correct for $x \gt e^e,$ and for $x \leq e^e$ the inequality is obvious.

Lower Bound via Erdos§

A further improvement on the lower-bound for the prime counting funciton can be found by inspecting Erdo’s proof with square-free numbers. Below, we define the function $\gamma(n)$ for positive $n$ to be the set of prime divisors of $n.$

Proposition 7

$$ \pi(x) \geq \frac{\log x}{2\log 2}. $$

Let $S$ be any set of primes where the function $f_s(x)$ is defined to be the number of integers $n \in [1, x],$ such that $\gamma(n) \subset S.$ Sps. that $S$ is finite with cardinality $t.$ Then, writing $n$ in the form $n = m^2s$ where $s$ square-free, we get that $m \leq \sqrt{x}$ and there are at most $2^t$ choices for $s,$ with each one corresponding to a subset of $S.$ Thus $f_s(x) \leq 2^{t}\sqrt{x}.$

Let $\pi(x) = m,$ so that $p_{m+1} \gt x.$ If $S = \{p_1, \dots, p_m\},$ then clearly $f_s(x) = x$ which implies that $x \leq 2^{m}\sqrt{x} = 2^{\pi(x)}\sqrt{x}.$ Then the result immediately follows.

Square-free Divergence Proof§

We can observe that the proof method above can also be used as an alternative proof to the divergence of the summation of prime reciprocals.

If $\sum 1/p_n$ converged, then there must exist an $n$ such that $\sum_{j \gt n} 1/p_j \lt \frac{1}{2}.$ If $S = \{p_1, \dots, p_n\},$ then $x - f_s(x)$ is the number of positive integers $m \leq x$ such that $\gamma(m) \notin S.$ That is, there exists a prime $p_j$ for $j \gt n$ such that $p_j | m.$ Such a prime, there are $[x/p_j]$ multiples of $p_j \leq x.$ Then,

$$ x - f_s(x) \leq \sum_{j \gt n} \left[\frac{x}{p_j}\right] \leq \sum_{j \gt n}\frac{x}{p_j} \lt \frac{x}{2}, $$

so that $f_s(x) \geq x/2.$ On the other hand, $f_s(x) \leq 2^n \sqrt{x}.$ The inequalities imply $2^n \geq \frac{1}{2}\sqrt{x},$ which for fixed $n$ and large $x$ is false.

Logarithmic Prime Summation§

Then we define the function $\theta(x) = \sum_{p_x} \log p,$ i.e. the sum of the logarithm of all primes that are at most $x.$ For $\theta(1)$ we define it to be $0.$

Proposition 8

$$ \theta(x) \leq (4\log 2)x. $$

Consider the binomial coefficient, $$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} = \frac{\prod_{i=n+1}^{2n} i}{n!}. $$

This integer is divisible by all primes $p \in (n, 2n),$ and

$$ (1 + 1)^{2n} = \sum_{j = 0}^{2n}\binom{2n}{j}, 2^{2n} \gt \binom{2n}{n}. $$


$$ 2^{2n} \gt \binom{2n}{n} \gt \prod_{n \lt p \lt 2n} p, $$

and therefore

$$ 2n\log 2 \gt \sum_{n \lt p \lt 2n} \log p = \theta(2n) - \theta(n). $$

For $n = 1, 2, 4, 8, \dots, 2^{m-1},$ the summation gives

$$ \begin{align*} \theta\left(2^{m}\right) &\lt \big(\log 2\big)\left(2^{m + 1} - 2\right)\\ &\lt (\log 2)2^{m + 1}. \end{align*} $$

If $2^{m-1} \lt x \leq 2^m,$ we get $$ \theta\big(x\big) \leq \theta\big(2^m\big) \lt \big(\log 2\big)2^{m+1} = \big(4\log 2\big)2^{m-1} \lt \big(4\log 2\big)x. $$

Asymptotic Upper Bound§

Corollary 1

$$ \pi(x) \in \mathcal{O}\left(\frac{x}{\log x}\right) $$

There must exist a $c$ such that for all $n \in \mathbb{N}, n \geq n_c$

$$ \pi(x) \leq cx/\log x. $$

Then, for $n_c = 2,$

$$ \begin{align*} \theta(x) &\geq \sum_{\sqrt{x} \lt p \leq x} \log p\\ &\geq \big(\log\sqrt{x}\big)\big(\pi(x) - \pi\big(\sqrt{x}\big)\big)\\ &\geq \big(\log\sqrt{x}\big)\pi{x} - \sqrt{x}\log\sqrt{x}. \end{align*} $$


$$ \begin{align*} \pi(x) &\leq \frac{2\theta(x)}{\log x} + \sqrt{x}\\ &\leq (8\log 2)\frac{x}{\log x} + \sqrt{x}. \end{align*} $$

Because $\sqrt{x} \lt 2x\log x$ for all $x \geq 2,$ $\pi(x) \in \mathcal{O}(x/\log x).$

Corollary 2

$$\pi(x) \in o(x).$$

Asymptotic Lower Bound§

Using properties of the binomial coefficient, we can observe that

$$ \binom{2n}{n} = \binom{n+1}{1}\binom{n+2}{2}\dots\binom{n+n}{n} \geq 2^n. $$

Then, using the fact

$$ \ord_p \binom{2n}{n} = \ord_p \frac{(2n)!}{(n!)^2} = \sum_{j = 1}^{t_p}\left(\left[\frac{2n}{p^j}\right] - 2\left[\frac{n}{p^j}\right]\right), \tag{\dag} $$

where $t_p$ is defined to be the largest integer such that $p^{t_p} \leq 2n.$

Then, $t_p = [\log 2n / \log p].$ Finally, we get that $[2x] - 2[x] \in \{0, 1\}.$ It then follows that

$$ \ord_p \binom{2n}{n} \leq \frac{\log 2n}{\log p}. $$

Note: ($\dag$) is a result from Exercise 6 from this chapter in Ireland and Rosen.

Proposition 9

$$ \pi(x) \in \Omega\left(\frac{x}{\log x}\right) $$

We have that $$ 2^n \leq \binom{2n}{n} \leq \prod_{p \lt 2n} p^{t_p}. $$


$$ n\log 2 \leq \sum_{p \lt 2n} t_p \log p = \sum_{p \lt 2n} \left[\frac{\log 2n}{\log p}\right]\log p. $$

If $\log p \gt \frac{1}{2} \log 2n,$ then $[\log 2n / \log p] = 1.$ Thus, $$ \begin{align*} n\log 2 &\leq \sum_{p \leq \sqrt{2n}}\left[\frac{\log 2n}{\log p}\right]\log p + \sum_{\sqrt{2n} \lt p \lt 2n} \log p\\ &\leq \sqrt{2n} \log 2n + \theta(2n). \end{align*} $$

Therefore, $\theta(2n) \gt n\log 2 - \sqrt{2n} \log 2n.$ But, $\lim_{n\to\infty} (\sqrt{2n} \log 2n) / n = 0,$ so $\theta(2n) \gt Tn$ for some $T \gt 0$ and for sufficiently large $n.$

For large $x, 2n \leq x \lt 2n + 1$ then we get $\theta(x) \geq \theta(2n) \gt Tn \gt T(x - 1) / 2 \gt Cx,$ for some $C \in \mathbb{R}.$

Thus, there exists a constant $c$ such that $\theta(x) \gt c$ for all $x \geq 2.$ Finally, we observe that

$$ \theta(x) = \sum{p \leq x} \log p \leq \pi(x) \log x. $$

Therefore, $\pi(x) \geq \frac{\theta(x)}{\log x} \gt c \frac{x}{\log x},$ and $\pi(x) \in \Omega\left(\frac{x}{\log x}\right).$

Finally, $$\pi(x) \in \Theta\left(\frac{x}{\log x}\right).$$

The asymptotic tightness was proven by Tchebychef in 1852, and later the prime number theorem was able to show the asymptotic equality $\pi(x) \sim \frac{x}{\log x}.$