本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
合同式の性質
$a\equiv b$，$c\equiv d$のとき，
- $a+c\equiv b+d\pmod{n}$
- $a-c\equiv b-d\pmod{n}$
- $ac\equiv bd\pmod{n}$
- $a^{k}\equiv b^{k}\pmod{n}$
が成り立つ。また，$n$を法として$ab\equiv ac$が成り立ち，$a$と$n$が互いに素であるとき，
- $b\equiv c\pmod{n}$
が成り立つ。$a$と$n$が互いに素でないとき，$a$と$n$の最大公約数を$g$とおくと，
- $b\equiv c\pmod{n/g}$
が成り立つ。
和・差・積に関しては通常の等号と同じような感覚で計算を進めることができます。一方，商に関しては割る数が法と互いに素であるという条件がつきますので，注意が必要です。
証明
和差積・べき乗・商の順番で証明していきます。
和差積
まず，1.〜3.を証明します。合同式の定義より，$a,b,c,d$は
a &= p_{a}n+q_{1}\\[0.7em]
b &= p_{b}n+q_{1}\\[0.7em]
c &= p_{c}n+q_{2}\\[0.7em]
d &= p_{d}n+q_{2}
\end{align}
と表せます。ただし，新しく導入した変数はすべて整数とします。すると，
a\pm c &= (p_{a}\pm p_{c})n+(q_{1}\pm q_{2})\\[0.7em]
&\equiv q_{1}\pm q_{2}\pmod{n}\label{和差_ac}
\end{align}
が成り立ちます。一方，
b\pm d &= (p_{b}\pm p_{d})n+(q_{1}\pm q_{2})\\[0.7em]
&\equiv q_{1}\pm q_{2}\pmod{n}\label{和差_bd}
\end{align}
が成り立ちます。式($\ref{和差_ac}$)と式($\ref{和差_bd}$)より，
a\pm c &\equiv b\pm d \pmod{n}
\end{align}
が示されました。同様に，
ac &= (p_{a}p_{c}n+p_{a}q_{2}+p_{c}q_{1})n+q_{1}q_{2}\\[0.7em]
&\equiv q_{1}q_{2}\pmod{n}\label{積_ac}
\end{align}
が成り立ちます。一方，
bd &= (p_{b}p_{d}n+p_{b}q_{2}+p_{d}q_{1})n+q_{1}q_{2}\\[0.7em]
&\equiv q_{1}q_{2}\pmod{n}\label{積_bd}
\end{align}
が成り立ちます。式($\ref{和差_ac}$)と式($\ref{和差_bd}$)より，
ac &\equiv bd \pmod{n}
\end{align}
が示されました。
べき乗
$a^{k}-b^{k}$の因数分解を用います。整数論の世界では，因数分解を用いて積の形に持ち込むことによって証明を行う流れは頻出です。
a^{k}-b^{k} &= (a-b)(a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1})\label{べき乗1}
\end{align}
したがって，$a^{k}-b^{k}$は$a-b$で割り切れます。いま，$n$を法として$a\equiv b$であることから，2.の合同式と差の関係を利用すると，
a-b\equiv 0\pmod{n}\label{べき乗2}
\end{align}
が成り立ちます。ゆえに，$a^{k}-b^{k}$は$n$で割り切れますので，$n$を法として$a^{k}\equiv b^{k}$が成り立ちます。
商
2.の合同式と差の関係を利用して与えられた条件を変形すると，
ab&\equiv ac&&\pmod{n}\\[0.7em]
ab-ac&\equiv 0&&\pmod{n}\\[0.7em]
a(b-c)&\equiv 0&&\pmod{n}\label{商1}
\end{alignat}
が得られます。ここで，$a$と$n$が互いに素である場合と互いに素でない場合を考えます。まず，$a$と$n$が互いに素である場合は，$b-c$が$n$の倍数となります。したがって，
b-c\equiv 0\pmod{n}
\end{align}
が成り立ちます。
$n$を法とする$a$の乗法逆元が存在するということです。
次に，$a$と$n$が互いに素でない場合を考えます。このとき，$a$と$n$の最大公約数$g$と用いて
a &= ga^{\prime}\\[0.7em]
n &= gn^{\prime}
\end{align}
と表されます。ただし，$g$が$a$と$n$の最大公約数であることから，$a^{\prime}$と$n^{\prime}$は互いに素となります。式($\ref{商1}$)にこれらを代入すると，
ga^{\prime}(b-c)\equiv 0\pmod{gn^{\prime}}
\end{align}
が得られます。すなわち，ある整数$k$が存在して
ga^{\prime}(b-c) &= gn^{\prime}\cdot k
\end{align}
が成り立ちます。すべての整数は$0$の約数であることから，任意の二つの整数の最大公約数は$0$ではありません。したがって，両辺を$g\neq 0$で割ると，
a^{\prime}(b-c) &= n^{\prime}\cdot k
\end{align}
が得られます。ここで，$a^{\prime}$と$n^{\prime}$は互いに素であることから，$b-c$は$n^{\prime}$の倍数となります。したがって，$n^{\prime}=n/g$に注意すると，合同式の定義より
b&\equiv c\pmod{n/g}
\end{align}
が成り立ちます。
参考文献
本稿の執筆にあたり参考にした文献は，以下でリストアップしております。
コメント