ホーム >> 整数 >> 1次不定方程式 ax+by=1 の2通りの解き方

1次不定方程式 $ax+by=1$ の整数解を求める方法を紹介します.




1次不定方程式ax+by=1

$x,y$ に関する $2$ 元 $1$ 次不定方程式 $ax+by=1$ の整数解を求めます.ここで,$a,b$ はともに整数であるとします.たとえば例として, $$3x+2y=1$$ の整数解を考えてみると,$(x,y)=(1,-1),(2,-2)$ などが見つかります.しかし,解はこれだけではありません.この方程式の一般解 (すべての解) は,$(x,y)=(2t+1,-3t-1)$ となります.ただし,$t$ は任意の整数です.一般に,$1$ 次不定方程式 $ax+by=1$ の整数解は存在するならば無数にあります.存在するならば,と断ったのは解がない場合があるからです.たとえば, $$2x+4y=1$$ は整数解をもちません.これは左辺がつねに $2$ の倍数となり,右辺の $1$ は $2$ の倍数でないからです.一般につぎのことが成り立ちます.

$x,y$ の方程式 $ax+by=1$ が整数解をもつ ⇔ $a,b$ は互いに素

$a$ と $b$ が互いに素のときに,一般解を求めてみましょう.

直感でひとつの解を見つける方法

$2$ 元 $1$ 次不定方程式 $ax+by=1$ のすべての解を求めるために,まずひとつなんでもよいので解を見つけます.そのひとつの解から芋づる式に他のすべての解が見つかるのです.不定方程式 $5x+7y=1$ を例として,説明します.まず,この方程式のひとつの解を探します.たとえば,$(x,y)=(3,-2)$ が見つかります. $$5x+7y=1  \cdots (1)$$ $$5・3+7(-2)=1  \cdots (2)$$ ($1$) 式から ($2$) 式を辺々引いて, $$5(x-3)+7(y+2)=0$$ を得ます.これより,$5(x-3)=-7(y+2)$ となり,$5$ と $7$ は互いに素なので,$x-3$ は $7$ の倍数,$y+2$ は $5$ の倍数であることがわかります.整数 $t$ を用いて,$x-3=7t$ とすると,$y+2=-5t$ とかけます.したがって,$(x,y)=(7t+3,-5t-2)$ が一般解となります.

このように,ひとつの解をみつけることができれば,それを用いて一般解を求めることができます.

ユークリッドの互除法を用いる方法

直感で解を見つけることが難しい場合は,ユークリッドの互除法を用いて解くことができます.
$$162x+125y=1$$ を解いてみましょう.この方程式を眺めてひとつの解を見つけるのはなかなか難しいでしょう.そこで,$x,y$ の係数 $162$ と $125$ に注目します.まず,$162$ を $125$ で割ります. $$162=125\cdot1+37$$ 次に,割る数であった $125$ を余りである $37$ で割ります. $$125=37\cdot3+14$$ 同様に,割る数であった $37$ を余りである $14$ で割ります. $$37=14\cdot2+9$$ この操作を余りが $1$ になるまで繰り返します.(最初の $2$ つの係数 $162$ と $125$ は互いに素なので,この操作を繰り返すといずれは必ず余りが $1$ になります.) $$14=9\cdot1+5$$ $$9=5\cdot1+4$$ $$5=4\cdot1+1$$ 余りが $1$ になったところで,今度は先ほどの計算を逆にたどります.

$1=5-4\cdot1$ に $4=9-5\cdot1$ を代入して,$1=5\cdot2-9$ です.
$1=5\cdot2-9$ に $5=14-9\cdot1$ を代入して,$1=14\cdot2-9\cdot3$ です.
$1=14\cdot2-9\cdot3$ に $9=37-14\cdot2$ を代入して,$1=14\cdot 8-37 \cdot 3$ です.
$1=14 \cdot 8-37 \cdot 3$ に $14=125-37 \cdot 3$ を代入して,$1=125 \cdot 8-37 \cdot 27$ です.
$1=125 \cdot 8-37 \cdot 27$ に $37=162-125 \cdot 1$ を代入して,$1=125 \cdot 35-162 \cdot 27$ です.

つまり,つぎつぎに割り算をしていって,最終的に余りが $1$ になったところで,今度は逆にたどって,つぎつぎに式を代入していくことで,$162$ と $125$ の線形和で $1$ を表現できるのです.これは,ベクトルの基底を変更していく操作に似ています.

よって,$162x+125y=1$ のひとつの解は $(x,y)=(-27,35)$ であることがわかります.あとは先ほどと同じ方法で,一般解を求めることができます.

逆にたどって代入していく操作が少々面倒ですが,この方法はどのような $2$ 元 $1$ 次不定方程式が与えられても原理的には一般解を求めることができるので,強力です


ユークリッドの互除法は単純な繰り返し作業なので,人間よりもコンピューターの方が得意ですね.