# 模運算
## infro
模為Mod的音譯，Mod的涵義為求餘數
7 Mod 3 為 1

## 性質
給定一正整數$p$，任意一個整數$n$，則一定存在等式$n = kp + r$
k, r 屬於整數，且$0 ≤ n < p$，k為n除p的商，r為n除p的餘數
## 基本概念
- $a\ \%\ p$ 或 $a\ mod\ p$ $\implies$表示a除以p的餘數

- $a\equiv b\ \%\ p$ 或 $a ≡ b\ (mod\ p)$$\implies$同餘式，表示a除p和b除p的餘數一樣

- $p\ =\ a\ -\ b$ 則 $a ≡ b\ \%\ p$

- $a\ \%\ p = b \%\ p$ 則 $a ≡ b\ \%\ p$

- $a ≡ b\ \%\ p$ 則 $b ≡ a\ \%\ p$

- $a ≡ b\ \%\ p$ 且 $b ≡ c\ \%\ p$ 則 $a ≡ c\ \%\ p$

- $n\ \%\ p$的正負由被除數n決定 ex:7 % 3 = 1， -7 % 3 = -1， 7 % -3 = 1， -7 % -3 = -1
java、C/C++使用上述規則。但在python，結果的正負僅與除數有關

## 運算
- $(a\ +\ b)\ \%\ p\ =\ (a\ \%\ p\ +\ b\ \%\ p)\ \%\ p$

- $(a\ -\ b)\ \%\ p\ =\ (a\ \%\ p\ -\ b\ \%\ p)\ \%\ p$

- $(a\ *\ b)\ \%\ p\ =\ (a\ \%\ p\ *\ b\ \%\ p)\ \%\ p$

- 沒有除法

- $(a\ {}^\land \ b)\ \%\ p\ =\ ((a\ \%\ p)\ {}^\land\ b)\ \%\ p)$

- $((a\ +\ b)\ \%\ p\ +\ c)\ \%\ p\ =\ (a\ +\ (b\ +\ c)\ \%\ p)\ \%\ p$

- $((a\ *\ b)\ \%\ p\ *\ c)\%\ p\ =\ (a\ *\ (b\ *\ c)\ \%\ p)\ \%\ p$

- $((a\ +\ b)\ \%\ p\ *\ c)\ \%\ p\ =\ ((a\ *\ c)\ \%\ p\ +\ (b\ *\ c)\ \%\ p)\ \%\ p$

- $a ≡ b\ \%\ p$，則 $(a\ +\ c) ≡ (b\ +\ c)\ \%\ p$ ，c為任意數

- $a ≡ b\ \%\ p$，則對於任意的正整數c，都有$(a\ *\ c) ≡ (b\ *\ c)\ \%\ p$，c為任意正整數
- $a ≡ b\ \%\ p$ 且 $c ≡ d\ \%\ p$，則 $(a\ +\ c) ≡ (b\ +\ d)\ \%\ p$