Q1

Prove that $k[x]$ has infinitely many irreducible polynomials.

Proof:

Consider $[f_1(x),f_2(x),...,f_n(x)]$ with $f_n(x)$ as the largest irreducible polynomial.

Then we have a new polynomial $f(x)=f_1(x)f_2(x)...f_n(x)+1$.

Obviously, $f(x)$ have higher order and cannot be divided by any of the previous polynomials.

Q2

For prime $p_1,p_2,p_3,...,p_n \in \Z$, consider a set of rational number $r=a/b,a,b\in\Z$ and $\text{ord}_{p_i}a \geq \text{ord}_{p_i}b$. Prove that this set is a ring, and $p_1,p_2,...p_n$ are the only primes.

Proof:

First, prove addition:

Consider $r_1 = a/b$ and $r_2=c/d$. We need to prove $r=r_1+r_2$ is still in set: $$r=\frac{a}{b}+\frac{c}{d} = \frac{ad+bc}{bd}$$ That is to prove: $$\text{ord}_{p_i}{ad+bc} \geq \min(\text{ord}_{p_i}{ad},\text{ord}_{p_i}{bc})\geq \min(\text{ord}_{p_i}{a}+\text{ord}_{p_i}{d},\text{ord}_{p_i}{c}+\text{ord}_{p_i}{b})$$ Since $\text{ord}_{p_i}{a}\geq \text{ord}_{p_i}{b}$ and $\text{ord}_{p_i}{c}\geq \text{ord}_{p_i}{d}$

We shall see: $$\text{ord}_{p_i}{ad+bc} > \text{ord}_{p_i}{bd}$$ Then prove multiplication: $$r = r_1r_2 = \frac{ac}{bd}$$

$$\text{ord}_{p_i}{ac} = \text{ord}_{p_i}{a}+\text{ord}_{p_i}{c} \geq \text{ord}_{p_i}{b} + \text{ord}_{p_i}{d} \geq \text{ord}_{p_i}{bd}$$

So it is a ring.

For a prime in this set, we have $\frac{a}{b}|\frac{ce}{df} \iff \frac{a}{b}|\frac{c}{d}\ \text{or}\ \frac{a}{b}|\frac{e}{f}$.

So by all means, $a,b$ should both be prime if $b\neq 1$.

Then $\text{ord}_{p_i}a = 1$ when $a=p_i$ and so does b. If $b\neq 1$, $\text{ord}_bb = 1 > \text{ord}_ba = 0$ that will make $a/b$ not in this set. So all primes should be $p/1$.

Q3

Prove there are infinitely many prime number.

Proof:

If there are finite many prime: $p_1,p_2,p_3,...,p_l$. Then for $n=p_1p_2p_3...p_l$, $\varphi(n)=1$.

However: $$\varphi(n)=n\prod_{i=1}^l(1-1/p_i)=1$$ That is $$\prod_{i=1}^l(1-1/p_i)=\prod_{i=1}^l 1/p_i$$ That's a contradiction.

Q4

If a is a non-zero integer, then for $m>n$ that $(a^{2^n}+1,a^{2^m}+1)=1\ \text{or}\ 2$.

Proof: $$a^{2^m}-1 = (a^{2^{m-1}}+1)(a^{2^{m-1}}-1) = (a^{2^{m-1}}+1)(a^{2^{m-2}}+1)(a^{2^{m-2}}-1) = ...= ...(a^{2^{n}}+1)(a^{2^{n}}+1)$$ So we know, if some prime $p|a^{2^n}+1$, then it must be $p|a^{2^m}-1$.

Assume an integer $c_1$ such that $c_1p=a^{2^n}+1$

That is, $a^{2^m}+1=c_2p+2$.

So our question is actually $(c_2p+2,c_1p)$

By the Euclidean algorithm, that is $(cp,2)$

So when $cp$ is odd, that is, $a^{2^m}$ is even, meaning $a$ is even, $GCD=1$.

When $cp$ is even, that is, $a$ is odd, $GCD=2$.

Q5

Prove there are infinitely many primes.

Proof:

Consider $2^{2^n}+1$; for a prime, there is only one n allowing it to $p|2^{2^n}+1$.

So since $n$ are infinity many, there must be infinitely many primes.

Q7

Prove $\sqrt[n]{n!}\leq\prod_{p|n!}p^{1/(p-1)}$

Proof:

First: $$\text{ord}_pn!=\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\lfloor n/p^3\rfloor+...$$

$$\text{ord}_pn!\leq n(1/p+1/p^2+1/p^3...)=n/(p-1)$$

So, we have: $$n! \leq \prod_{p|n!}p^{n/(p-1)}$$ That is: $$\sqrt[n]{n!}\leq\prod_{p|n!}p^{1/(p-1)}$$

Q8

Prove there are infinitely many primes.

Proof:

By Q7, the left side can go to infinity when $n\to \infin$

So the right side should have infinity many terms, that is, infinitely many primes.

Q9

Show that a multiplicative function is completely determined by its value on prime powers.

Proof:

A function is multiplicative if $f(ab)=f(a)f(b)$ whenever $(a,b)=1$.

So: $$f(x)=f(\prod_i^{\infin}p_i^{a_i})$$

Q10

Prove that if $f(x)$ is multiplicative, then $g(x)=\sum_{d|x}f(d)$ is also multiplicative.

Proof:

Consider $n=ab$ where $a=\prod_{p\in S_a}p$ and $b=\prod_{p\in S_b}p$ . Here, $S_a,S_b$ are two set of primes unique to each other, also in length of $l_a,l_b$.

Then: $$g(a) = \sum_{i=0}^{l_a}f({l_a \choose i}) = \sum_{i=0}^{l_a}\prod_{p \in {l_a \choose i}} p$$

$$g(b) = \sum_{i=0}^{l_b}f({l_b \choose i}) = \sum_{i=0}^{l_b}\prod_{p \in {l_b \choose i}} p$$

So $$g(a)g(b) = \sum_{i=0}^{l_a+l_b}f({l_a+l_b \choose i}) = \sum_{i=0}^{l_a+l_b}\prod_{p \in {l_a+l_b \choose i}} p = g(ab)$$

Q11

Prove $\phi(n)=n\sum_{d|n}\mu(d)/d$ .

Proof:

By Q9 and Q10, we can first prove $\mu(d)/d$ multiplicative.

By definition:

$\mu(ab) = (-1)^{\nu(ab)} = (-1)^{\nu(a)+\nu(b)}$ as along as $(a,b)=1$.

So $$\frac{\mu(ab)}{ab} = \frac{\mu(a)}{a}\frac{\mu(b)}{b}$$ As same as in Theorem 2, $f(x) = x$ is multiplicative: $$n=\sum_{d|n}\phi(d) \implies \phi(d) = \sum_{d|n}\mu(d)\frac{n}{d} = n\sum_{d|n}\mu(d)/d$$

Q12

Find formulas for:

• $\sum_{d|n}\mu(d)\phi(d)$
• $\sum_{d|n}\mu(d)^2\phi(d)^2$
• $\sum_{d|n}\mu(d)/\phi(d)$

By Q11, they are all multiplicative: $$\mu(ab)\phi(ab) = (-1)^{\nu(ab)}ab\prod_{p|ab}(1-1/p) = \mu(a)\phi(a)\mu(b)\phi(b)$$ The rest two are the same.

So the result is determined by its primes powers (as in Q9)

Assume $G_1(n)=\sum_{d|n}\mu(d)\phi(d)$, and $n=\prod_{i=1}^{l}p_i^{a_i}$ $$G_1(n) = G_1(p_1^{a_1})G_1(p_2^{a^2})...G_1(p_l^{a^l})=\prod_{i=1}^{l}\mu(p_i)\phi(p_i)$$

$$G_1(n)=(1-p_1)(1-p_2)(1-p_3)...(1-p_l)$$

Assume $G_2(n)=\sum_{d|n}\mu(d)^2\phi(d)^2$ $$G_2(n) =\prod_{i=1}^{l}\mu(p_i)^2\phi(p_i)^2 = (p_1-1)^2(p_2-1)^2...(p_l-1)^2$$ Assume $G_3(n)=\sum_{d|n}\mu(d)/\phi(d)$ $$G_3(n)=\prod_{i=1}^{l}\mu(p_i)/\phi(p_i)=\frac{1}{1-p_1}\frac{1}{1-p_2}...\frac{1}{1-p_l}$$

Q13

Show $\sigma_k(n)=\sum_{d|n}d^k$ formula and prove that it is multiplicative.

Proof:

First prove $d^k$ is multiplicative. That $(ab)^k=a^kb^k$. So $\sigma_k(n)$ is multiplicative.

So $$\sigma_k(n)=\prod_{i=1}^lp_i^{({a_i}+k)}=n\prod_{i=1}^lp_i^k$$

Q15

Prove that $\sum_{d|n}\mu(n/d)\nu(d)=1$ and $\sum_{d|n}\mu(n/d)\sigma(d)=1$

Proof:

By Q10 use same way to prove that if $f(n)$ is multiplicative, then $h(n)=\sum_{d|n}\mu(n/d)f(d)$ is also multiplicative.

Then $$\sum_{d|n}\mu(n/d)\nu(d)=\prod_{i=1}^{l}(\mu(p_i^{a_i}/p_1^{a_i})\nu(p_i^{a_i})+\mu(p_i^{a_i}/p_i^{a_i-1})\nu(p_i^{a_i-1})) = \prod_{i=1}^{l}(a_i+1-a_i) = 1$$

$$\sum_{d|n}\mu(n/d)\sigma(d)=\prod_{i=1}^{l}(\sigma(p_i^{a_i})-\sigma(p_i^{a_i-1}))=\prod_{i=1}^{l}\frac{p_i^{a_i+1}-1-p_i^{a_i}+1}{p_i-1}=\prod_{i=1}^{l}p_i^{a_i}=n$$

Q16

Prove that $\nu(n)$ is odd iff n is a square.

Proof:

For $n=\prod_{i=1}^{l}p_i^{a_i}$ $$\nu(n)=\prod_{i=1}^{l}(a_i+1)$$ If $\nu(n)$ is odd, then every term of $(a_i+1)$ must be odd, that is, $a_i$ is even. So $n$ is a square.

Q17

Prove that $\sigma(n)$ is odd iff n is a square or twice a square.

Proof:

Still, assume $n=\prod_{i=1}^{l}p_i^{a_i}$ $$\sigma(n)=\prod_{i=1}^{l}\sum_{b_j=0}^{a_i}p_i^{b_j}$$ If $\nu(n)$ is odd, then every term shall be odd.

For each term, if $p\neq 2$, then $p$ must be odd. So there are $a_i+1$ odd number ($p^b$) summing up. To keep this term to be odd, $a_i+1$ must be odd, that is, $a_i$ is even, and n is a square.

If $p=2$, this term must be odd, so $n$ could be twice a square.

Q18

Prove that $\phi(m)\phi(n)=\phi((m,n))\phi([m,n])$

Proof:

Consider $m=p_m^2p_np_a, n=p_mp_n^2p_b$. Therefore, $(m,n)=p_mp_n,[m,n]=p_m^2p_n^2p_ap_b$. And $p_m,p_n,p_a,p_b$ are relatively prime. $$\phi([m,n]) =p_m\phi(p_m)p_n\phi(p_n)\phi(p_a)\phi(p_b)$$

$$\phi((m,n))=\phi(p_mp_n)=\phi(p_m)\phi(p_n)$$

$$\phi(m) = \phi(p_m^2p_np_a)=p_m\phi(p_m)\phi(p_n)\phi(p_a)$$

$$\phi(n) = \phi(p_n^2p_mp_a)=p_n\phi(p_m)\phi(p_n)\phi(p_a)$$

$$\text{lhs} = \phi(p_m)^2\phi(p_n)^2\phi(p_a)\phi(p_b)$$

$$\text{rhs} = \phi(p_m)^2\phi(p_n)^2\phi(p_a)\phi(p_b)$$

Q19

Prove that $\phi(mn)\phi((m,n))=(m,n)\phi(m)\phi(n)$

Proof: $$\text{lhs} = \phi(p_m^3p_n^3p_ap_b)\phi(p_mp_n)=p_m^2p_n^2\phi(p_m)^2\phi(p_n)^2\phi(p_a)\phi(p_b)$$

$$\text{rhs}=p_mp_np_m\phi(p_m)\phi(p_n)\phi(p_a)p_n\phi(p_m)\phi(p_n)\phi(p_a)=p_m^2p_n^2\phi(p_m)^2\phi(p_n)^2\phi(p_a)\phi(p_b)$$

So $\text{lhs}=\text{rhs}$

Q20

Prove that $\prod_{d|n}d=n^{\nu(n)/2}$

Proof:

For each $d|n$, there must be a $n/d|n$.

So there are $\nu(n)$ dividers, and there are $\nu(n)/2$ pairs of $d*n/d$.

So the result is $n^{\nu(n)/2}$

Q21

Define Von Mangoldt function $\Lambda(n)=\log{p}$ if n is a power of $p$, otherwise 0. Prove that $\sum_{d|n}\mu(n/d)\log{d}=\Lambda(n)$.

Proof:

First, assume $n=\prod_{i=1}^{l}p_i^{a_i}$ $$\sum_{d|n}\Lambda(d)=\sum_{i=1}^{l}\sum_{a=1}^{a_i}\log{p_i}=\log{(\prod_{i=1}^{l}p_i^{a_i})}=\log(n)$$ Then apply the Möbius inversion: $$\Lambda(n)=\sum_{d|n}\mu(n/d)\log{d}$$

Q22

Show that the sum of all integers $t$ such that $1\leq t\leq n$ and $(t,n)=1$ is $1/2 \cdot n\phi(n)$.

Proof:

For each $(t,n)=1$, there shall be a $(n-t,n)=1$ and obviously $1 \leq n-t \leq n$.

So we can pair up all relatively primes, the number of pair shall be $1/2 \phi(n)$ unless $t=n/2$. And each pair, on average, shall be $1/2*n$

So the sum of $t$ shall be $1/2*n\phi(n)$

Q23

For a function $f(x)$, define $\psi(n)$ as the number of $f(j), j=1,2,...,n$ such that $(f(j),n)=1$. Prove that $\psi(n)$ is multiplicative and $\psi(p^t)=p^{t-1}\psi(p)$.

Proof:

As same as the proof for $\phi(n)$, we can consider a series $\frac{f(1)}{n},\frac{f(2)}{n},...,\frac{f(n)}{n}$

We shall have same result: $$\sum_{d|n}\psi(d)=n$$ So by Möbius inverse: $$\psi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$$ That is $\psi(n)/n$ is multiplicative. So $\psi(n)$ is multiplicative by Q10.

For $\psi(p^t)$, the number of term remains $d|p^t$ the same, so $\psi(p^t)=p^t\sum_{d|p}\mu(p)=p^{t-1}\psi(p)$

Also, $$\psi(p^a)=1-1/p=\psi(p)$$ So by multiplicative: $$\frac{\psi(n)}{n}=\prod_{i=1}^{l}\frac{\psi(p^{a_i})}{p_i^{a_i}}=\prod_{p|n}\frac{\psi(p)}{p}$$

Q25

Riemann Zeta Function $\zeta(s)=\sum_{n=1}^\infin 1/n^s$. Prove the formal identity (Euler's Identity) $\zeta(s)=\prod_{p}(1-(1/p^s))^{-1}$

Proof:

Consider each n: $$n=\prod_{p}p^k$$ So the Zeta function actually are summing all different compositions of prime powers. $$\zeta(s)=\prod_p\sum_k\frac{1}{p^{ks}}$$ For each prime term, this is a sum of a geometric series: $$\sum_k\frac{1}{p^{ks}}=(1-\frac{1}{p^s})^{-1}$$ So: $$\zeta(s)=\prod_p(1-(1/p^s))^{-1}$$

Q26

Prove some identities.

• $\zeta(s)^{-1}=\sum_{n=1}^{\infin}\frac{\mu(n)}{n^s}$
• $\zeta(s)^2=\sum_{n=1}^{\infin}\frac{\nu(n)}{n^s}$
• $ \zeta(s)\zeta(s-1)=\sum_{n=1}^{\infin}\frac{\sigma(n)}{n^s}$

Proof:

Assume two function: $$F(s)=\sum_{n=1}^\infin\frac{f(n)}{n^s},G(s)=\sum_{n=1}^\infin\frac{g(n)}{n^s}$$ Consider Dirichlet convolution: $$F(s)G(s)=\sum_{n-1}^{\infin}\sum_{m-1}^{\infin}\frac{f(n)g(m)}{(mn)^s}= \sum_{mn=1}^{\infin}\frac{f*g(mn)}{(mn)^s}$$ Let $f(s)=1$ , then $F(s)=\sum_{n=1}^{\infin}\frac{1}{n^s}=\zeta(s)$.

Assume $h(s)=1*g(s)$ $$H(s)=\sum_{n=1}^{\infin}\frac{h(n)}{n^s}=F(s)G(s)=\zeta(s)\sum_{n=1}^\infin\frac{g(n)}{n^s}$$

$$h(n)=\sum_{d|n}g(d)$$

Let $g(n)=\mu(n)$: $$h(1)=\mu(1)=1$$

$$h(n)=\sum_{d|n}\mu(n) = 0$$ So: $$H(s)=1=\zeta(s)\sum_{n=1}^{\infin}\frac{\mu(n)}{n^s}$$

$$\zeta(s)^{-1}=\sum_{n=1}^{\infin}\frac{\mu(n)}{n^s}$$

Let $g(n)=n^0$: $$h(n)=\sum_{d|n}d^0=\nu(n)$$ Now, $G(s)=\zeta(s)$ $$\sum_{n=1}^{\infin}\frac{\nu(n)}{n^s} = \zeta(s)^2$$ This can be generalize to $g(n)=n^\alpha$​ $$h(n)=\sum_{d|n}d^\alpha = \sigma_\alpha(n)$$ When $\alpha=1$, its $\sigma(n)$​ $$\sum_{n=1}^{\infin}\frac{\sigma(n)}{n^s} = \zeta(s)\zeta(s-1)$$ More generally: $$\sum_{n=1}^{\infin}\frac{\sigma_\alpha(n)}{n^s} = \zeta(s)\zeta(s-\alpha)$$

Q27

Prove that $\sum1/n$ where n is square free integers, diverges.

Proof:

The sum is actually: $$\sum_{n=1}^{\infin}\frac{|\mu(n)|}{n} > \sum_{n=1}^{\infin}\frac{\mu(n)}{n} =\zeta(1)^{-1}$$

$$\zeta(1)^{-1} = \prod_{p<n}(1+1/p)$$

Take log: $$\log{\prod_{p<n}(1+1/p)}=\sum_{p<n}\log{(1+1/p)} < \sum_{p<n}1/p$$ So it diverge.