16

高校数学(3) 一次不定方程式

405
0
$$$$

次の形の一次方程式について考えます。
$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)$
と求められます。

また、連分数を使って解くこともできます。

$\displaystyle\frac{39}{22}=1+\frac{17}{22} \\\displaystyle=1+\frac{1}{1+\frac{5}{17}} \\\displaystyle=1+\frac{1}{1+\frac{1}{3+\frac{2}{5}}} \\\displaystyle=1+\frac{1}{1+\frac{1}{3+\frac{1}{2+\frac{1}{2}}}}$
$\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)$

これについてはまたの機会に書こうと思います。

投稿日:20201125

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

tria_math
tria_math
515
39903
大学2年生

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中