基礎數論
\(MOD\)性質
性質1 \(a \equiv b\pmod k \Longleftrightarrow k \mid a - b\)
性質2 \(a \equiv b\pmod k\ \&\&\ c \equiv d\pmod k \Longleftrightarrow a + b = c + d(mod\ k)\)
性質3 \(a \equiv b(mod\ k)\ \&\&\ c \equiv d\pmod k \Longleftrightarrow ac = bd(mod\ k)\)
- \(a \equiv b\pmod k \Longleftrightarrow a^n \equiv b^n\pmod k\)
- \(a \equiv b\pmod k \Longleftrightarrow am \equiv bm\pmod k\)
Modulo(模除)
- \((a+b)\mod m = ((a\mod m) + (b \mod m)) \mod m\)
- \((a \cdot b)\mod m = ((a\mod m) \times (b \mod m)) \mod m\)
Lemma 1
我們在\(MOD\)性質3那邊有提到這個引理。 \(p\) is a prime \(\forall m, a, b\in \lbrace1,2,...,p-1\rbrace, a \equiv b\pmod k \Longleftrightarrow am \equiv bm\pmod k\)
Proof
而我們由性質1可知\(a \equiv b\pmod k \Longleftrightarrow k \mid a - b\) \(ma - mb \equiv 0\pmod k \Longleftrightarrow k \mid ma - mb\) 整理一下 \(m(a - b) \equiv 0\pmod k \Longleftrightarrow k \mid m(a - b)\)
費馬小定理(Fermat’s Little Theorem)
\(a^{p-1}\equiv 1{\pmod {p}}\)
PROOF:
根據\(mod\)的性質我們可以 \[ a \cdot 2a \cdot 3a \cdot (p-1)a \% p = 1 \cdot 2 \cdot 3 \cdot (p-1) \%p \] \[ (p-1)!\ \%p = (p-1)!a^{p-1} \% p \] 把\((p - 1)!\)除掉。 \[ a^{p-1}\equiv 1{\pmod {p}} \]
Reference
- https://hackmd.io/@701-Coder/N_theorems?fbclid=IwAR1Qxf4eEb5MG7iNDMwAXfYQf3uik5MH6rKCnfTp5BymwhPKMmxWqMGM0FY#Wilson%E2%80%99s-Theorem
- https://www.youtube.com/watch?v=0Bk1fyvGq3Y
- https://www.youtube.com/watch?v=eYjuqLfJeQc&t=37s