[SymPy] ディオファントス方程式

Advertisement

ディオファントス方程式

 整係数高次不定方程式
 
\[f(x_1,\ x_2\ \cdots x_n)=0\]
ディオファントス方程式といいます。SymPy では以下のような形のディオファントス方程式を解くことができます。

線形不定方程式 (n元1次不定方程式)
 $a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$

2元2次不定方程式
 $ax^2 + bxy + cy^2 + dx + ey + f = 0$

・斉次3元不定方程式
 $ax^2 + by^2 + cz^2 + dxy + eyz + fzx = 0$

・ピタゴラス方程式
 $a_{1}x_{1}^2 + a_{2}x_{2}^2 + \ldots + a_{n}x_{n}^2 = a_{n+1}x_{n+1}^2$

・平方和不定方程式
 $x_{1}^2 + x_{2}^2 + \ldots + x_{n}^2 = k$

 sympy.solvers.diophantine.diop_solve() の引数に f(x) を渡すことによって解をタプルの形式で得ることができます。詳細については各記事のサンプルコードを参照してください。

線形不定方程式 (n元1次不定方程式)

 $a_1,\ a_2,\ \cdots\ a_n$ を整数、$x_1,\ x_2,\ \cdots\ x_n$ を未知数としたとき、
 
\[a_1x_1+a_2x_2+\cdots a_nx_n=k\]
を $n$ 元 $1$ 次不定方程式といいます(ベズーの等式とよばれることもあります)。一般に未知数が $n$ 個なら、解 $x_1,\ x_2\ \cdots x_n$ は $n-1$ 個のパラメータを用いて表されます。たとえば
 
\[3x+2y=5\]
という不定方程式の解はパラメータ $t$ を用いて
 
\[(x,\ y)=(2t+5,\ -3t+5)\]
で与えられます。SimPy で確認してみましょう。

# 不定方程式の解①

import sympy
from sympy.solvers.diophantine import diop_solve

# 記号x,yを定義
sympy.var("x y")

# 3x+2y=5の解
sol = diop_solve(3*x + 2*y - 5)

print(sol)
(2*t_0 + 5, -3*t_0 - 5)

 Jupyter Notebook 環境下で、実行結果を LaTeX 形式で表示させたい場合は次のコードを記述してください。

# 不定方程式の解① (Jupyter Notebook)

import sympy
from sympy.solvers.diophantine import diophantine

sympy.init_printing()

sympy.var("x y")

# 不定方程式3x+2y=5の解
diophantine(3*x + 2*y - 5)
\[\left ( 2 t_{0} + 5, \quad - 3 t_{0} - 5\right )\]

 
 次は未知数 $3$ 個の不定方程式
 
\[2x+5y+4z=9\]
を SymPy に解かせてみます。

# 不定方程式の解②

import sympy
from sympy.solvers.diophantine import diop_solve

sympy.var("x y z")

# 3x+5y+4z=9の解
sol = diop_solve(2*x + 5*y + 4*z - 9)
(t_0, 2*t_0 + 4*t_1 + 9, -3*t_0 - 5*t_1 - 9)

 Jupyter Notebook で実行結果を LaTeX 形式で表示させたい場合は次のコードを記述してください。

# 不定方程式の解② (Jupyter Notebook)

import sympy
from sympy.solvers.diophantine import diop_solve

sympy.init_printing()

sympy.var("x y z")

# 3x+5y+4z=9の解
diop_solve(2*x + 5*y + 4*z - 9)
\[\left ( t_{0}, \quad 2 t_{0} + 4 t_{1} + 9, \quad - 3 t_{0} - 5 t_{1} - 9\right )\]

 
 base_solution_linear() を使って、$ax+by=c$ を解くこともできます。

 base_solution_linear(c, a, b, t = None)

 t はパラメータに用いる記号です。
 これを省略すると 1 組の解のみが表示されます。

# 不定方程式の解③

import sympy
from sympy.solvers.diophantine import base_solution_linear

# 記号x,y,tを定義
sympy.var("x y t")

# 3x+2y=5の解
sol_0 = base_solution_linear(5, 3, 2)

# 3x+2y=5の1組の一般解(パラメータ記号をtに設定)
sol_t = base_solution_linear(5, 3, 2, t)

print(sol_0, ",", sol_t)
(5, -5) , (2*t + 5, -3*t - 5)