一次不定方程式とその解法について

一次不定方程式とその解法についてまとめます。

a,b,cを整数の定数として、$a \ne 0,b \ne 0$とします。

x,yの一次方程式$ax + by = c$を成り立たせる整数x,yの組を
この方程式の整数解といいます。

その方程式を整数解をもとめることを一次不定方程式を解くと言います。
整数解が無数に求まるため、不定方程式と呼ぶそう。

先の例で整数a,bが互いに素であるとき、次のことが成り立ちます。

$ax + by = 0$を満たす全ての整数解は、kを整数として
$x = bk,y = -ak$と表される

$ax + by = 0$より

$ax = b(-y) - ①$

よって、axはbの倍数です。

ここで、aとbは互いに素なので、 xはbの倍数になります。

これを利用して、kを整数として
$x = bk$と表せます。

これを①に代入して

$-by = abk$

$b \ne 0$より、両辺を-bで割ると

$y = -ak$

と証明することができました。

また、先の例で整数a,bが互いに素であるとき、以下も成り立ちます。

$ax + by = 1$を満たす整数解の一つをx = p,y = qとすると、
全ての整数解は、kを整数として、

$x = bk + p,y = -ak + q$
と表すことができます。

$ax + by = 1$ - ②

aとbは互いに素なので、互除法でaとbの最大公約数が1であることがわかります。

この1は、互徐法の計算を逆にたどると、aとbを用いて、
$1 = ap + bq$の形で表せます。

このとき、$x = p,y = q$が整数解の一つであり、

$ap + bq = 1$ - ①とします。

② - ③より

$a(x - p) + b(y - q) = 0$

性質1により、

$x - p = bk$,$y - q = -ak$(kは整数)

各々の式を移行して

$x = bk + p$,$y = -ak + q$(kは整数)

と表すことができます。

初版:2020/7/7