Infinitely Many Primes

Theorem 1

In the ring $\Z$, there are infinitely many prime numbers.

Proof:

Consider a series of positive prime number $[p_1,p_2...p_n]$ where $p_n$ is the largest prime number.

We shall have $p=(p_1p_2p_3...p_n)+1 > 1$. And p is not divisible by any prime number in list.

So either $p$ is yet another prime number larger than $p_n$, or $p$ can be divide by a prime larger than $p$. By any case, we can have a larger prime given a largest prime yet.

Actually, in any Euclidean Domain, there are infinitely many primes (irreducible).

Consider a $p \in \Z$ as a prime and a set of rational number $a/b, p\nmid b$ as $\Z_p$. $\Z_p$ shall be a ring and when $p\nmid a$, $a/b$ will be a unit.

Therefore, there is only one prime in $\Z_p$ and in form of $pc/d$ where $c/d$ is a unit.

If $a/b \in \Z_p$ and not a unit, $a/b+1$ shall be a unit.

Proof:

Since $a/b$ is not a unit, so we can write $a=p^l*a'$ where $p\nmid a'$.

So $a/b+1=(a+1)/b = (p^la'+1)/p$. Obviously $p\nmid(p^la'+1)$. So $(a+1)/b$ is a unit.

Square Free

Proposition 1

An integer $a\in\Z$ is said to be square free if it is not divisible by the square of any other integer except 1.

If $n\in\Z$ can be written in form of $n=ab^2$, where $a,b\in\Z$ and a is square-free.

Proof:

Consider $a = p_1^{r_1}p_2^{r_2}...p_l^{r_l}$ and r is either 0 or 1. $b = p_1^{b_1}p_2^{b_2}...p_l^{b_l}$.

Then $n=ab^2=\prod_{i=1}^n(p_i^{2b_i+r_i})$. Since $2b_i+r_i$ can represent any integer, so proved.

Divisor function

Define $\nu(n)$ as the number of positive divisors of n and $\sigma(n)$ as the sum of positive divisors of n.

Let a be a positive integer, $n=p_1^{a_1}p_2^{a_2}...p_l^{a_l}$​ as its prime decomposition. $$\nu(n)=(a_1+1)(a_2+1)...(a_l+1)$$

$$\sigma(n)=((p_1^{a_1+1}-1)/(p_1-1))((p_2^{a_2+1}-1)/(p_2-1))...((p_l^{a_l+1}-1)/(p_l-1))$$

Proof:

A divisor is in form of $m=p_1^{b_1}p_2^{b_2}...p_l^{b_l}$ where $0\leq b_i\leq a_i$ for $i=1,2,...,l$. So the number of combination shall be $(a_1+1)(a_2+1)...(a_l+1)$. $$\sigma(n)=\sum p_1^{b_1}p_2^{b_2}...p_l^{b_l}=\sum_{b_1=0}^{a_1}p_1^{b_1}\sum_{b_2=0}^{a_2}p_2^{b_2}...\sum_{b_l=0}^{a_l}p_l^{b_l}$$

Perfect

This problem is related to Mersenne Prime. A perfect number is defined as $\sigma(n)=2n$. If a Mersenne prime $2^{m+1}=1$ is a prime, $2^m(2^{m+1}-1)$ will be perfect.

For multiplicative perfect, $\sigma(n)=n^2$. So it is obvious that iff there are 2 divisors. For example, cube of prime or products of 2 distinct prime.

Möbius function

For $n\in\Z^+$, Möbius function $\mu(1)=1,\mu(n)=0$ if $n$ is not square-free. And $\mu(p_1p_2...p_n)=(-1)^n$.

That is:

• If n is a square-free positive integer and even number of prime factors, $\mu(n)=1$;
• If n is a square-free positive integer and odd number of prime factors, $\mu(n)=-1$;
• If n has a squared prime factor,$\mu(n)=0$.

Proposition 2

If $n>1$ and $\sum_{d|n}\mu(d)=0$.

Proof:

Let $n=p_1^{a_1}p_2^{a_2}...p_l^{a_l}$. For those factors $a_i > 1$, it will turn to be zero. So we can consider: $$n=p_1p_2p_3...p_l$$ Then consider number of different type of d as $\alpha(i)$. For example, $\alpha(1)$ is the number of d that only formed by 1 prime factor. $$\alpha(i) = {l \choose i}$$ And the $\mu(d)$ of those type of d are all the same: $$\mu(d_i) = (-1)^i$$ So, our sum shall be: $$\sum_{d|n}\mu(d)=\sum_{i=0}^l(-1)^i{l \choose i}$$

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

Dirichlet Convolution

The Dirichlet convolution of $f,g$ is defined by the formular $f*g(n)=\sum f(d_1)g(d_2)$, where the sum is over all pair of $(d_1,d_2)$ which $d_1d_2=n$.

It is obvious that the Dirichlet product is associative and communitive.

Define $\Bbb{I}$ that $\Bbb{I}(1)=1$ and $\Bbb{I}(n)=0$ for $n>1$. Then, $f*\Bbb{I}=\Bbb{I}*f=f$. Define $I(n)=1$ for $n\in\Z^+$.

Lemma 1

$I*\mu=\mu*I=\Bbb{I}$

Proof:

For $n=1$, it is obvious. For $n>1$, $\mu*I(n)=\sum_{d|n}\mu(d)=0$ by Proposition 2.

Theorem 2

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

Proof:

By definition, $F=I*f(n)$. As we know: $f(n)=f*\Bbb{I}=f*(I * \mu)=(f*I)*\mu=F*\mu$.

This theorem works in any abelian group. This law also works when written multiplicatively. $$F(n)=\prod_{d|n}f(d) \implies f(n)=\prod_{d|n}F(n/d)^{\mu(d)}$$

Euler's totient function

Define Euler $\phi$ function that for $n\in\Z^+$, $\phi$ is the number of relatively prime number between 1 to prime.

Proposition 2

$\sum_{d|n}\phi(d)=n$

Proof:

Consider a series of rational number $\frac{1}{n},\frac{2}{n}...\frac{n}{n}$.

Put them into lowest term, we shall see, all the fraction with n as denominator are in number of $\phi(n)$. And for each factor d of n, there will be $\phi(d)$ number fractions. So all fraction can be split into subsets of size $\phi(d)$ for all d that $d|n$.

Proposition 3

$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_l})$ for $n=p_1^{a_1}p_2^{a_2}...p_l^{a_l}$

Proof:

By mobius inversion theorem (Theorem 2), we shall see $$\phi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$$

$$\phi(n)=n-\sum_{i}\frac{n}{p_i}+\sum_{i,j}\frac{n}{p_ip_j}-\sum_{i,j,k}\frac{n}{p_ip_jp_k}...(-1)^l\sum_{1,2,3,...l}\frac{n}{p_1p_2...p_l}$$

Sum of 1/p Diverges

Prove $\sum\frac{1}{p}$ diverges where p is positive prime.

Proof:

Consider a function $$\lambda(n) = \prod_{p}\frac{1}{1-p^{-1}}$$ Where p are primes less than n.

Then take log on both side: $$\log{\lambda(n)}=-\sum_p\log(1-p^{-1})$$ Expand log with Tylor Series: $$\log\lambda(n)=\sum_p\sum_i^{\infin}\frac{1}{ip^{i}}$$ This can be consider as: $$\log\lambda(n)=\sum_p\frac{1}{p}+\frac{1}{2}\sum_p\frac{1}{p^2}...$$ This first part is what we need.

Since $\sum\frac{1}{n^2}$ converges, so $\sum_p\frac{1}{p^2}$ converges too, as same as the rest parts.

For each part of $\lambda(n)$, $\frac{1}{1-p^-1} > 1$ so when $n\to\infin$, $\lambda(n)\to\infin$, as well as $\log{\lambda(n)}\to\infin$.

So the first part of $\log{\lambda(n)}$ must diverges.

The same proof works for $k[x]$. We need to consider prime as monic irreducible polynomials and the size of monic polynomial by $q^{\text{deg}f(x)}$