合同式の基本 a≡b (mod p)

スポンサーリンク
2整数a,\ bをpで割ったときの余りが等しいとき いくつか例を示す.\ 合同式から意味を読み取れるようになろう. \ 22≡15≡1 od7 (22も15も7で割ったときの余りは1である)  \ つまり,\mod7の世界では,\ 22,\ 15,\ 1は同じものとみなせるのである. \ 23≡3≡-1od4 (23を4で割ったときの余りは3,\ -1である)  \ 多くの問題では,\ より{絶対値が小さい剰余にする}と計算が楽になる.  \ よって,\ {負の剰余}を導入して考えることにも慣れる必要がある.  \ 整数0~12をmod}4でみるとこの表のようになる.  \ mod}4でみたとき,\ {余り3を-1と考えることもできる}のである.  \ もちろん余り2を-2と考えることもできるが,\ わざわざ負にする必要はない. また,\ {合同式の様々な言い換え}をおさえておく. a-bがpで割り切れる」} 「a-b=pkとなる整数kがある」} a=b+pkとなる整数kがある」} 和の余りは,\ 余りの和}) \差の余りは,\ 余りの差}) 積の余りは,\ 余りの積}) これらの合同式の性質の意義を理解しよう. 和ならば,\ 24+57=81を7で割って余り4とするのもそこまで難しくない. しかし,\ 積の場合,\ 2457を計算してから7で割るのは大変である. 合同式の性質を用いると つまり,\ {計算してから余りを求めるのではなく,\ 余りを求めてから計算}できる. }の性質は,\ 合同式を等式に変換すると容易に証明できる. わかりやすいように具体例も示しておく. よって,\ a+bを5で割ると余りは4,\ abを5で割ると余りは3であるとわかる. この過程をよく観察すると,\ 商p,\ qは余りには全く関与していない. よって,\ 最初から余りの部分だけを見て,\ 1+3=4,\ 13=3\ と考えればよい. この{余りだけに着目していることを示す数学的表現が合同式}なわけである. 合同式を使うと,\ {本質がわかりやすくなり,\ 圧倒的に簡潔な記述が可能になる.} }は,合同式が{加法・減法・乗法のときは等式と同様に扱える}ことも意味する. \ また,\ {等式と同様に移項}することもできる.除法m,\ pが互いに素}であるとき {合同式の最も大きな弱点が除法}である. ,\ のような合同式の除法があるが,\ 使う機会は非常に少ない. ここでは,\ 参考程度にとどめておく. は,\ {m,\ pが互いに素ならば,\ 両辺をmで割ってよい}ことを意味する(2と5は互いに素)  {×} 2x≡6od8\ -1/\ x≡3od8 (2と8は互いに素ではない) 「ma≡ mb od p」「ma-mbがpの倍数」 \「m(a-b)がpの倍数」「a-bがpの倍数」(∵\ m,\ pは互いに素) は,\ を一般化したものであり,\ {法も含めて両辺をmで割ることができる.} なお,\ 合同式は{異なる法の2数にも弱い.} 整数mは7で割ると3余り,\ 整数nは7で割ると5余るとする.$ $このとき,\ 次の式を7で割ったときの余りを求めよ.$ $7を法とすると  合同式は等式と同様に扱えるから,\ m=3,\ n=5を代入するのと同じ感覚でよい. 7で割ったときの余りであるから,\ {0~6で答えなければならない}ことに注意する. 先に述べたように,\ {7を超える数値は余りにしてから計算する}と楽である. よって,\ 3635=540\ ではなく,\ {36≡1}を用いてから計算したわけである. 9-125程度なら普通に計算してもよいが,\ 9≡2,\ 125≡6\ を先に適用した. {125≡6≡-1\ のように絶対値が小さい負の剰余}を利用するとさらに楽である. なお-4を正の剰余に直すには,\ +7をすればよい. {7で割ったときの余りは,\ 周期7で循環}しているからである. m=7p+3,\ n=7q+5\ とする解法と比較すると,\ 合同式の便利さを実感できる.
タイトルとURLをコピーしました