模除｜剰余演算｜Modulo
- 2023.07.17
- Mathematics Modulo
Definition1WIKIPEDIA: Modulo
\begin{align}
& a \ \% \ n = r \\
& \text{或 } a \text{ mod } n = r \\\\
& \equiv a = nq + r; \quad q, r \in \mathbb{Z} \quad |r| < |n|
\end{align}
同餘關係 Congruence Relation2WIKIPEDIA: Congruence Relation
\begin{align}
& a \equiv b \quad ( \text{mod } n) \\
& \text{if } a \ \% \ n = b \ \% \ n
\end{align}
In programming languages
| 程式語言 | 演算子 | 餘數的符號（正負） |
| C (ISO 1999) | % / div | 與被除數相同 |
| C++ (ISO 2011) | % / div | 與被除數相同 |
| Java | % | 與被除數相同 |
| Python | % | 與除數相同 |
| math.fmod(x, y) | 與被除數相同 | |
| C# | % | 與被除數相同 |
Properties
Distributive 分配律
(a + b) % n = [(a % n) + (b % n)] % n
(a * b) % n = [(a % n) * (b % n)] % n
模倒數 Modular Multiplicative Inverse3WIKIPEDIA: Modular Multiplicative Inverse
$$ a \cdot a^{-1} = 1 $$
求模倒數
費馬小定理
If p is a prime number, ∀ a ∈ :
:ap ≡ a (mod p)
同乘 a-1 兩次:
ap⋅a-1⋅a-1 ≡ a⋅a-1⋅a-1 (mod p)
⇒ ap-2 ≡ a-1 (mod p)
⇒ a-1 ≡ ap-2 (mod p)
Last Updated on 2025/08/13 by A1go
