合同式は慣れるまでは大変ですが、慣れてしまえば非常に便利な道具となります。
まずは定義から始め、その基本性質から見ていきます。
・合同式の定義
\(a,b\)を整数、\(p\)を正の整数とする。
\(a-b\)が\(p\)の倍数のとき、\(a,b\)は\(p\)を法として合同であるといい、
\(a≡b\) (\(\mathrm{mod}\) \(p\))
と表します。このような式を合同式とよびます。
なお
\(a≡b\) (\(\mathrm{mod}\) \(p\))
\(\leftrightarrow\)
「\(a-b\)が\(p\)の倍数」
\(\leftrightarrow\)
「\(a\)を\(p\)で割った余り=\(b\)を\(p\)で割った余り」
・・・(※)
となります。
要するに、\(a≡b\) (\(\mathrm{mod}\) \(p\)) は、
両辺それぞれ\(p\)で割ったときの余りが等しいということです。
例えば\(8\)と\(14\)は\(3\)で割った余りが\(2\)で等しいため
\(8≡14\) (\(\mathrm{mod}\) \(3\))
が成り立ちます。
このように合同式は等式と異なる点もありますが、似たような性質もあります。
両辺それぞれ\(p\)で割ったときの余りが等しいということです。
例えば\(8\)と\(14\)は\(3\)で割った余りが\(2\)で等しいため
\(8≡14\) (\(\mathrm{mod}\) \(3\))
が成り立ちます。
このように合同式は等式と異なる点もありますが、似たような性質もあります。
(※)の2番目の矢印について。
(1)\(\rightarrow\) について
\(k,l,r,r’\) を整数として、
\(a=pk+r\), \(b=pl+r’\) とする。(\(0≦r<p\)), (\(0≦r'<p\))
\(k,l,r,r’\) を整数として、
\(a=pk+r\), \(b=pl+r’\) とする。(\(0≦r<p\)), (\(0≦r'<p\))
よって
\(a-b=p(k-l)+r-r’\)
\(a-b\)は\(p\)の倍数だから、\(r-r’\)も\(p\)の倍数。
\(a-b\)は\(p\)の倍数だから、\(r-r’\)も\(p\)の倍数。
ここで、\(-p<r-r'<p\) より、この範囲にある\(p\)の倍数は\(0\)。
ゆえに、\(r-r’=0\)
\(r=r’\)つまり「\(a\)を\(p\)で割った余り=\(b\)を\(p\)で割った余り」
\(r=r’\)つまり「\(a\)を\(p\)で割った余り=\(b\)を\(p\)で割った余り」
(2)\(\leftarrow\) について
\(a=pk+r\), \(b=pl+r\) (\(0≦r<p\)) だから
\(a-b=p(k-l)\)
よって\(a-b\)は\(p\)の倍数
よって\(a-b\)は\(p\)の倍数
・合同式の性質
\(a≡b\)(\(\mathrm{mod}\) \(p\)) , \(c≡d\)(\(\mathrm{mod}\) \(p\)) のとき
①和:\(a+c≡b+d\)(\(\mathrm{mod}\) \(p\))
②差:\(a-c≡b-d\)(\(\mathrm{mod}\) \(p\))
③積:\(ac≡bd\)(\(\mathrm{mod}\) \(p\))
④累乗:\(a^n≡b^n\)(\(\mathrm{mod}\) \(p\)) (\(n\)は自然数)
⑤関数:整数係数の\(x\)の整式\(f(x)\)について、
\(f(a)≡f(b)\)(\(\mathrm{mod}\) \(p\))
①～③は合同式の定義より証明できます。
また③が成り立つとき、\(c=a\),\(d=b\)として
\(a^2≡b^2\)(\(\mathrm{mod}\) \(p\))
さらに\(a=a^2\),\(b=b^2\)、\(c=a\),\(d=b\)として
\(a^3≡b^3\)(\(\mathrm{mod}\) \(p\))
さらに\(a=a^2\),\(b=b^2\)、\(c=a\),\(d=b\)として
\(a^3≡b^3\)(\(\mathrm{mod}\) \(p\))
以下繰り返すことで、
\(a^n≡b^n\)(\(\mathrm{mod}\) \(p\))
\(a^n≡b^n\)(\(\mathrm{mod}\) \(p\))
⑤は①～④の性質より成り立つことが分かります。
①～③より、等式のように両辺に余りが同じである数を、足したり引いたり掛けたりしてもよいことになります。
また式変形においては、\(d=c\)として、例えば①だと
\(a+c≡b+c\)(\(\mathrm{mod}\) \(p\))
なので、\(a\)→\(b\)と同じ余りの数にどんどん変換してもよいことになります。②～⑤も同様です。
また式変形においては、\(d=c\)として、例えば①だと
\(a+c≡b+c\)(\(\mathrm{mod}\) \(p\))
なので、\(a\)→\(b\)と同じ余りの数にどんどん変換してもよいことになります。②～⑤も同様です。
・合同式の除法(割り算)
除法については注意が必要です。
除法については注意が必要です。
\(ac≡bc\) (\(\mathrm{mod}\) \(p\)) のとき
\(c\)と\(p\)が互いに素のとき、
\(a≡b\) (\(\mathrm{mod}\) \(p\))
\(c\)と\(p\)が互いに素のとき、
\(a≡b\) (\(\mathrm{mod}\) \(p\))
(証明)
\(ac-bc=pk\) (\(k\)は整数)と表すことできる。
\(c(a-b)=pk\)で、\(c\)と\(p\)が互いに素であることから
\(a-b=pl\) (\(l\)は整数)と表すことできる。
\(c(a-b)=pk\)で、\(c\)と\(p\)が互いに素であることから
\(a-b=pl\) (\(l\)は整数)と表すことできる。
よって \(a≡b\) (\(\mathrm{mod}\) \(p\))
\(c\)と\(p\)が互いに素でない場合は、\(a-b\)が\(p\)の倍数になるとは限らないので、\(a≡b\) (\(\mathrm{mod}\) \(p\))とならない場合もあります。
例題を通して合同式の威力を見てください。
(例題)
次の数を\(7\)で割った余りはいくつか。
次の数を\(7\)で割った余りはいくつか。
(1)\(92×37\)
(2)\(8^{100}\)
(2)\(8^{100}\)
(解答)
(1)
\(92=7×13+1\), \(37=7×5+2\) なので
\(92≡1\) ,\(37≡2\) (\(\mathrm{mod}\) \(7\))
(1)
\(92=7×13+1\), \(37=7×5+2\) なので
\(92≡1\) ,\(37≡2\) (\(\mathrm{mod}\) \(7\))
よって
\(92×37≡1×2=2\) (\(\mathrm{mod}\) \(7\))
よって余りは\(2\)
\(92×37≡1×2=2\) (\(\mathrm{mod}\) \(7\))
よって余りは\(2\)
(2)
\(8≡1\) (\(\mathrm{mod}\) \(7\)) なので、
\(8^{100}≡1^{100}=1\) (\(\mathrm{mod}\) \(7\))
\(8≡1\) (\(\mathrm{mod}\) \(7\)) なので、
\(8^{100}≡1^{100}=1\) (\(\mathrm{mod}\) \(7\))
よって余りは\(1\)
\(8^{100}\)のようなとても計算できないような数でも、余りが簡単に求まりました。
以上になります。お疲れ様でした。
ここまで見て頂きありがとうございました。