Number Theorem 2nd note
Def 2.1
An integer \(p > 1\) is said to be prime iff. the only positive divisors of \(p\) are \(1\) and \(p\) itself.
It is easy to see that an integer \(n\) is composite iff it is divisible by some \(p \leq \sqrt{n}\), which leads to an (ineffective) primality test.
Rmk 2.2
There are probabilistic polynomial algorithm (about \(O\left( b^{2} \right)\) eg. Miller Rabin in 1970s) and deterministic polynomial algorithm (about \(O\left( b^{6} \right)\) eg. Agrawal-Kayal-Saxena test around 2003)
Lemma 2.3
If \(p\) is prime and \(p\) divides \(a_{1} \cdot a_{2} \cdot \ldots \cdot a_{k}\), then \(p\) divides \(a_{i}\) for some \(i\).
Pf
(Corollary 1.16) \(a|bc \Rightarrow a|c\)
Theorem 2.4 (FTA)
Each integer \(n \geq 1\) has a prime-power factorization
where \(p_{i}\)'s are distinct primes, and \(e_{i}\)'s are positive integers. Moreover, up to permutation of factors, this factorization is unique.
Pf
Existence can be easily shown by strong induction. For the uniqueness: Suppose, to the contrary, there is an integer that has two prime-power factorization(p.p.f.). Let \(n\) be the least such integer and write \(n = p_{1} \cdot p_{2} \cdot \ldots \cdot p_{j} = q_{1} \cdot q_{2} \cdot \ldots \cdot q_{k}\) (\(p_{i},q_{i}\) is prime). We see that \(p_{i}\) divides some \(q_{i}\) be lemma 2.3. WLOG, say \(p_{1}\) divides \(q_{i} \Rightarrow p_{1} = q_{1}\). Then we get \(p_{2}\ldots p_{j} = q_{2}\ldots q_{k}\), which has two distinct p.p.f. but is strictly smaller than \(n\) (contradiction).
By contrast, there is no deterministic polynomial algorithm for factoring \(n\), but probabilistic polynomial algorithms exist. (J. Pollard 1975)
Lemma 2.5
Suppose that \(a_{1},\ldots,a_{r}\) are mutually coprime positive integers. If \(a_{1}\ldots a_{r}\) is an \(m\)-th power, then each \(a_{i}\) is an \(m\)-th power.
Pf
\(\begin{aligned} a_{1} & = p_{11}^{e_{11}}\ldots p_{1k_{1}}^{e_{1k_{1}}} \\ \vdots \\ a_{1} & = p_{11}^{e_{11}}\ldots p_{1k_{1}}^{e_{1k_{1}}} \end{aligned}\)
(easy to see that each \(e_{ij}\) must be a multiple of \(m\))
Corollary 2.6
If a positive integer \(m\) is not a perfect square, then \(\sqrt{m}\) is irrational.
Pf
Suppose \(\sqrt{m} = \frac{a}{b}\) is rational \(\Rightarrow m = \frac{a^{2}}{b^{2}}\) \(\begin{cases} a = p_{1}^{e_{1}}\ldots p_{j}^{e_{j}} \\ b = p_{1}^{f_{1}}\ldots b_{j}^{f_{j}} \end{cases}\left( e_{i},f_{j} \geq 0 \right) \Rightarrow m = p_{1}^{2e_{1} - 2f_{1}}\ldots p_{j}^{2\left( e_{j} - f_{j} \right)}\) is a perfect square.\(↯\)
Theorem 2.7 (Euclid)
There are infinitely many primes.
Pf
Suppose that there are finitely many primes \(p_{1},\ldots,p_{s}\)
Consider \(m = p_{1} \cdot p_{2} \cdot \ldots \cdot p_{s} + 1\) being composite.
Then some \(p_{i}|m \Rightarrow p_{i}|1\) (contradiction)
An interesting related fact is that gap between two primes can be arbitrarily large. On the other hand, there is the well-known twin-prime conjecture.
Theorem 2.8 (Dirichlet)
If \(\gcd(a,b) = 1\), then there are infinitely many primes of the form \(aq + b\).
Pf for \(a = 4,b = 3\)
Suppose there are finitely many primes \(p_{1},\ldots,p_{s}\) of this form.
Consider \(m = 4p_{1}p_{2}\ldots p_{s} - 1\) being composite.
There must be a prime factor \(q\) of \(m\) of the form \(4q - 1\) (If all prime factors are \(4q + 1\), then their product must be \(4k + 1\))
Then \(q|m \Rightarrow q|1 ↯\)
Problem 2.9
Pick a pair \((a,b)\) with \(a \neq 2,3,4\). Prove Dirichlet's theorem for your pick.
A major extension came in 2004 when Ben Green and Terence Tao proved that primes contain arbitrarily long arithmetic progressions.
Let \(\pi(x)\) denote the number of primes \(p \leq x\). The following was conjectured by Gauss and proved by Hadamard in 1896.
Theorem 2.10 (Prime Number Theorem)
"Density" \(\frac{\pi(x)}{\left\lfloor x \right\rfloor} = O\left( \frac{1}{\ln(x)} \right)\). Primes occur less frequently when \(x\) increases.
Earlier there is Bertrand's postulate (proved by Chebyshev in 1852): for every \(n > 1\), there is always at least one prime \(p\) such that \(n < p < 2n\). This theorem can be restated as: \(\pi(x) - \pi(\frac{x}{2}) \geq 1\). (Consider \(\lim\limits_{x \rightarrow \infty}\frac{\pi(x)}{\pi(\frac{x}{2})} = 2\))
It seems (by experiment) that \(\pi(x)\) was always less than the following function:
But Littlewood in 1914 prove that there is a "crossover" point. 1
As of 2015, ot was shown that \(\pi(x) < \text{ Li}(x)\) for \(x < 10^{19}\)
As of 2011, it was shown that (the first) crossover happens before \(1.397162 \cdot 10^{316}\) by searching zeta zeros.
Corollary 2.12 (Equivalent to the Riemann Hypothesis) 2
For all \(x \geq 2.01\), \(|\pi(x) - \text{Li}(x)| \leq \sqrt{x} \cdot \ln(x)\)
2.1 Fermat and Mersenne Primes
Lemma 2.13
If \(2^{m} + 1\) is prime, then \(m = 2^{n}\) for some integral \(n \geq 0\)
Pf
Suppose \(m\) has an odd fact \(q,m = 2^{n} \cdot q\).
Then \(2^{m} + 1{= \left( 2^{2^{n}} \right)}^{q} + 1\). But \(x^{q} + 1\) has a factor \((x + 1) \Rightarrow q = 0\).
Def 2.14
Numbers of the form \(F_{n} = 2^{2^{n}} + 1\) are called Fermat numbers, and those are prime are called Fermat primes. Numbers of the form \(M_{p} = 2_{p} - 1\) are called Mersenne numbers, and those are prime are called Mersenne primes. (\(p\) os prime)
Lemma 2.15
Distinct Fermat numbers \(F_{n}\) are mutually coprime.
Pf
\(F_{n}\) and \(F_{n + k}\) are related as \(F_{n + k} - 1{= \left( F_{n} - 1 \right)}^{2^{k}}\). We see that \(F_{n}|F_{n + k} - 2\) so \(\gcd(F_{n},F_{n + k})|2\), but all Fermat numbers are odd. So \(\gcd(F_{n},F_{n + k}) = 1\)
Rmk 2.16
This provides another proof of Theorem 2.7
In 1801 Gauss showed that a regular \(n\)-gon can be constructed by rule-and-compass iff \(n = 2^{e}p_{1}\ldots p_{r}\) where \(p_{1},\ldots,p_{r}\) are distinct Fermat primes.
Later we will prove that distinct Mersenne numbers are mutually coprime.
The current world record is \(2^{82589933} - 1\) (51 th) 3
Prime numbers of the form \(p(m,n) = 2^{m} \cdot 3^{n} + 1\) are called Pierpont prime; Prime numbers of the form \(p(m,n) = 2^{m} \cdot 3^{n} - 1\) are called Pierpont prime of second kind.
Corollary 2.18 (Fei)4
There are infinitely many pairs of twin primes of the form \(\left( 2^{m}3^{n} - 1,2^{m}3^{n} + 1 \right)\).
(But for fixed \(n\), there is only finitely twin primes of this form)
HW: 2.7, 2.18, 2.19, 2.11, 2.24