動機 #
別記事(🔗大きな数のmod)を書いている際に合同式に馴染みがなかったので、学習、整理する必要が生じたため。
合同式 #
$$ a \equiv b \mod n \iff \exists k \in \mathbb{Z}:\space a = b + kn $$
latexを書くのがめんどかったので一部は写真で。
合同式 推移 #
合同式 和と積 #
その他 #
\(a \equiv p^{x} \land b \equiv p^{y} \implies ab \equiv p^{x+y} \quad \mod n\) #
仮定より、
\(\exists k \in \mathbb{Z}: \space a = p^x + k n\)
\(\exists l \in \mathbb{Z}: \space b = p^y + l n\)
$$ ab = (p^x + kn )(p^y + ln) \\ ab = p^x \cdot p^y + (p^x l + k p^y + kln)n \\ ab = p^{x+y} + (p^x l + k p^y + kln)n \\ \therefore ab \equiv p^{x+y} $$