Number Theory

Theorem Euclid

NOTE

For all integers $a$ and $d\ne 0$ there exist unique integers $q$ and $r$ satisfying

$$a=dq+r\text{ and }0\le r<|d|$$

• $a$ is the dividend
• $d$ is the divisor
• $q$ is the quotient
• $r$ is the remainder

$r$ or the remainder is denoted as $R_d(a)$

For $a,b$ with $a\ne 0$ or $b\ne 0$ is a g.g.T. an element $d$ with $(d|a)\wedge (d|b)\wedge (\forall c(c|a)\wedge (c|b)\to (c|d))$ $gcd(a,b)$ is the unique positive g.g.T. from $a$ and $b$

NOTE

$gcd(m,R_m(n))=gcd(m,,n)$

Ideal

Definition

$(a,d)\stackrel{def}{=}\{ua+vb|u,v\in \mathbb{Z}\}$ $(a)\stackrel{def}{=}\{ua|u\in \mathbb{Z}\}$

Lemma 4.3

For $a,b\in \mathbb{Z}$ , $a$ and $b$ are not both 0, then $(a,b)=(gcd(a,b))$ Proof: $(a,b)\subseteq (d)$

Ideal-generator.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

0

a

b

a

b

Link to original

Sei $a,b$ so, dass $a\ne 0$ oder $b\ne 0$, und $d\in (a,b)$ das kleinste positive Element in $(a,b)$. Dann $d=u^{\ast }a+v^{\ast }b$ $d|a$ und $d|b$ (wenn z. B. )

• for all $c$ with $c|a$ and $c|b$

$(d)\subseteq (a,b)$

• finish the proof

Corollary 4.5

NOTE

For $a,b\in \mathbb{Z}$, there exist $u,v\in \mathbb{Z}$ such that $gcd(a,b)=ua+vb$

Theorem 4.6 prime factorization

Discrete Mathematics ETH, p.80

Every positive integer can be written uniquely (up to the order in which factors are listed) as the product of primes.

Example

$x^3+x^2=y^4+y+1$ left side is always even, right is always odd The equation hat no solution in $\mathbb{Z}$ $x^3-x=y^2+1$ left side divisible by 3, the right side cannot be divisible by 3

Modular Arithmetic

$a{\equiv }_{m}b\stackrel{def}{⟺}m|(a-b)$

• $a=b⟹a{\equiv }_{m}b$
• $⟺R_m(a)=R_m(b)$

Define ${\mathbb{Z}}_m=\{0,\dots ,m-1\}$

Example

$2^{20}{\equiv }_{15}(2^4{)}^5{\equiv }_{15}{1}^5{\equiv }_{15}1$

Multiplicative Inverses

$ax{\equiv }_{m}1$ The equation has a solution $x\in {\mathbb{Z}}_m$ if and only if $\text{gcd}(a,m)=1$. The solution is unique

This unique solution $x\in {\mathbb{Z}}_m$ is called the multiplicative inverse of $a$ modulo $m$

Example

$5^{-1}{\equiv }_{13}8$ because $5\cdot 8{\equiv }_{13}1$

CRT

Chinese Remainder Theorem (CRT)

Generally

NOTE

Let $m_1,m_2,\dots ,m_r$ be pairwise relatively prime integers and let $M={\prod }_{i=1}^r{m}_i$. For every list $a_1,\dots ,a_r$ with $0\le a_i<m_i$ for $1\le i\le r$, the system of congruence equations

$$\{\begin{array}{l}x{\equiv }_{m_1}{a}_1\\ x{\equiv }_{m_2}{a}_2\\ \dots \\ x{\equiv }_{m_r}{a}_r\end{array}$$

has a unique solution $x$ satisfying $0\le x<M$

Case: r=2

NOTE

Let $n_1$​ and $n_2$​ be two positive integers that are coprime ($\gcd (n_1,n_2)=1$). Then for any pair of residues $a_1$​ and $a_2$​, the system

$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{n}_1),\\ x\equiv a_2(\mathrm{mod}{n}_2),\end{array}$ has a unique solution modulo $M=n_1{n}_2$.

A simple constructive example

$\{\begin{array}{l}x\equiv 2(\mathrm{mod}3),\\ x\equiv 3(\mathrm{mod}5),\end{array}$ $M=3\ast 5=15$ $M_i=M/n:$ $M_1=15/3=5,M_2=15/5=3$ Find the modular inverse: $M_i{N}_i{\equiv }_{m_i}1$ $N_1:5N_1\equiv 1(\mathrm{mod}3)⟹N_1=2$ $N_2:3N_2\equiv 1(\mathrm{mod}5)⟹N_2=2$ Switch the parts together: ($r=2$ the number of equations) $x{\equiv }_{15}{\sum }_{i=1}^r{a}_i{M}_i{N}_i{\equiv }_{15}{a}_1{M}_1{N}_1+a_2{M}_2{N}_2{\equiv }_{15}2\ast 5\ast 2+3\ast 3\ast 2=38{\equiv }_{15}8(mod15)$ $x=8+15k,k\in \mathbb{N}$

Link to original