整数に関する方程式(2)
合同式に未知数xが含まれている場合、未知数の値を求める目的だから合同方程式という。そうでない場合は合同式という。普通の方程式でも解がない場合があるが、合同方程式の場合は、解がない場合が多い。解が存在しない事も知らずに、時間を掛けることは無駄だから、解があるなしの判定は重要である。
例1.次の1次合同方程式に解があるかどうかを判定せよ(レベル2)。
1)3X≡5(mod 7) 2)7X≡15(mod 14) 3)21X≡14(mod 28)
解説:AX≡B(mod M)にて、AとMの最大公約数をdとおく。d=1、すなわち、AとMが互いに素ならば、ただ一つの解がある。d>1で、Bがdで割り切れれば、(mod M/d)でただ一個の解がある。Bがdで割り切れなければ解はない。
1)3と7は互いに素だから、ただ1つの解がある。Nを6以下の整数として、3X=7N+5より、N=1より、X=4。
2)7と14の最大公約数は7、15は7で割り切れないから解はない。
3)21と28の最大公約数は7、14は7で割り切れるから、全体を7で割って、3X≡2(mod 4)として、解が存在する。3X=4N+2より、N=1より、X=2。
元の式に戻れば、答えはX=2,6,10,14,18,22,26(mod 28)。