# 資訊安全與基礎數論

## [Divisibility (整除特性)](https://zh.wikipedia.org/wiki/%E6%95%B4%E9%99%A4%E8%A7%84%E5%88%99)
### 符號
##
$\underbrace{a|b}_{\scriptsize念作\ b\ 能被\ a\ 整除}\iff az =b\ \ \ for\ \ \ some\ \ \ z\in\mathbb{Z}$
### 基本性質
##
$1.\ \ a|a\ , \ 1|a\ ,\ a|0$

$2.\ \ 0|a\iff a=0$

$3.\ \ a|b\iff −a|b\iff a|−b$

$4.\ \ a|b\ \ \land\ \ a|c\implies a|(b+c)$

$5.\ \ a|b\ \ \land\ \ b|c\implies a|c$

$6.\ \ a|1\implies a=\pm 1 \ ,\ \ \forall a\in\mathbb{Z}\ ,\ \ a|1\iff a=\pm 1$

$7.\ \ a|b\ \ \land\ \ b|c\implies a|(m\cdot b+n\cdot c)\ \ for\ \ some\ \ m,n\in\mathbb{Z}$

$8.\ \ \forall\ a,b\ \in\ \mathbb{Z}\ ,\ \ a|b\ \land\ b|a\iff a=\pm b$

---
## [算術基本定理 (Fundamental theorem of arithmetic)](https://zh.wikipedia.org/zh-tw/%E7%AE%97%E6%9C%AF%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86)
$Defination:\ \ Every\ \ nonzero\ \ integer\ \ {\bf\ \ n}=\pm p^{e1}_{1}\ \times \pm p^{e2}_{2}\ \times\ ...... \ \pm p^{er}_{r}\\ ,\ {\bf e_{1}\ ,e_{2}\ ......e_{r}}\in \mathbb{Z^+}\ \ ,\ \ \ {\bf p_{1}\ ,\ p_{2}\ ......p_{r}}\ \ \ \ are\ \ distinct\ \ prime$
##
### 定義: 任何非 $0$ ==整數 ${\bf n}$ ,== 除了本身是質數,皆可寫成 $2$ 個或以上==質數 ${\bf p}$ ,== 的乘積
### $eg:\ \ 1200 = 2^4\times3\times5^2$
---
## [帶餘除法 (又稱歐幾里得除法、除數法則) (Division with remainder property or Euclidean division)](https://zh.wikipedia.org/wiki/%E5%B8%A6%E4%BD%99%E9%99%A4%E6%B3%95)
$Defination:\ \ Let\ \ a,n\in\mathbb{Z}\ \ with\ \ n>0\ \ ,\ then\ \ there\ \ exist\ \ unique\ \ q,r\in\mathbb{Z}$ $\ such \ \ thate$ ==:$\ \ {\bf\underline{ a=q\cdot n+r}}$ ,==$\ \ and\ \ \ 0\le r\lt n$
##
定義: 給定兩個整數 ${\bf a\ ,n}$ 且 ${\bf n>0}$ , 則必存在唯一一對整數 ${\bf q\ , r}$ 其中 ${\bf 0\le r<n}$ , ==並稱整數 ${\bf q\ ,r}$ , 為 ${\bf a}$ 除以 ${\bf n}$ 的商與餘數; 且 ${\bf r=0}$ 的充要條件就是 ${\bf n|a}$ ,== 使得上面等式成立,帶餘除法一般表示為: ${\bf \ \displaystyle a\div q=n\dots r}$ 其中 ${\bf 0\le r<n}$ ==且 ${\bf q\ ,n}$ 互質($Relatively\ \ Prime\ -$ 定義: $gcd(a\ ,b)=1$ ), 如果不互質,則無反元素。==
##
##
==$由上圖知\ {\bf a=q\cdot n+r\implies gcd(a\ ,n)=gcd(n\ ,r)}$==$\\eg:\ gcd(70\ ,15)=gcd(15\ ,10)$
---
## [模數 (Moudular Arithmetic)](https://zh.wikipedia.org/zh-tw/%E6%A8%A1%E9%99%A4)
### 定義: 給定整數 $a\ , b\ ,q$ 且 $q>1\ ,$ 設: ==$a=qn+r\ \ \therefore\ \ r=a\ \ mod\ \ n\ \ \therefore\ \ r\equiv a\ \ (mod\ \ n)\ ,\ b=qp+r\ \ ,$== 其中 $0\le r<q\ \ ,$ 且 $\ r\ ,n\ ,p\in\mathbb{Z}\ \ ,$ $\ then\ \ \underbrace{a-b=q(n-p)+(r-r)}_{為上式\ a=qn+r\ 和\ b=qp+r合併}\ \ ,\ \ a-b=q(n-p)$ 則稱 $a$ 與 $b$ 同餘 , 記作:
### $a\equiv b(mod\ \ q)\ \ ,\ \ \underline{a \equiv b(mod\ \ q)}\iff q|(a-b)\ \ ,\\ a\equiv b(mod\ \ q)\implies q\cdot n =a-b\ \ ,\ n\in\mathbb{Z}\ (整除性,即\ a\ 和\ b\ 差\ n\ 倍)$

##
翻譯: $a$ 和 $b$ 除 $q$ 是同餘的,如果除 $5$ 有 $5$ 種可能,分別為: 整除,和同餘 $1$ 到同餘 $4$
### $eg\ (1.):8\equiv 1(mod\ \ 7)\ ;\ 102\equiv 2(mod\ \ 2)$
$eg\ (2.):5\equiv 0(mod\ \ 5)\ 整除\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6\equiv 1(mod\ \ 5)\ 餘\ 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 7\equiv 2(mod\ \ 5)\ 餘\ 2\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 8\equiv 3(mod\ \ 5)\ 餘\ 3\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9\equiv 4(mod\ \ 5)\ 餘\ 4$