Number Theory Revise 2

Continuing from the previous post from here.

Another memory lane of theorem I want to prove/try!

Book Reffered: David Burton, Elementary Number Theory

Problem 1: $$p_n<2^{2^{n-1}}$$

Proof: Note that $$p_{n+1}\le p_1p_2\dots p_n+1\le 2\cdot \dots 2^{2^{n-1}}=2^{2^{n-1}}$$

Problem 2: If the $n>2$ terms of the arithmetic progression

$$p,p+d, p+2d,\dots,p+(n-1)d$$

are all primes then the common difference $d$ is divisible by every prime $q<n.$

Proof: If not then there exists a $q$ such that $(d,q)=1, q<n.$ But then we can get a $r$ such that $p\equiv -rd\mod q.$

Problem 3: Let $p_n$ denote the $n$ th prime. For $n>3$ show that $$p_n<p_1+p_2+\dots p_{n-1}.$$

Proof: Use induction and Bertrand's postulate.

We get that $$p_{n+1}<2p_n<p_1+p_2+\dots p_{n-1}+p_n.$$

I should try to prove FLT and Wilson on my own too! But lemme state them in problems format. Anyways..

Problem4: If $n=a^2+b^2=c^2+d^2$ then $$n=\frac{(ac+bd)(ac-bd)}{(a+d)(a-d)}$$

Proof:  Note that $$\frac{(ac+bd)(ac-bd)}{(a+d)(a-d)}=\frac{a^2c^2-b^2d^2}{a^2-d^2}$$

$$=\frac{a^2c^2+b^2c^2-b^2c^2-b^2d^2}{a^2-d^2}= \frac{a^{2}(c^{2} - b^{2})}{a^{2} - d^{2}} + b^{2}=n$$

Problem5:  If $p$ is a prime and $p\nmid a$ then $a^{p-1}\equiv 1\mod p.$

Proof: Note that $\{a,2a,\dots, (p-1)a\}\equiv \{1,2,\dots,p-1\}.$

Then $a^{p-1}\cdot (p-1)!\equiv (p-1)!\mod p\implies a^{p-1}\equiv 1\pmod p.$

Problem6: If $p$ is a prime, then $$(p-1)!\equiv -1\pmod p$$

Proof: Note inverse of $a$ is unique $\pmod p$ and $a^2\equiv 1 \pmod p$ has two solutions $1,p-1.$

So $$2\cdot 3\cdot \dots (p-2)\equiv 1\pmod p\implies (p-1)!\equiv -1\pmod p$$

Problem7: The quadratic congruence $x^2+1\equiv 0\pmod p$ where $p$ is an odd prime, has a solution if and only if $p\equiv 1\pmod 4.$

Proof: Since $x^2\equiv -1\pmod p.$

Now $$x^{p}\equiv -1^{p-1/2}\pmod p\implies 2|\frac{p-1}{2}\implies 4|p-1.$$

Note that $\left(\frac{p-1}{2}! \right)^2=(p-1)!.$

Problem8: If $f$ is a multiplicative function and $F$ is defined by $$F(n)=\sum_{d|n}f(d)$$
then $F$ is also a multiplicative function.

Proof: Let $(m,n)=1.$

$$F(mn)=\sum_{d|mn}f(d)=\sum_{d_1|m,d_2|n}f(d_1d_2)$$

$$=\sum_{d_1|m}f(d_1)\sum_{d_2|n}f(d_2)$$

$$=F(m)\cdot F(n)$$

Define:  For a positive integer $n,$ define $\mu$ by the rules,

$\mu(n)=$ $1$ if $n=1, 0$ if $p^2|n, (-1)^r$ if $n=p_1p_2\dots p_r$

It's called the mobius inversion function. Btw it's multiplicative.

Problem9: Prove that $\mu$ is multiplicative.

Proof: We just have to show that $\mu(mn)=\mu(m)\mu(n)$ with $\gcd(m,n)=1.$

If $p^2|m\implies \mu(m)=0,\mu(mn)=0.$ ( as $p^2|mn$)

If $\mu(m)=(-1)^r,\mu(n)=(-1)^s.$ As $\gcd(m,n)=1\implies \mu(mn)=(-1)^{r+s}.$

Problem 10: Prove that  for each integer $n>1$ 

$$F(d)=\sum_{d|n}\mu(d)=0 \forall n >1$$

Proof: It's  enough to show $F(p^k)=0$ for all prime $p.$

But $$F(p^k)=\sum_{d|p^k}\mu(d)=\mu(1)+\mu(p)+\mu(p^2)+\dots+\mu(p^k)=0$$

Last problem which is again mobius inversion formula.. Which was so confusing :pleading:

Problem 11:   $$F(n)=\sum_{d|n} f(d) \implies f(n)=\sum_{d|n}\mu(d)F(n/d)$$

Proof:  $$\sum_{d|n}\mu(d)F(n/d)=\sum_{d|n}\mu(d)\sum_{c|n/d} f(c)$$

$$=\sum_{d|n}\sum_{c|n/d} \mu(d)f(c)$$

Note that $c|n, d|n/c.$

$$=\sum_{d|n/c}\sum_{c|n} \mu(d)f(c) = \sum_{c|n}\sum_{d|n/c}\mu(d)f(c)=f(n)$$

As $\sum_{d|n/c}\mu(d)=0\forall n > 1.$


Next is primitive roots and heavy NT!

See you soon!

Sunaina💜