a.2 終結式とAP+BQ=C


・終結式

終結式はシルベスター行列の行列式というもので計算できる。
f(x)がn(x)次、gがm次のとき、それは次のような(m+n)次正方行列となる。
[Wikipedia:シルベスター行列]
f(x)の係数をずらしながらm行、g(x)の係数をずらしながらn行書いたものである。

・f(x)とg(x)が共通解をもつ ⇔ (f(x)とg(x)の終結式=0) が成り立つ。
これが終結式である。

が、実際にこの行列式を計算するのはしんどいので、コンピュータで、
例えばソフトMaximaで resultant(式1,式2,変数); と命令する。

・f(x)の解をαとする。g(α)を解とする方程式は
 resultant(f(y),x-g(y),y); で求めてくれる。

・方程式ap+bq=c と A(x)P(x)+B(x)Q(x)=C(x)

#34p+49q=1となる整数p,qを求めよ。
 色々な解法が考えられるがここでは以下のように解いてみる。
 34p≡13 (mod 49, 以下すべてmod 49とする)を解く。
 34≡-15
 34*3≡-15*3≡-45≡4 [49=3*15+4≡0であることから]
 34*3*12≡4*12≡48≡-1 [49=12*4+1≡0であることから]
 よってp≡-3*12≡13, q=(34p-1)/49
 一般解は 34*(13+49t)-49*(9+34t)=1

このように、a,bが互いに素ならap+bq=1の解を構成できる。
a,bをc倍すればap+bq=cの解も構成できる。
多項式の場合も同様に考えることができる。

#(x^2+2)P(x)+(x^3-x+5)Q(x)=1となる多項式P,Qを求めよ。
 (x^2+2)P(x)≡1 (mod x^3-x+5 以下同様) を解く。
 (x^2+2)*x≡x^3+2x≡3x-5
 (x^2+2)*x*(x^2/3+5x^2/9+16x/27)≡-215/27
  [x^3-x+5=(3x-5)(x^2/3+5x/9+16/27)+215/27≡0であることから]
 よってP(x)≡x*(x^2/3+5x/9+16/27)*(-27/215)≡(-3x^2-5x+9)/43
 これから次の一般解を得ることができた。
 P(x)=(-3x^2-5x+9)/43+T(x)*(x^3-x+5)
 Q(x)=(3x+5)/43+T(x)*(x^2+2)

このように、A(x),B(x)が共通因数を持たないなら
A(x)P(x)+B(x)Q(x)=1を満たすP(x),Q(x)を構成することができる。
C(x)倍すれば A(x)P(x)+B(x)Q(x)=C(x) も同様に解を構成できる。
計算は上記のように煩雑なものとなり解も煩雑であるけれど...

 目次 inserted by FC2 system