ディオファントス方程式

2018.11.29

ディオファントス方程式

整係数高次不定方程式
 \[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..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)\]
で与えられます。SymPy で確認してみましょう。

# DIOPHANTINE_EQUATION

# In[1]

import sympy

# ディオファントス方程式を解く関数をインポート
from sympy.solvers.diophantine.diophantine import diop_solve

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

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

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

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

# In[2]

sympy.init_printing()

# 不定方程式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 に解かせてみます。

# In[3]

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

print(sol)
# (t_0, 2*t_0 + 4*t_1 + 9, -3*t_0 - 5*t_1 - 9)

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

# In[4]

sympy.init_printing()

# 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$ を解くこともできます。

sympy.solvers.diophantine.diophantine.base_solution_linear(c,a,b,t=None)

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

# In[5]

from sympy.solvers.diophantine.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)
ホーム