〔論説〕

連立 1 次ディオファントス方程式
有澤健治†

Abstract
Another solution to a system of linear Diophantine equations is presented.
The idea stands on the work of Gilbert and Pathria eliminating some defects
in their solution.

はじめに1

ディオファントス方程式とは、整数係数の方程式において整数解を求める方程式である。例えば x2 + y 2 = z 2 を満たす整数 x, y, z を求める問題もディオファントス方程式に含まれる。しかし、ここでは次の連立 1 次ディオファントス方程式だけを考える:

a1,1 x1 + a1,2 x2 + · · · + a1,n xn
a2,1 x1 + a2,2 x2 + · · · + a2,n xn···

am,1 x1 + am,2 x2 + · · · + am,n xn====
b1 b 2··· bm(1)

ここに ai,j や bi たちは全て整数であり、その下で整数解 x1 , ..., xn を求めるのが目標である。不定方程式なので、多くの場合 m < n として問題が与えられているだろう 1 。
連立ではない場合、すなわち m = 1 の場合には、初等整数論のテキストや、ネット上に多数の解説が見つかる。しかし m > 1 の場合の解説を見つ† Kenji Arisawa, Aichi University, Nagoya, Japan, arisawa@aichi-u.ac.jp1

似て非なる問題に整数線形計画法がある。それはジャンルの異なる難しい問題である

─ 63—
1 ─—

けるのが難しい 2 。筆者はようやく Gilbert-Pathria による解説を見つけた [7] 。
彼らの解説を読むと、連立 1 次ディオファントス方程式は易しい問題であることが分かる。計算量も少ない、うまい初等的な解法が紹介されているのである 3 。ここでは彼らのアイデアに沿いながら、彼らのいくつかの欠点については修正を加えて解法を紹介する。修正点については本文の中で説明する。
この記事で使用する記法を簡単にまとめておく:• (M )i,j : 行列 M の i, j 要素

• ⌊α⌋ : 床関数 (実数 α を超えない最大の整数)• a | b : a は b の約数である (ak = b となる整数 k が存在する)• a mod b : a を b (b > 0) で割った剰余 (a = bq + r (0 ≤ r < b) となる r)
剰余については多少の注釈が必要であろう。標準的な整数論のテキストでは剰余計算を b > 0 の場合に限定している 4 。b < 0 についても剰余を定義できなくはないが、不必要な複雑さを招くからだと思える。ここでも b > 0 の場合にだけ mod を使っている。

解法

2

まずは簡単な問題から始める。

a1,1 x1 + 0x2 + 0x3 + 0x4=b1

0x1 + a2,2 x2 + 0x3 + 0x4=b2(2)

この方程式の解は自明で、解を持つためには a1,1 | b1 , a2,2 | b2 の条件が必要であり、その下で x1 = b1 /a1,1 , x2 = b2 /a2,2 で、x3 , x4 は任意の整数である。
式 (1) で与えられた問題を、簡単な問題、つまり対角行列での問題に変形できれば問題が解けることが分かる。行列 M が対角行列であるとは、(M )i,j =0 (i ̸= j) である行列を言う。

問題を一般的に扱うために、最初に整数行列 (整数を要素とする行列) の性質を調べる。整数行列 M に次の変形規則を導入する。
高木 [2] の補遺に m = 2 の解法例が載っているが、素朴である学生にも分かる解法であることが強調されている
4
例えば文献 [1, 2, 3, 4] など
23

─ 64—
2 ─—

連立 1 次 Diophantus 方程式(a) M の任意の行 i に、i と異なる任意の行の整数倍を加えてもよい。列についても同様である(b) M の任意の行、あるいは任意の列は符号を反転してもよい(c) M の任意の 2 つの行、あるいは任意の 2 つの列は、交換可能である

これらの規則は行列式の変形規則でもある。ただし行列式は値を持っており、上記の (b) および (c) では行列式の符号が反転する可能性があるが、ここではM は値を考えない。
これらの規則は可逆な変形規則である。(b) と (c) が可逆であることは自明である。(a) が可逆であることは次のように分かる: i 行目と j 行目を各々 viおよび vj とすると、操作 (a) によって j 行目に i 行目の k 倍を加えると j 行目は vj + kvi となる。その結果に i 行目の −k 倍を加えると元に戻る。列についても同様である。

(c) は (a) と (b) の組み合わせて実現できることに注意しよう。なぜなら

状態i 行目j 行目

説明S0vivj

初期状態

S1vi

vi + vj

状態 S0 の j 行目に i 行目を加える

S2−vj

vi + vj

状態 S1 の i 行目から j 行目を引く

vi

状態 S2 の j 行目に i 行目を加える

vjvi

状態 S3 の i 行目の符号を反転する

S3S4−vjとなるからである。列についても同様である。

M がこれらの変形規則によって M ′ を生成する場合、M は M ′ に変形可能であると言うこととし、記号的に M ∼ M ′ と書こう。

行列の変形について、よく知られた定理を、次の補題 1 と補題 1 の系として示しておく。
補題 1. 零行列 (全ての要素が 0 の行列) ではない m × n の整数行列 M は、

a′1,1 ̸= 0,a′1,j = 0 (j = 2, ..., n),a′i,1 = 0 (i = 2, ..., m)となるように変形可能である。ここに a′i,j = (M ′ )i,j である。
証明: 証明に当たって、次の用語と記法を定義しておく:
─ 65—
3 ─—

• 零行 : 全ての要素が 0 の行
• “:=” : 代入

以下では ai,j = (M )i,j とする。M の中の零行ではない要素を一つを選び 5 、先頭行に移動する。行の入れ替えを行えばよい。そして、以下の STEPを繰り返す。
STEP1: a1,k (k = 1, ..., n) の中に負の要素があれば、その列の符号を反転しておく。a1,k (k = 1, ..., n) の中の、0 ではない最小の要素を a1,i とする。列1 を列 i と入れ替える。その結果 a1,k (k = 2, ..., n) が全て 0 であれば STEP2へ行く。そうでなければ次の計算をする:

nk := ⌊a1,k /a1,1 ⌋,a′i,k = ai,k − nk ai,1

(k = 2, ..., n)

ここに a の添字の i は 1, ..., m を表す。すると a′1,k = a1,k mod a1,1 となっている。この操作の結果得られた行列 M ′ を再び M として、STEP1 へ行く。

a1,1 の値が減少することに注意。
STEP2: i = 2, ..., m について ai,1 mod a1,1 を調べる。ai,1 mod a1,1 ̸= 0 となる i を見つけて ai,1 := ai,1 mod a1,1 とし、1 行目と i 行目を入れ替えて、STEP1 へ行く。a1,1 の値が減少することに注意。ai,1 mod a1,1 ̸= 0 となる iが存在しなければ STEP3 へ行く。

STEP3: この段階で条件を満たす M ′ が得られている。

補題 1 の系 m × n の整数行列 M は、対角行列 M ′ に変形可能である。
証明: 補題 1 によって M はa′1,1000∗

∗∗

∗

00∗

∗

···0···

∗···

∗···

∗の形に変形できる。ここに ∗ は何かの整数である。変形規則を M の (2 行目、2 列目以降の) 小行列に適用すると 2 行目まで対角化できる。そして、3 行目、4 行目へとこのプロセスを繰り返せばよい。
5

一般的に言えば、絶対値が (0 ではない) 最小の要素が収束が速い─ 66—4 ─—

連立 1 次 Diophantus 方程式

補注 1: 我々の目的には対角化されれば十分である。しかし、もっと強い主張が成り立つ。すなわち整数行列の対角化された対角要素を e1 , e2 , ... とすると ei |ei+1 (i = 1, 2, ...) になるように対角化可能である。このことは、補題 1のアルゴリズムに多少の修正を加えることで証明できる。アーベル群論における対応する定理は、単因子定理と呼ばれる 6 。Kurosh によると、「有限個の生成元を持つアーベル群の全理論が、本質的にはこの定理 (単因子定理) に基づいている 7 」。それほど重要な定理なのである。
補注 2: Gilbert-Pathria は行列の変形目標を三角行列に置いている。そのことが変形後の処理を複雑にし、解の存否の判定にさらに計算を要する原因になっている。
問題 1. 行列(5686−117)()を対角化せよ。

答: 行列の変形規則を基に、変形の結果を 1 ステップごとに書いて行くと次のようになる:(568568)(09113)∼∼−11 7
1 −17 −1
1 −17 −1() () () (0 91 130 0 13
1 0 01∼∼∼∼1 00
1 0 00 0 130600130)

行われた操作は順に、行:(a), 行:(a), 列:(a), 列:(a), 行:(c), 列:(c) である。ここに (例えば)「行:(a)」は、行列の行に変形規則 (a) を適用したという意味である。
行列に対する変形操作が正方行列で表現できることを示しておく。E を単位行列、Ii,j を行列要素 i, j が 1 で残りの全てが 0 の正方行列とする。すると Ii,j は2Ii,i= Ii,i ,2Ii,j= 0 (i ̸= j)を満たす。ここに 0 は零行列である。
67

Waerden [6] p.148
Kurosh [5] p.121

─ 67—5 ─—M Ii,j は M と同じサイズの行列であり、j 列目を除き全て 0 で、j 列目には M の i 列目が現れる。従って、行列 M の i 列目の k 倍を j 列目に加える操作は M (E + kIi,j ) で表される。E + kIi,j の逆行列は逆操作でもあり、

E − kIi,j である。実際である。

2(E + kIi,j )(E − kIi,j ) = E 2 + kIi,j − kIi,j + k 2 Ii,j=EM の i 列目の符号を反転する行列は E−2Ii,i である。この逆行列が E−2Ii,iであることは自明であるが、計算によっても確認できる:2(E − 2Ii,i )(E − 2Ii,i ) = E − 4Ii,i + 4Ii,i=EM の 2 つの列を入れ替える操作 (c) は、(a) と (b) の組み合わせであるから、正方行列で表現でき、また逆行列も存在することになる。
行に対する操作は、M に左から正方行列を掛けることによって、列と同様に扱える。
問題 1 の答では(10−11)(5686−117)=(5681−17−1)など、多数の行の変形がある。列の変形としては(などがある。

09110)

113 00 001−700
=1(0013100)

式 (1) を行列式 Ax = b で表そう。ここに A は m × n (n > m) 行列で、ai,j = (A)i,j とする。また x は n × 1 の行列で xi = (x)i であり、b は m × 1の行列で bi = (b)i とする。目標は A, x, b を変形して Âx̂ = b̂ の形に持っていくことである。ここに Â は対角行列である。

A ∼ Â 故 A と Â は正方行列による変形操作で結ばれている:Â = Sk Sk−1 · · · S1 AT1 T2 · · · Tl
─ 68—
6 ─—

連立 1 次 Diophantus 方程式

ここに S∗ (∗ = 1, ..., k) は行に対する変形操作で m × m の行列である。またT∗ (∗ = 1, ..., l) は列に対する変形操作で n × n の行列である。

行列の掛け算の計算は行列の変形に比べてひどく煩わしく、極力避けたいものである。以下のことに気がつけば、それが可能であることが分かる:
方程式 Ax = b は(Sk Sk−1 · · · S1 )A(T1 T2 · · · Tl )(T1 T2 · · · Tl )−1 x = (Sk Sk−1 · · · S1 )bと変形できる。これと Âx̂ = b̂ を比較して

x̂ = (T1 T2 · · · Tl )−1 x,b̂ = (Sk Sk−1 · · · S1 )bを得る。b̂ と、対角化された Â が与えられれば、x̂ は容易に求まり、そして x̂
から x = T1 T2 · · · Tl x̂ によって x が得られる。計算を効率良く行うために、n × n の単位行列 E を導入すると x = ET1 T2 · · · Tl x̂ である 8 。
そこでE (l) = ET1 T2 · · · Tl ,A(l) = AT1 T2 · · · Tlと置くと、 A から A(l) を得る操作も、 E から E (l) を得る操作も、共に操作
列 T1 , T2 , ..., Tl である 9 。また同様に A に対する行の操作は b に対する操作と共通である。従って A を対角化するついでに x̂ から x を求めるのに必要な行列 Ê を求め、さらにその上 b を b̂ に変形可能である。
従って図 1 のような計算表を描くが良い。この図には変形目標が計算表によって示されている。ここに終状態の “∗” は自然数であり、Â の対角要素を表す。ここの最後の行 “ 0 0 · · · 0 ” は全てが 0 である必要はなく、一般的には対角要素がここまで伸びている。また êi,j = (M̂ )i,j である。ここに Ê = E (l)は x = Ê x̂ を満たす、我々が欲しかった行列である。

補注 3: Gilbert-Pathria は b1 , ..., bm を表に加えない。対角化の意図がないからであろうが、方法の力を弱める原因になる。さらに A も E も行列を転置して表に書く 10 。そのために E を A の右隣に書いている。その結果、表と8Gilbert-Pathria のうまさは、単位行列 E の導入にある。それによって、変数を引きずる計算から解放され、行列の計算だけでやって行けるようになるのである
9
このことが理解しやすいように証明したから、ここでは自明なのであるが、そうでなければ、ここは気付きにくい箇所である。整数線形計画法ではよく知られたテクニックなのであろう
10
この点について彼らも不自然であることを認めている。学生が列の操作よりも行の操作の方

─ 69—
7 ─—

図 1: 変形目標 (左: 始状態, 右: 終状態)

a1,1 · · · a1,na2,1 · · · a2,n···am,1 · · · am,n
1 0 ··· 00 1 ··· 0···0 0 ··· 1b1b2···bm∗ 0 ··· 00 ∗ ··· 0···0 0 ··· 0ê1,1 · · · ê1,nê2,1 · · · ê2,n···ên,1 · · · ên,n⇒b̂1b̂2···b̂m

式 (1) との対応が不自然になり、彼らの証明もまた分かり難くなるのである。

連立ディオファントス方程式

5x1 + 6x2 + 8x3 = 16x1 − 11x2 + 7x3 = 9(3)を解く場合の計算表を図 2 に示す 11 。この計算表によって解はx1 = x̂1 + x̂2 + 10x̂3 ,x2 = x̂3 ,x3 = x̂2 − 7x̂3として得られる。そして x̂1 + 0x̂2 + 0x̂3 = 8, 0x̂1 + 13x̂2 + 0x̂3 = −39 故x̂1 = 8, x̂2 = −3 であり、x̂3 は任意の整数である。従って k を任意の整数としてx1 = 5 + 10k,x2 = k,x3 = −3 − 7kを得る 12 。に慣れているからだとか...
11題材は Gilbert-Pathria から採った。彼の解法と比較するが良い12得られた解は Gilbert-Pathria の解 x1 = −5 + 10k, x2 = −1 + k, x3 = 4 − 7k とは (見かけ上) 異なるが、k → k + 1 の置き換えで両者は一致するので実際は同じである

─ 70—8 ─—連立 1 次 Diophantus 方程式

図 2: 式 (3) の計算表
5610036−110108700119⇒511006−170108−1001

18⇒0110091
01710130101−398⇒1010000101−70131018−39⇒0110091−1701013−1001−398⇒0110000101−7130101−398⇒1010001310100101−78−39

おわりにGilbert-Pathria の記事 13 は、30 年も前 (1990 年) のものである。類似のテーマの記事があるかどうか? ネット検索では見つからない。彼らの参考文献を見る限り、彼らは線形計画法あるいは整数計画法の研究者らしい。彼らの方法は (すべてを行列に持ち込む手法など) そこからヒントを得たのではないかと思える。また、“Further Reading” として線形計画法と整数計画法を挙げているのだが、これらの守備範囲は広大で、特に整数計画は計算機のパワーに依拠する極めて困難な分野である。連立 1 次ディオファントス方程式は計画法の一分野として考えるような問題ではなかろう。独自の世界を持つ易しい問題なのである。
https://www.math.uwaterloo.ca/~wgilbert/Research/AlgAndGeomPapers.html によると論文ではなく、manuscript となっている。論文にする程ではないが、公表の価値はあると判断したのであろう
13─ 71—9 ─—

行列の三角行列化あるいは対角化自体はありふれた手法である 14 。それと連立 1 次ディオファントス方程式の解法を結びつけたのが Gilbert-Pathria だとしたら、彼らは非常に良い仕事をしたことになる。そのヒントが計画法の中にあった可能性が高いが、筆者はそれを確認する資料を持ち合わせていない。

References[1] P.G.L.Dirichlet, J.W.R.Dedekind (酒井孝一訳):『整数論講義』(共立出版,1970)[2] 高木貞治:『初等整数論講義 (第 2 版)』(共立出版, 1971)[3] L.M.Vinogradoff (三瓶与右衛門、山中健訳):『整数論入門』(共立全書, 1962)[4] G.H.Hardy, E.M.Wright: “An Introduction to the Theory of Numbers”(Oxford Science Publication,1979)（東京図書，1960）[5] A.G.Kurosh (本田欣哉校閲、吉崎敬夫訳):『群論 (1)』[6] van der Waerden (銀林浩訳): 『現代代数学 3』(東京図書, 1960)[7] Willliam J. Gilbert, Anu Pathria: “Linear Diophantine Equations”(https://www.math.uwaterloo.ca/~wgilbert/Research/

GilbertPathria.pdf 1990)

Gilbert-Pathria が、対角化ではなく、三角行列に変形したのは、明らかに整数線形計画法の影響である。この分野では、三角行列が好まれているようである。しかし、この問題に関する限り、それは負の影響でもあった
14—─ 72
10 ─—