合同式の基本

\(a\equiv b\pmod m\) なら \(m\mid(a-b)\)、\(c\equiv d\pmod m\) なら \(m\mid(c-d)\) です。 よって \((a+c)-(b+d)=(a-b)+(c-d)\) も \(m\) の倍数なので、加法の性質が従います。

また \(ac-bd=a(c-d)+d(a-b)\) と変形すると、右辺はどちらの項も \(m\) の倍数です。 したがって \(ac\equiv bd\pmod m\) です。 べき乗は乗法の性質を繰り返し使えば示せます。

\(n\) が偶数なら \(n=2k\) なので \(n^2=4k^2\equiv0\pmod4\) です。 \(n\) が奇数なら \(n=2k+1\) なので \(n^2=4k(k+1)+1\equiv1\pmod4\) です。

\(7^2=49\equiv-3\pmod{13}\) なので \(7^4\equiv9\pmod{13}\)、 さらに \(7^6\equiv-1\pmod{13}\) です。 よって \(7^{12}\equiv1\pmod{13}\) となり、 \(7^{100}=7^{96}\cdot7^4=(7^{12})^8\cdot7^4\equiv9\pmod{13}\) です。

\(3\) で割って \(2x\equiv3\pmod5\) にできます。 ここで法も \(15\to5\) に下がる点が重要です。 \(2^{-1}\equiv3\pmod5\) より \(x\equiv9\equiv4\pmod5\) です。 したがって解は \(x=4,9,14\pmod{15}\) です。