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

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

不定方程式とは

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$と表される

$x = bk,y = -ak$の証明

$ax + by = 0$より、$ax = b(-y) - ①$

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

ここで、aとbは互いに素なので、xは

前提式でabを表すと

$3.ab = (mq + r)(mq' + r ') = m^2qq' + mqr' + rmq' + rr'$ $= m(mqq' + qr' + q'r) + rr'$

累乗と余りの性質

$a^k$をmで割った余りは、$r^k$をmで割った余りに等しい

3の式でb = aとすると

$4.a^2 = (mq + r)^2 = m(mq^2 + 2qr) + r^2$

累乗の数が大きくなるとすると、

$a^k = m × (m,q,rで表される式) + r^k$
になる。

1~4の証明方法

1~4の最終式のm × (整数)をmで割ると余りは0なので、

$a + b,a - b,ab,a^k$をそれぞれmで割った余りは、
$r + r',r - r',rr',r^k$をmで割った余りに等しくなります。

初版:2020/6/28

このエントリーをはてなブックマークに追加