合同式の基本
(※今回の記事は生徒に解説するために作ったので,100%高校範囲です.)
断りがなければ,を整数,を0以上の整数とします.
1.合同式とは
合同式とは,整数の剰余(あまりのことね.)に着目した式のことです.
例えば,とで割った剰余が等しいことを
と書きます.
これをはを法として合同( and are congruent modulo )と言います.
(modulo【前】:〜を法として)
例えば,
です.
これは適切な整数を用いてを,
と表せることに対応していますね.
2.合同式の性質1
合同式の性質2-2
条件より,
推移律より,
条件より,は任意なのでと置き換えて,より,
条件とより,
推移律より,
これで合同式においても等式と同様に加減乗が保障されました.
難しかったら最悪と置けば証明できます.
合同式の性質2-2
即ちより,はの倍数.
とが互いに素ゆえ,はの倍数となるから
.
条件付きで加減乗(除)が保障されました.
べき乗
数学的帰納法を用いる.
のときは自明.
のときと仮定すると,のときを示す.
仮定と条件より,
だから,
でも成立.
以上により,題意は示された.
を使ってもよいならもっと簡単に示せますね.
フェルマーの小定理
のとき,
, は互いに素より,
はの倍数だから,二項定理より,
よって,これを繰り返すと,
を得る.
条件よりが使えるので,の両辺をで割ると,
3.使用例1:ユークリッドの互除法
合同式を使うと,次のようになります.
4.使用例2:一次不定方程式
小さい方の係数を法として計算
(より,右辺がの倍数になるようにする)より,
とは互いに素だから,
よって,と表せるから,
故に,
特殊解を求めなくても一次不定方程式を解くことができました.
4.演習問題
を7で割った余りを求めよ.(易)
を9で割った余りを求めよ.(易)
を19で割った余りを求めよ.(易)
がの倍数になることを示せ.(普)
が自然数のとき,がの倍数となることを示せ.(普)
が自然数のとき,がの倍数となることを示せ.(普)
が平方数となるようなを全て求めよ.(難)
(ヒント:からまでの平方のの位に注目せよ.)
整式を整式で割ったときの余りを求めよ.(難)
(ヒント:より,)
自然数に対し,の最大公約数を求めよ.(難)
(ヒント:とでそれぞれ互除法.)