COMP2711 Discrete Mathematical tools for Computer Science
Notation:
| Notation | Meaning |
|---|---|
| a | b | a divides b (b 可以比 a 整除) (b/a ∈ Z) |
Euclid’s Divison Theorem:
所有integer都可以用 a = dq + r 哩 represent // $a,q,r \in \mathbb{Z}$ & $d \in \mathbb{Z^+}$
a = dividend q d = divisor —————- q = quotient d | a r = remainder √ -————- r
Proof of Existence (By Contradiction):
Assume m is the smallest counter example of the predicate a = dq + r {m = nq + r}
< this part can be represent by m = nq + r > m < this part maybe some can, some can’t> <————————————————– m ++++++++++++++++++++++++++++++>
We want to put the m back into the range that is representable by m = nq + r, let say
when n > m: ie. 5 ÷ 10 $ m = n•0 + m $ 5 = 10 x 0 + 5
when m ≥ n: $m - n = nq + r$
$ m = nq + n + r $ $m = n(q + 1) + r ≈ nq’ + r$
$m = nq’ + r$ is contradict with the statement that m ≠ nq + r
so m can be represent by the a = dq + r
Proof of Uniqueness:
Assume q and r is not unique for a = dq + r so we can say: \(\begin{cases} a = dq_1 + r_1 & 0≤r_1≤d \\ a = dq_2 + r_2 & 0≤r_2≤d \end{cases}\) if (1) - (2) \(a-a = (dq_1 + r_1) - (dq_2 + r_2) \\ 0 = d(q_1 - q_2) + (r_1 - r_2) \\ r_2 - r_1 = d(q_1 - q_2)\) Remainder - Remainder must be smaller then d since $r ∈{0,1,2, … , d - 1}$:
$r_2 - r_1 < d$
then we can say $d(q_1 - q_2)$ is also smaller then d as $r_2 - r_1 = d(q_1 - q_2)$
$d(q_1 - q_2) < d$
LHS is smaller then RHS in integer context IFF $q_1 - q_2 = 0$ , So we can conclude that $q_1 = q_2$ and therefore $r_2 - r_1 = 0$ , $r_1 = r_2$
So every $a$ has a unique $d$ and $r$
Modular Arithmetic:
Lemma
| $a \mod m $ | $(a + bm) \mod m $ |
|---|---|
| $(a \mod mn) \mod n $ | $a \mod n$ |
| $( a + b ) \mod m$ | $((a \mod m ) + (b \mod m)) \mod m$ |
| $(ab \mod m) $ | $((a \mod m)(b \mod m)) \mod m$ |
Modular Arithmetic on $\mathbb{Z_m}$:
$\mathbb{Z_m} = {0,1,…,m-1}$
Symbol:
| $a +_m b$ | $(a + b) \mod m$ |
|---|---|
| $a \ •_m b$ | $(a \ •\ b) \mod m$ |
Properties:
| Associative | $(a +_m b) +_m c$ | $a+_m(b+_mc)$ |
|---|---|---|
| $(a•_mb)•_mc$ | $a•_m(b•_mc)$ | |
| Communative | $a+_mb$ | $b+_ma$ |
| $a•_mb$ | $b•_ma$ | |
| Distributive | $a•_m(b+_mc)$ | $(a•_mb)+_m(a•_mc)$ |
Additive Inverse:
All number have additive inverse
如果 $a \in \mathbb{Z_m}$ , 代表 $a < m$ , 因為 $a$ 只會係 ${0,1,…,m-1}$ and $a+_m0=a$ and $a•_m1=a$
$a \mod m$ <additive inverse> $-a \mod m$
$a + (-a \mod m ) = m$
$(a + (-a \mod m)) \mod m = 0$
Multiplicative inverse:
Not all number have mulitplactive inverse
係 $a \in \mathbb{Z_m}$ 嘅情況下，如果 $a•_m b = 1$ 咁 $b$ 就係 $a$ ge Multiplicative Inverse
$ab \mod m = 1$
Congruences:
a and b have Same Remainder when divided by m
Notation: $a\equiv b\ \ (\mod m)$ // 嗰 ( ) 好似一定要有
if $a\mod m = b \mod m$, then we can say $a\equiv b\ \ (\mod m)$
亦代表：
$m (a-b)$ // remainder 嗰part 相減左，$mq_1$ 同 $mq_2$ 都係 $m$ ge 倍數，所以可以比$m$ 整除 - $\exist t \in \mathbb{Z} (a = b + mt)$ // $ m(q_2 + t) + r_2$
Domain:
$+_m$ 同 $•_m $ 淨係可以係$\mathbb{Z_m}$ 入面用 ie. $0 ≤ a,b < m $
$\equiv$ 可以係成個 $\mathbb{Z}$ 入面用 ie. $0 ≤ a,b $ & $m \in \mathbb{Z^+}$
Corallary:
可以用當 $ a \mod m = b \mod m $ 嗰時 $a = b + mt$ 哩proof
if $a \equiv b (\ mod\ m)$ and $c \equiv d (\ mod\ m)$
- $a+c \equiv b+d(\ mod \ m)$
- $ac \equiv bd (\ mod \ m)$
- $a+c \equiv b + c(\ mod \ m)$
- $a - c \equiv b - c (\ mod \ m)$
- $ac \equiv bc (\ mod \ m)$
GCD:
Greatest Common Divisor, 可以除盡a 同 b最大嗰粒數
Relative Prime:
gcd(a,b) = 1
Euclidean Algorithm:
Let $a = bq + r$, when $a, b, q, r \in \mathbb{Z}$ then gcd(a,b) = gcd(b,r)
e.g: $$ gcd(252,198)
252 = 198 • 1 + 54
198 = 54 • 3 + 36
54 = 36 • 1 + 18
36 = 18 • 2 + 0\
\therefore gcd(252,198) = 18 $$
Extend GCD (Bézout’s Theorem):
gcd(a,d) = ay+dx
用返上面嗰個example: gcd(252,198)
By: \(\begin{cases} a = dq + r \\ x = y' - qx' \\ y = x'\\ \end{cases} \\\)
denote that x’ and y’ means old x and old y
| a | d | q | r | x | y |
|---|---|---|---|---|---|
| 252 | 198 | 1 | 54 | -5 | 4 |
| 198 | 54 | 3 | 36 | 4 | -1 |
| 54 | 36 | 1 | 18 | -1 | 1 |
| 36 | 18 | 2 | 0 | 1 | 0 |
$\therefore gcd(252,198) = 4 • 252 - 5• 198 = 18$
Multiplicative inverse:
如果 gcd(a,m) = 1, then $a^{-1}$ exist
Finding Inverse:
雖然話都係用extend GCD 去搵，但要記得 inverse of mod 係under damin $\mathbb{Z_m}$
again by extend GCD \(Find \ the\ inverse\ of \ 101\ modulo \ 4620:\\\\ gcd(101,4620)\\ 4620 = 101 • 45 + 75 \\ 101 = 75 • 1 + 26\\ 75 = 26 • 2 + 23\\ 26 = 23 • 1 + 3\\ 23 = 3 • 7 + 2\\ 3 = 2 • 1 + 1\\ 2 = 1 • 2 + 0\\ \therefore \ gcd(101,4620) = 1, inverse \ exists\)
| a | d | q | r | x | y |
|---|---|---|---|---|---|
| 4620 | 101 | 45 | 75 | 1601 | -35 |
| 101 | 75 | 1 | 26 | -35 | 26 |
| 75 | 26 | 2 | 23 | 26 | -9 |
| 26 | 23 | 1 | 3 | -9 | 8 |
| 23 | 3 | 7 | 2 | 8 | -1 |
| 3 | 2 | 1 | 1 | -1 | 1 |
| 2 | 1 | 2 | 0 | 1 | 0 |
inverse of 101 mod 4620 = x = 1601
Chinese Remainder Theorem:
(Sun-Tsu’s Problem 孫子，你有咩問題)
Let $m_1,m_2,..,m_n$ be pairewise relatively prime {$gcd(m_a,m_b) = 1$} and $\in \mathbb{Z} > 1$ and $a_1,a_2,…,a_n$ arbitrary integer $\in \mathbb{Z}$
$x \equiv a_1 (\mod m_1)$ $x \equiv a_2 (\mod m_2)$ … $x \equiv a_n (\mod m_n)$
has unique solution modulo $m = m_1m_2…m_n$ \(x = a_1M_1y_1+a_2M_2y_2+...+a_nM_ny_n\\ \\ a_n = r_n\\ \\ M_n = \frac{m_1•m_2•...•m_n}{m_n}\\ \\ y_n=inverse\ of M_n \\\) 都幾big brain
睇落就似鎖匙咁
x 係成條鎖匙， $m_n$係對應第幾個鎖匙凹位，$a_n$ 就係凹幾多咁
例子： \(x = a_1 \frac{m_1m_2m_3}{m_1}y_1 + a_2 \frac{m_1m_2m_3}{m_2}y_2 +a_3 \frac{m_1m_2m_3}{m_3}y_3\\\) 當我地mod $m_1$ 嗰時：
$\frac{m_1m_2m_3}{m_1}y_1$ 會變左做1 ， 因為 $y_1$ 係 $M_1$ ge inverse ，$M_1 • M_1^{-1} = 1$
而$a_2 \frac{m_1m_2m_3}{m_2}y_2$ 同 $a_3 \frac{m_1m_2m_3}{m_3}y_3$ 會變左做0， 因為 $\frac{m_1m_2m_3}{m_n}$ 入面上下會cancel out which 變成 $a_2m_1m_3y_2$ 同 $a_3m_1m_2y_2$ 係哩個moment，佢變左個 $m_1$ ge倍數，所以 mod $m_1$ 就變左0
| $x$ mod $m_n$ | equals |
|---|---|
| $m_1$ | $a_1$ |
| $m_2$ | $a_2$ |
| $m_3$ | $a_3$ |
Cryptography:
Modular exponentiation:
- $a^i \mod n = ((a\mod n)(a \mod n )……(a \mod n))\mod n$
- $a^{i+j} \mod n = ((a^i\mod n )(a^j \mod n))\mod n $
- $a^{ij}\mod n = ((a^i mod n)^j)\mod n$
Repeated Squaring Method:
let say we want to compute $a^n\mod m$ where $n$ is a large number
we can rewrite n in binary which = $(b_k…b_1b_0)_2$
e.g.: n = 50 = 110010 then \(a^{50} \mod m \\ a^{2^1 + 2^4 + 2^5} \mod m\\ (a^{2} \mod m • a^{16}\ \mod m • a^{32} \mod m )\mod m\) $a^{32} = (a^{16})^2 = ((a^{8})^2)^2 = (((a^{4})^2)^2)^2 = ((((a^{2})^2)^2)^2)^2$
and we know $a^{ij}\mod n = ((a^i mod n)^j)\mod n$
so we can recursively find the value we want and add them together to find $a^{50}$