---
tags: NTNU,CSIE,必修,Discrete Mathematics
title: Modular Arithmetic of Discrete Mathematics
description:
---
{%hackmd @NTNUCSIE112/S1VbPN1HU %}
# Modular Arithmetic
### Moodle Information
Reading assignment: 
Ch 4.1, 4.3, 4.4, 4.6.4-4.6.6

### Moodle Slide
{%pdf https://drive.google.com/file/d/19HaUEBl-eCded6TAI0QXvahu5Mvd4iKi/preview %}

---
### Modular Arithmetic

a % b = ?
5 % 3 = 2
5 % -3 = ?
-5 % 3 = ?

### Congruence Modulo
+ Given two integers $a$ and $b$, and a positive integer $m$, we say that $a$ is congruent to $b$ modulo $m$ if $m|(a-b)$ ($a\equiv b \pmod{m}$)
- e.g. $m= 5 ,\ a = 12,\ b = 27$
#### Propositions
- $a\equiv b \pmod{m}$, $c\equiv d \pmod{m}$
$\Rightarrow(a+c) \equiv (b+d) \pmod{m}$
##### $pf.$
> $\because a\equiv b \pmod{m},\ c\equiv d \pmod{m}$
$\therefore m|(a-b),\ m|(c-d)$
$\Rightarrow a-b=k_1m,\ c-d=k_2m,\ k_1,k_2\in\mathbb{Z}$
$(b+d) - (a+c) = (b-a) + (d-c) = -k_1m - k_2m = -(k_1+k_2)m$

---

- $a\equiv b \pmod{m}$, $c\equiv d \pmod{m}$
$\Rightarrow ac \equiv bd \pmod{m}$
##### $pf.$
> $a-b=k_1m,\ c-d=k_2m,\ k_1,k_2\in\mathbb{Z}$
> $\Rightarrow a=b+
> k_1m,\ c=d+k_2m$
> $\Rightarrow ac-bd = (b+k_1m)(d+k_2m)-bd$

#### Application

##### RSA
R：Rivest
S：Shamir
A：Adleman

- The public key is a pair of number$(N,e)$
The private key is a pair of numbers$(N,d)$
Encryption : $C$ = $F^e$ $mod$ $N$
Decryption : $F$ = $C^d$ $mod$ $N$

- Q1: What are n, e, and d?
- $n$: the product of two primes $p\ \&\ q$
- $e$: $gcd( e,\ (p-1)(q-1)) = 1$
- $d$: $ed \equiv 1 \pmod{r}, \ r = \phi(n) = (p - 1)(q - 1)$
- Theorem ( Bezout identity )
> For $a,b\in \mathbb{N}, if gcd(a,b)=d$
> then $\exists\ x,y \in \mathbb{Z}$ s.t. $ax + by = d$
- $pf.$
>(well-ordering principle:
> Any nonempty subset of $\mathbb{N}$ has a smallest element).
> Consider
> $S = \{ax+by|x,y\in\mathbb{Z},ax+by>0\}$
> By well-ordering principle, $S$ has a smallest element, say $d^* = ax^* +by^*$
> claim **1.** $d^*|a$, **2.** $d^*|b$, **3.** $\forall c \ c|a,\ c|b\rightarrow c|d^*$
> let $a = d^*, k+r, 0\leqslant r \leqslant d^*$
> $\Rightarrow r = a - d^*k$
> $\ \ \ \ \ \ \ = a - (ax^*+by^*)k$
> $\ \ \ \ \ \ \ = (1-x^*k)a+y^*kb=0\ (\because r \nleq d^* )$
> $\therefore d^*|a$
> 同理 $d^*|b$
> For **3.** , let $a = ck_1,b=ck_2, k_1,k_2\in\mathbb{N}$
> $d^* = ck_1x^*+ck_2y^*$
> $\ \ \ \ = c(k_1x^* + k_2y^*)$
> $\ \ \ \ \Rightarrow c|d^*$
- Q2: Why the message m can be recovered?

- Q3: Is RSA safe?

##### Theorem (Fermat's Little Theorem)
1636
> Let $p$ be a prime. Then $\forall a \in \mathbb{N}, \ gcd(a, p)=1 \implies a^{p-1} \equiv 1 \pmod{p}$

$pf.$
Consider $S = \{1, 2, 3, ..., p - 1\}$.
Multiply each element of $S$ by $a$
$\{a, 2a, 3a, ..., (p - 1)a\}$

claim: $\forall i<j, \ i\times a \not\equiv j\times a \pmod{p}$
if $i \times a \equiv j \times a \pmod{p}$,
then $p|(j-i)\times a$, which contradicts.

Consider $(a)(2a)...((p-1)a)=a^{p-1}(p-1)!$
$\implies a^{p-1} \times (p-1)! \equiv (p-1)! \pmod{p}$

lemma:
If $ac \equiv bc \pmod{d}$, and $gcd(c,d) = 1$, then $a \equiv b \pmod{d}$

$\implies a^{p-1} \equiv 1 \pmod{p}$

$c^d \equiv (m^e)^d$
<font color=darblue>($ed \equiv 1 \pmod{r}$)</font>
$= m^{ed} = m^{1 + rk}, \ k \in \mathbb{Z}$
$\equiv m(m^{k(p - 1)(q - 1)}) \pmod{n}$
<font color=darblue>($\ r = \phi(n) = (p - 1)(q - 1)$)</font>

$m^{k(p - 1)(q - 1)} \equiv (m^{p - 1})^{k(q - 1)} \equiv 1 \pmod{p}$

> $gcd( m, p)=1$
$C^d\equiv m \pmod{p}$
$gcd( m, q)=1$
$C^d\equiv m \pmod{q}$
$\Rightarrow C^d = pqk'+m$ [(The Chinese remainder theorom)](#####中國餘數定理-(The-Chinese-remainder-theorom))

##### 中國餘數定理 (The Chinese remainder theorom)
> $C^d=pqk' + m$
Let $m_1, m_2, ..., m_n$ be pairwise relatively prime positive integers greater than $1$, and $a_1, a_2, ..., a_n$ be arbitrary(任意的) integers.
Then:
$x\equiv a_1 \pmod{m_1}$
$x\equiv a_2 \pmod{m_2}$
.
.
.
$x\equiv a_n \pmod{m_n}$
has a unique solution modulo $\prod\limits_{i=1}^n m_i$ .

- e.g.
$x \equiv 2 \pmod{3}$
$x \equiv 3 \pmod{5}$
$x \equiv 2 \pmod{7}$
$x = 23, 128, 233...$

| 1 | 2 | 3 |
| ------------------------- | ------------------------- | ------------------------- |
| $X\equiv 1 \pmod{3}$ | $x\equiv 0$ | $x\equiv 0$ |
| $X\equiv 0 \pmod{5}$ | $x\equiv 1$ | $x\equiv 0$ |
| $X\equiv 0 \pmod{7}$ | $x\equiv 0$ | $x\equiv 1$ |
| $5*7*X_1\equiv 1 \pmod{3}$ | $3*7*X_2\equiv 1 \pmod{5}$ | $5*3*X_3\equiv 1 \pmod{7}$ |
特解＝$2*35*X_1 + 3*21*X_2+2*15*X_3$
- Uniqueness
- 令 $x_1\ x_2$ 為同餘方程式之解
- 知 $x_1\equiv x_2 \equiv 2 \pmod{3}$
- $\Rightarrow 3|(x_1 - x_2)$
- 同理 $5|(x_1 - x_2)$, $7|(x_1 - x_2)$
- $\Rightarrow x_1 - x_2 = 3\times 5\times 7 \times k, \ k \in \mathbb{Z}7$
- 一般解 = 特殊解 $+ k\prod\limits_{i=1}^n m_i$