Number Theory

1 Divisibility

Let $a$ and $b$ be integers with $a \neq = 0$ . Then $a$ divides $b$ if there exists an integer $c$ such that $b = a c$

1.1 Theorem

$a ∣ b \land a ∣ c \to a ∣ (b + c)$
$a ∣ b \to \forall c \in Z a ∣ b c$
$a ∣ b \land b ∣ c \to a ∣ c$

1.2 Corollary

If $a$ , $b$ , $c$ are integers where $a \neq = 0$ , such that $a ∣ b$ and $a ∣ c$ , then $a ∣ (mb + n c)$ whenever $m$ and $n$ are integers

2 Euclid’s Division Theorem

For any $a \in Z$ , $d \in Z^{+}$ , there exist unique integers $q$ and $r$ , with $0 \leq r < d$ , such that $a = d q + r$

$r = a mod b$
$q = a div d$


$a$	dividend
$d$	divisor
$q$	quotient
$r$	remainder

3 Greatest Common Divisor

4 Chinese Remainder Theorem

Solving system of linear congerence

⎩ ⎨ ⎧ x \equiv a_{1} (mod m_{1}) x \equiv a_{2} (mod m_{2}) ⋮ x \equiv a_{n} (mod m_{n})

x = a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + \dots + a_{n} M_{n} y_{n}

M_{i} = \frac{m _{1} \times m _{2} \times \dots \times m _{n}}{m _{i}}

4.1 Non co-prime basis

Cite

https://www.youtube.com/watch?v=2L7__8_6YUg&pp=4AQB

5 Fermet’s Little Theorem

a^{p - 1} \equiv 1 mod p

6 RSA

The setup of RSA is as follows, where 5 is the encryption step and 6 is the decryption step, note that $(e, n)$ is the public key and $d$ is the private key

Choose $p$ and $q$ which are prime number (> 150 digits)
$n = pq$ and $T = (p - 1) (q - 1)$
Choose $e$ such that $g cd (e, T) = 1$
$d = e^{- 1} mod T$
$y = x^{e} mod n$
$x = y^{d} mod n$

🏡

Explorer

Number Theory

1 Divisibility

1.1 Theorem

1.2 Corollary

2 Euclid’s Division Theorem

3 Greatest Common Divisor

4 Chinese Remainder Theorem

4.1 Non co-prime basis

5 Fermet’s Little Theorem

6 RSA

Explorer

Table of Contents

Backlinks