Maxima で綴る数学の旅

紙と鉛筆の代わりに、数式処理システムMaxima / Macsyma を使って、数学を楽しみましょう

-Maxima入門、数学- 多項式f(x)のmod p(x)での逆元

これから引続くいくつかの記事では主に1変数有理係数方程式を扱う予定です。

今回は二つの有理係数の多項式p(x)とf(x)が与えられた時、f(x)のmod p(x)での逆元g(x)を求めます。f(x)の逆元g(x)とは、f(x)*g(x)=1 (mod p(x))となるような有理係数の多項式g(x)を指します。

ちなみにp(x)が既約であればそのようなg(x)は必ず存在し、計算できます。やって見ましょう。(%o1)でp(x)を定義します。このp(x)は既約です。

(%i1) p(x):=x^5-x^2+x+1;
$$ \tag{%o1} p\left(x\right):=x^5-x^2+x+1 $$

次にf(x)を定義します。
(%i2) f(x):=x^4-2;
$$ \tag{%o2} f\left(x\right):=x^4-2 $$

gcdex()にこれらの2つの多項式を渡すと、あれば逆元を求めてfinvという変数に入れてくれます。
(%i3) ([dummy,finv,gcdvalue]:gcdex(p(x),f(x)),finv);
$$ \tag{%o3} -\frac{33\,x^4-8\,x^3+9\,x^2-14\,x+107}{233} $$

検算をして見ます。finvとf(x)を掛け算して展開まで実行します。
(%i4) finv*f(x),expand;
$$ \tag{%o4} -\frac{33\,x^8-8\,x^7+9\,x^6-14\,x^5+41\,x^4+16\,x^3-18\,x^2+28\,x-214}{233} $$

p(x)で割った余りを求めてます。
(%i5) remainder(%,p(x));
$$ \tag{%o5} 1 $$

ちゃんと1になったので、finvはf(x)の逆元です。

 

もう一つやって見ましょう。今度はp(x)は規約ではありませんが、f(x)とは互いに素になるようにします。
(%i6) p(x):=(x^3+2*x^2+3*x+1)*(x^2-9);
$$ \tag{%o6} p\left(x\right):=\left(x^3+2\,x^2+3\,x+1\right)\,\left(x^2-9\right) $$
(%i7) f(x):=x^2;
$$ \tag{%o7} f\left(x\right):=x^2 $$

gcdex()で逆元を求めます。
(%i8) ([dummy,finv,gcdvalue]:gcdex(p(x),f(x)),finv);
$$ \tag{%o8} -\frac{3\,x^4+5\,x^3-20\,x^2-45\,x-64}{9} $$

検算して見ます。掛けて展開して、
(%i9) finv*f(x),expand;
$$ \tag{%o9} -\frac{3\,x^6+5\,x^5-20\,x^4-45\,x^3-64\,x^2}{9} $$

p(x)で割った余りを求めると、、、
(%i10) remainder(%,p(x));
$$ \tag{%o10} 1 $$

ちゃんと1になりました。

 

ちなみにa, mを整数としてaのmod mでの逆元はinv_mode(a,m)で求めることができます。こちらも試してみてください。