線形不定方程式を解く

lineqZ.c

これをファイル lineqZ.c に貼り付けて保存. コンパイル, 実行は

cc lineqZ.c
./a.out
数字を入力して enter(return)キー

$103 c_1 + 23 c_2 = 1$ の解はたとえば $(c_1,c_2)=(-2,9)$. この結果から mod 103 での $23$ の逆元は $9$ がわかる.
他の方程式も解いてみる.

これをファイル lineqZ.rr に貼り付けて保存. asir メニューから, start asir, execute current buffer.

一変数多項式環で不定方程式 $ c_0 f + c_1 g = 1 $ を解く. ここで $f=x^3-1$, $g=x^2+1$. 未知多項式は $(c_0,c_1) \in {\bf Q}[x]^2$.

これを Macaulay2 (M2) に貼り付ける(paste). または名前 11-lineqP.m2 で保存して, M2で

load "11-lineqP.m2"

変数の値は表示されないので, load したあとたとえば FG と入力すれば FG の値がわかる.

gens(G)

で G の要素を出力. この場合は gcd.

$c_0 (x^2+y^2-4) + c_1 (xy-1) + c_2 (x^3+y^3-4)=1$

$c_0 \pmatrix{x^3-1 \cr x \cr} + c_1 \pmatrix{x^2+1\cr 1 \cr}= \pmatrix{x+1 \cr 0 \cr}$ $c_0=-1, c_1=x$ が解.