数a　合同式の基本(整数の性質)

こんにちは、もちもちの実です！

今回は合同式の基本について、解説していきます。

整数問題を解くにあたり、非常に大きな武器となることがあるので、是非覚えておきましょう。

1　合同式とは？

2つの整数a,bが、自然数nで割った余りがそれぞれ等しいとき、

a≡b(mod n)

と表し、「nを法とするとき、aとbは合同である。」という。

また、上記のように表される式を合同式と言う。

例えば、以下のような合同式が成り立つ。

12≡2(mod 3)

5≡-1(mod 6)

2　合同式の演算

加法、減法、乗法について

a≡b(mod n),c≡d(mod n)のとき、以下の式が成り立つ。

a+c≡b+d(mod n)…①

a-c≡b-d(mod n)…②

ac≡bd(mod n)…③

①～③全て等式に変換すると証明は簡単である。

a=nk1+r1,b=nk2+r1,c=nk3+r2,d=nk4+r2とおけばよい。

今回は都合上③のみ証明を行う。

ac=(nk1+r1)(nk3+r2)=n(nk1k3+k1r2+k2r1)+r1r2より、

ac≡r1r2(mod n)…(i)

また、bd=(nk2+r1)(nk4+r2)=n(nk2k4+k2r2+k4r1)+r1r2より、

bd≡r1r2(mod n)…(ii)

(i),(ii)より、ac≡bd(mod n)(証明終)

これは簡単に理解できるだろう。問題は除法(割り算)である。

(2)　除法について、　

m, nが互いに素であるとき

ma≡mb (mod mn)⇔ a ≡ b (mod n)…④

合同式の最も大きな弱点が除法である。

しかし、ほとんど使う機会は少ないので、ここでは、参考程度にとどめておく。

3　練習問題

[問題]pを素数とする。2p^2+1が素数であるとき、pの値を求めよ。

[答え]p=3

(1)p=2のとき
2p^2+1=9
よって素数でない

(2)p=3のとき、
2p^2+1=19
よって素数である

(3)p>3のとき、
pが素数→p≡±1(mod 3)
したがって、
2p^2+1≡2(±1)^2 +2=2×1+1=3≡0(mod 3)
また2p^2+1≧2×5^2+1>3
よって3の倍数かつ3ではないため、素数でない。

以上より、p=3

4　最後に

いかがでしたしょうか？
素数判定などといった余りに着目する問題では絶大な効果を発揮しますので覚えておきましょう！
以上です！

ご精読いただきありがとうございました！
それでは！

もちもちの実