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