高校数学(3) 一次不定方程式
次の形の一次方程式について考えます。
$ax+by=c$$\ \ $($a,b,c$は定数)
まず、この方程式が解を持つ条件について考えます。
$a,b$の最大公約数を$d$と置くと、$\displaystyle\frac cd=\frac adx+\frac bdy$より、$c$は$d$の倍数であることが必要条件です。
実はこれは十分条件でもあります。
$S(a,b)=\{ax+by|x,y\in\mathbb{Z}\}$とします。
このとき、$S$は和について閉じています。
$S$に含まれる正の整数のうち最小のものを$d'$とします。
$S$の任意の元$n$に対して$n$を$d'$で割った余りを$r$と置くと、$d'$の最小性より$r=0$となるので、$S=d'\mathbb{Z}$となります。
$a,b\in S$より、$d'$は$a,b$の公約数なので$d'\leq d$
また、$d|d'$より、$d\leq d'$となるので、$d'=d$であり、$n\in S\Leftrightarrow d|n$が分かりました。 □
このことにより、$ax+by=c$を解く問題は$a,b$が互いに素な場合に帰着でき、$ax+by=1$の解を$c$倍することで$ax+by=c$の解も求まるので、結果的に$a,b$が互いに素なときの$ax+by=1$を解く問題へと帰着できました。
また、解が$1$つ見つかればそれを基に全ての解を構成できるので解は$1$組見つければ十分です。
例題として$22x+39y=1$を考えてみましょう。
この問題では$22x\equiv1\ (\mathrm{mod}39)$となる$x$を見つければ$\displaystyle y=\frac{1-22x}{39}$として解が求められます。
それでは、$22x\equiv1\ (\mathrm{mod}39)$の解を探してみましょう。
$22x=1$のときは$\displaystyle x=\frac{1}{22}$となるので、合同式でも同じようにしてみます。
$a,n$が互いに素であるとき、$ax\equiv b\ (\mathrm{mod}n)$であることを$\displaystyle x\equiv\ \frac{b}{a}\ (\mathrm{mod}n)$と表す。
※この記法を数学のテストで使うときはきちんと断りましょう
$a\equiv b,c\equiv d$で$m$と$n$が互いに素であるとき、$\displaystyle\frac{b}{a}\equiv\frac{d}{c}$や$\displaystyle\frac{b}{a}\equiv\frac{mb}{ma}$が成り立ちます。
これを使うと、$22x\equiv1\ (\mathrm{mod} 39)$の解は、
$\displaystyle x\equiv\frac{1}{22}\equiv\frac{2}{44}\equiv\frac{2}{5}\equiv\frac{16}{40}\equiv16\ (\mathrm{mod}39)$
と求められます。
また、連分数を使って解くこともできます。
$\displaystyle1+\frac{1}{1+\frac{1}{3+\frac{1}{2}}}=1+\frac{1}{1+\frac{2}{7}} \\\displaystyle=1+\frac{7}{9}=\frac{16}{9}$
よって、$(x,y)=(16,-9)$
これについてはまたの機会に書こうと思います。