Applications of Unique Factorization

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.

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.

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.

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

$\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.$

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

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

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

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.

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 ].$

Then,

$$ \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.

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.

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.

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}. $$

Hence

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

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*} $$

Then,

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

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