Intro

This post is a very fast tour through elementary number theory. It consists mainly of lecture notes shrinked to a cheat sheet.

Linear Diophantine Equations

$$ax+by=c,\;a\neq 0,\;b\neq 0$$ (solvable $$\Leftrightarrow gcd(a,b)\mid c$$)

Let $$d:=gcd(a,b)=ax_0+by_0$$. Then the solutions are $$x=\frac{c}{d}x_0+\frac{b}{d}n,\;y=\frac{c}{d}y_0+\frac{a}{d}n$$ for all $$n\in\mathbb{Z}$$.

Perfect Numbers

$$n\in\mathbb{N}$$ is called perfect $$:\Leftrightarrow n=\sum\limits_{d\geq 1,\;d|n}^{n-1}$$.
$$\sigma(n):=\sum\limits_{d|n}d\Rightarrow n$$ is perfect $$\Leftrightarrow 2n=\sigma(n)$$.

$$n=p_1^{\alpha_1}\cdots p_r^{\alpha_r},\;p_i\in\mathbb{P}$$ for all $$i \Rightarrow \sigma(n)=\sigma(\prod\limits_{i=1}^{r}p_i^{\alpha_i}) =\prod\limits_{i=1}^{r}\sigma(p_i^{\alpha_i})=\prod\limits_{i=1}^{r}\frac{p_i^{\alpha_i+1}-1}{p_i-1}$$

$$n=2^{s-1}b$$ for all $$s\geq 2$$, b odd $$\Rightarrow$$ (n perfect $$\Leftrightarrow b\in\mathbb{P}\wedge b=2^s-1$$)

$$M_s:=2^s-1$$ for all $$s\geq 1$$: $$M_s$$ prime $$\Leftrightarrow: M_s$$ Mersenne prime $$\Rightarrow s\in\mathbb{P}$$

$$F_s:=2^s+1$$ for all $$s\geq 0$$: $$F_s$$ prime $$\Leftrightarrow: F_s$$ Fermat prime $$\Rightarrow \exists t\in\mathbb{N}:s=2^t$$ (Proof through geometric series)

The Totient Function

$$\varphi(n):=\lvert \mathbb{Z}_n^*\rvert$$

Euler’s theorem: $$k,n\in\mathbb{N}_{>0},\;gcd(k,n)=1\Rightarrow k^{\varphi(n)}\equiv 1\;(mod\;n)$$ (Proof by observation in $$\mathbb{Z}_n^*$$)

Fermat’s little theorem: $$k\in\mathbb{N}_{>0},\;p\in\mathbb{P}\Rightarrow k^p\equiv k\;(mod\;p)$$.

It follows that $$n\in\mathbb{P}\Rightarrow\forall k\in\{1,\cdots ,n-1\}:k^{n-1}\equiv 1\;(mod\;n)$$.

$$n\in\mathbb{Z}$$ is called Carmichael number $$:\Leftrightarrow\;(\forall a:gcd(a,n)=1\Rightarrow a^{n-1}\equiv 1\;(mod\;n))$$

Computing $$\varphi(n)$$

$$n=\sum\limits_{d|n}\varphi(d)$$

$$p\in\mathbb{P}\Rightarrow\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}$$ (Proof by Induction)

$$\varphi(n\cdot m)=\varphi(n)\cdot\varphi(m)$$ (Proof by induction over $$n\cdot m$$)

Similar to chinese remainder theorem: $$\mathbb{Z}_{nm}^*\cong\mathbb{Z}_{n}^*\times\mathbb{Z}_{m}^*$$

and thus $$\varphi$$ can be computed as $$\varphi(n)=n\cdot\prod\limits_{p\mid n,\;p\in\mathbb{P}}(1-\frac{1}{p})$$

Multiplicative Functions

$$\psi:\mathbb{N}_{>0}\rightarrow\mathbb{R}$$ is called multiplicative $$:\Leftrightarrow \psi(nm)=\psi(n)\cdot\psi(m)$$ for all $$n,m\in\mathbb{N}$$ with $$gcd(n,m)=1$$

$$\sigma,\varphi$$ multiplicative

$$$$o(n):=\begin{cases} 1, & n=1\\ 0, & else\\ \end{cases}$$$$ is multiplicative

$$e(n):=1$$ multiplicative, $$i(n):=n$$ multiplicative

$$f$$ multiplicative $$\Rightarrow f(1)=1\vee \forall n\in\mathbb{N}:f(n)=0$$

$$f, g$$ multiplicative $$\Rightarrow (f\cdot g)(n):=f(n)\cdot g(n)$$ multiplicative

We define the Dirichlet convolution for $$f,g:\mathbb{N}\rightarrow\mathbb{R}$$ as $$(f\star g)(n):=\sum\limits_{d\mid n}f(d)\cdot g(\frac{n}{d})$$

Dirichlet convolution: commutative, associative, $$o$$ is the neutral element

$$f, g$$ multiplicative $$\Rightarrow f\star g$$ multiplicative

$$\mu:\mathbb{N}\Rightarrow\mathbb{R},\; $$\mu(n):=\begin{cases} (-1)^r, & n=p_{1}\cdots p_{r} \text{ is squarefree} \\ 0, & \text{ else} \\ \end{cases}$$$$ is multiplicative.

$$f:\mathbb{N}_{>0}\rightarrow\mathbb{R},\;F(n):=\sum\limits_{d\mid n}f(d)=(f\star e)(n)$$ summation function of $$f$$

We have the following identities: $$\varphi\star e=i,\quad i\star e=\sigma,\quad\mu\star e=o,\quad o\star e=e,\quad \frac{\mu}{i}\star e=\frac{\varphi}{i}$$

$$e\star e=\tau,\;\tau(n):=\sum\limits_{d \mid n} 1$$ the number of factors

The Diophantine Equation $$x^2+y^2=p$$

Every polynomial that is not constant has roots modulo infinitely many primes (Idea of proof $$f(p_{1}\cdots p_{r}a_0x)=a_0g$$)

$$p\in\mathbb{P}$$ odd: $$x^2+1\equiv 0\;(mod\;p)$$ is solvable $$\Leftrightarrow p\equiv 1\;(mod\;4)$$ (Idea of proof: $$1\equiv(\alpha^2)^{\frac{p-1}{2}}\;(mod\;p)$$)

It follows that there are infinitely many primes of the form $$p\equiv 1\;(mod\;4)$$.

Wilson’s Theorem

Let $$K$$ be a field, $$\alpha$$ a zero of $$f\in K[X]$$. Then $$\Rightarrow (\alpha-x)\mid f$$ (Idea of proof: $$f=q(x-\alpha)+r,\;deg(r)<deg(x-\alpha)$$)

$$f\in K[X],\;deg(f)=n\Rightarrow f$$ has at most $$n$$ zero points.

Wilson: $$p\in\mathbb{P}\Rightarrow (p-1)!\equiv -1\;(mod\;p)$$ (Idea of proof: $$x^{p-1}-1\in\mathbb{Z}_p[X]$$ and Euler)

Primes as Sum of Two Square

$$x,y\in\mathbb{Z}$$ with $$x^2+y^2=p\in\mathbb{P}\setminus\{2\}\Rightarrow gcd(x,p)=gcd(y,p)=1$$

$$x,y\in\mathbb{Z}$$ with $$x^2+y^2=p\in\mathbb{P}\setminus\{2\}\Leftrightarrow p\equiv 1\;(mod\;4)$$ (Idea of proof: Fermat’s theorem)

Thue’s lemma: $$a\in\mathbb{Z}\;,n\in\mathbb{N}$$ is not square $$\Rightarrow ax\equiv y\;(mod\;n)$$ has a solution $$(x,y)\neq(0,0)$$ with $$\lvert x\rvert,\;\lvert y\rvert <\sqrt{(n)}$$

The Group of Units in $$\mathbb{Z}_n$$

$$\lvert G\rvert=n$$

$$\forall d\mid n\exists\varphi(d)$$ elements of order d $$\Leftrightarrow$$ G is cyclic.

$$K$$ field, $$G\leq K^*$$ subgroup, $$\lvert G\rvert=n<\infty\Rightarrow$$ G is cyclic (Idea of proof: $$x^d-1$$)

$$a \in\mathbb{N}$$ is a primitive root modulo $$n:\Leftrightarrow\overline{a}\in\mathbb{Z}_n^*$$ with $$o(\overline{a})=\varphi(n)$$, therefore $$\mathbb{Z}_n^*=\langle\overline{a}\rangle$$

$$\alpha\geq 3 \Rightarrow$$ there is no primitive root modulo $$2^\alpha$$, since $$a^{2^{\alpha-2}}\equiv1\;(mod\;2^\alpha)$$

$$\forall p\in\mathbb{P}\setminus\{2\}:\;\mathbb{Z}_{p^\alpha},\;\mathbb{Z}_2,\;\mathbb{Z}_4\;\mathbb{Z}_{2p^\alpha}$$ is cyclic.

The Legendre Symbol

$$a\in\mathbb{Z},\;gcd(a,n)=1$$ is called quadratic residue modulo $$n:\Leftrightarrow x^2\equiv a\;(mod\;n)$$ is solvable

$$\mathfrak{R}:=\{\overline{a}\in\mathbb{Z}_p^*:\, a$$ is a quadratic residue mod p$$\}\leq\mathbb{Z}_n^* \quad\lvert \mathfrak{R}\rvert=\frac{p-1}{2}$$

$2\neq p\in\mathbb{P},\;a\in\mathbb{Z}$

Definition of the Legendre symbol $$$$\left(\frac{a}{p}\right):=\begin{cases} 1,&gcd(a,p)=1,\text{ a is a quadratic residue mod p}\\ -1,&gcd(a,p)=1,\text{ a is a quadratic nonresidue mod p}\\ \end{cases}$$$$

The Legendre symbol has the following properties:

• $a\equiv b\;(mod\;p)\Rightarrow \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
• $\left(\frac{a\cdot b}{p}\right)=\left(\frac{a}{p}\right)\cdot\left(\frac{b}{p}\right)$
• $\left(\frac{a^2}{p}\right)=1\Leftrightarrow p\nmid a$
• $\left(\frac{2}{p}\right)=1\Leftrightarrow p=\pm 1\;(mod\;8)$
• Euler: $$\left(\frac{a}{p}\right)=a^{\frac{p-1}{2}}$$

Law of Quadratic Reciprocity: Let $$2\neq p,q\in\mathbb{P},\;p\neq q:$$. Then

$$$\left(\frac{p}{q}\right)\cdot\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} =\begin{cases} -1, & p\equiv q\equiv 3\;(mod\;4) \\ 1, & else \\ \end{cases}$$$ $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ $$$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}} =\begin{cases} 1, & p=\pm1\;(mod\;8) \\ -1, & p=\pm3\;(mod\;8) \\ \end{cases}$$$

The Diophantine Equation $$x^2-my^2=\pm p$$

$$gcd(p,k,m)=1,\;2\neq p\in\mathbb{P},\;x^2-my^2=kp$$ solvable $$\Rightarrow(\frac{m}{p})=1$$

$$x^2+2y^2=p,\;2\neq p\in\mathbb{P}$$ solvable $$\Leftrightarrow p\equiv1,\;3\;(mod\;8)\Leftrightarrow(\frac{-1}{p})=1$$

05 March 2022

Lesson