基礎數論
\(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)\)
