Logo address

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

2019/05/21
2019/05/31 更新
2019/06/17 更新(bug fix and shape up in PDF)

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次ディオファントス方程式、すなわち下記の式(1)
\[ \begin{equation} %\label{eq:bi:2} \left. \begin{array}{lcl} a_{1,1}x_1 + a_{1,2}x_2+\cdots + a_{1,n}x_n &=& b_1\\ a_{2,1}x_1 + a_{2,2}x_2+\cdots + a_{2,n}x_n &=& b_2\\ \cdots &=& \cdots\\ a_{m,1}x_1 + a_{m,2}x_2+\cdots + a_{m,n}x_n &=& b_m \end{array} \right\} \end{equation} \] において整数 $a_{i,j} \;(i=1,...,m;\; j=1,...,n)$ と整数 $b_i \;(i=1,...,m)$ を与え、整数解 $x_1,...,x_n$ を求める問題の、効率の良い、しかも易しい解法の紹介です。
主なアイデアは Gilbert and Pathria の記事から来ていますが、改良が加えられています。
この解法は、筆者の知る限り、どの本にも載っていないし、またネット検索でも見つからないものです。
素朴に計算すると、嫌になるような計算が、巧みに避けられています。
1次ディオファントス方程式にチャレンジした経験のある方は是非とも読んでみてください。
新しい解法の威力が分かると思います。

読者としては、行列の初等的な知識を持っていることが想定されています。

ダウンロード: http:lde.pdf