合同方程式


xの多項式f(x)≡0 (mod p) は合同方程式と呼ばれる。

・一般的に f(x)≡f(x+Np) (mod p)
 なぜなら多項式の各項で (x+Np)^k≡x^k となるから。
ということは合同方程式f(x)≡0 (mod p) の解は、  x≡なんとかたち (mod p)という形で書かれる。

☆主張☆
n次の多項式f(x)による合同方程式f(x)≡0 (mod p)について考える。
(最高次の係数≠0 (mod p)とする。)
pが素数ならばpを法として高々n個の解しか持たない。

[証明]
数学的帰納法による。n=1ではかなり明らかである。
ax+b≡0 (mod p)においてa≠0 (mod p)だから、
xの値が違えばaxの値が違う。よって解は1つのみ。
あるいは拡張合同式を使えばx≡-b/aとすればよい。

n=k次式の時、高々k個の解しかもたないと仮定する。

n=k+1次式f(x)について、f(x)≡0 (mod p)の1つの解をcとする。
すなわち、f(x)=(x-c)*g(x)+R と書くとR≡0(mod p)である

よってf(x)≡(x-c)*g(x) (mod p) と書ける。(g(x)はxのk次多項式である)

pが素数なので、f(x)がpで割り切れるなら(x-c)とg(x)のどちらかがpで割り切れる。
よってx≡c以外の解は、g(x)≡0を満たさなければいけない。

よって帰納法の仮定によりf(x)は高々1+k個の解しか持たない。(証明終わり)

上記証明では、AB≡0 (mod p)ならばa≡0またはb≡0という事実がポイントである。
これはpが素数であれば、A,Bがm次の無理数としても同様に成り立つ。

#合同方程式x^2+2x+5≡0 (mod p) を解くことを考える。
#p=13 の場合x≡2,9が答えとなる。
 x^2+2x+5≡(x-2)(x-9) (mod 13) という表記も得る。(「合同分解」)
#p=65 では解が4つある。 x≡15,48,35,28
 x^2+2x+5≡(x-15)(x-48)≡(x-35)(x-28) (mod 65) も得る。
#このようにpが素数でない時は2次式でも解が4つあったりする。

 目次 inserted by FC2 system