【一次不定方程式】なぜユークリッドの互除法で特殊解が求められるのか？分かりやすく解説

ここでは不定一次方程式の整数解の１つ(特殊解)が、なぜユークリッドの互除法で求められるのかについて書きました。

ユークリッドの互除法の手順を覚えてとりあえず使えるけど、なぜ使えるのか分かんなくてもやもやもやも。

そんな高校生の方々のお役に立てれば幸いです。

「なぜ」か理解すれば、手順を忘れることは無くなるでしょう。またそもそも手順も覚えていない方は、この記事を読んで、覚えて、しかも忘れないようになれるでしょう。

本題。。、。

ユークリッドの互除法で特殊解を求めるまでの流れ

不定一次方程式の例として

$23x + 16y = 1$

を考えることにします。これの特殊解を求めるために、以下の図の操作(ユークリッドの互除法)をすることになりますよね。

ちゃんと言葉にして言うと、

1. $x, y$の係数($23, 16$)で割り算、大きい方を小さい方で割る
2. 割る数、余りを、次は割られる数、割る数にしてまた割り算
3. 2を繰り返そう

ですね。

ユークリッドの互除法

ここで、割り算を

$(割られる数) - (割る数) \times (商) = (余り)$

と（後で、じゃなくて、はじめから）表すことにします。学校の授業、教科書ではまず割り算を、

$(割られる数) = (割る数) \times (商) + (余り)$

と表してから、後で移項して上の方の形の式にするよう言われると思いますが、要らん二度手間です。

実は、これらの割り算の操作を繰り返すことで、

途中で割り切れたりせず、最後に必ず余り１にたどり着くこと

が保証されており、これが大事なのです！

なぜこれが保証されているかは後で説明する(下で話題のタイトルにする)ことにして、先に進みます。

最後の式（$7 - 2 \times 3 = 1$）はそのまま問題の式（$23x + 16y = 1$）になります。

つまり、最後の余り１＝問題の式の右辺の１　となり、最後の式の左辺が必ず

$7 ~- ~2~ \times~ 3 = 23 ~×~ ? ~+~ 16 ~×~ ?$

と変形できることが保証されていて、その変形の手順も上のユークリッドの互除法の中で与えられていることに（頑張れば）気付きます。

最後に、その２つの？が解の１つ（特殊解）ということになります。

以上がユークリッドの互除法で特殊解が得られるまでの道筋ですが、

あとは以下の２つのことを理解すれば、
「なぜユークリッドの互除法で特殊解が求められるのか」が分かるはずです。

• なぜ、割り算が途中で割り切れず、必ず余り１にたどり着くのか
• なぜ、最後の余り１の式が必ず 23 × ? + 16 × ? = 1 と変形できるのか、
  その手順が与えられていること

これらについて以下で解説しまーす

なぜ割り算の繰り返しは最後に余り１にたどり着くのか

なぜあの割り算の操作を繰り返すと、途中で割り切れたりせず、最後に必ず余り１にたどり着くのでしょうか？

これには23と16が互いに素（公約数が１のみ）であることが大事なのです。

そして、次の命題が成り立つことを意識する必要があります。

$a-bq=r$ で $a, b$ が互いに素であれば、$b, r$ も互いに素になる。

特に上式を割り算とみなして言葉で言えば、

互いに素な数の割り算では、余り と 割る数 も必ず互いに素になります。

（ちなみにこれは、「$a, b$の最大公約数は $b, r$の最大公約数である」を狭めた解釈です。まあ今これは気にしなくていいです。）

この証明は短く済みます。書いておきます。

$b, r$ の公約数のどれかを $d$ とし、$b= b' d, r=r'd$ とすると、($-bq$を右に移項して、)

$a= bq + r = (b'q + r') d$

となります。よって、$a= (整数) \times d$ であるから、$d$ は $a$ の約数でもあることになります。

つまり、$d$ は互いに素な$a, b$ （←互いに素、は仮定、前提条件だよ） の公約数でもあるというので、ぜったい$d=1$ です。

よって $b, r$ は互いに素（公約数 $d=1$ だけ）です。QED.....

具体的に上のユークリッドの互除法で言えば、

$23, 16$ が互いに素　⇒　$16, 7$ が互いに素　⇒　$7, 2$ が互いに素

と次の割り算へ「互いに素」が連鎖していくんですねー。

また、余りが割る数より必ず小さくなることも考えると、

次の割り算に進むたび割る数、割られる数は小さくなっていき、しかもそれらはいつも互いに素で決して割り切れることは無いので、最終的に余り１にたどり着きます。

というわけでしたー

なぜ、最後の余り１の割り算の式が、必ず問題の式の形にできるのか

解説のため、専門用語を１つだけ、、、

23 × ? + 16 × ?（23と16を定数倍して足したもの）は23と16の線形結合と言います。
大学数学でよく使うようになる言葉なんですが、便利な言葉です。

他に例えば、$3\vec{a}+2\vec{b}$ は $\vec{a}$と$\vec{b}$ の、$6f(x)-5g(x)$ は $f(x)$と$g(x)$ の線形結合です。

上の式(上の図)の割り算の式たちを見ればすぐわかるように、

割り算の 余りは、割る数、割られる数の線形結合です(で表せます)。

また、$23$ と $16$ の線形結合の線形結合は、必ず $23$ と $16$ の線形結合として表せます。

これはなぜなら例えば、$\vec{a}, \vec{b}$ の線形結合である、$3\vec{a}+2\vec{b}$ と$\vec{a}-\vec{b}$ の線形結合、例えば、

$2\times (3\vec{a}+2\vec{b}) + 3\times (\vec{a}-\vec{b}) = 9\vec{a}+\vec{b}$

もまた $\vec{a}, \vec{b}$ の線形結合ですよね。

この赤い字の２つのことから上の図で、

$7$ は $23, 16$ の線形結合で表せて、

次に$2$ は $16, 7$ の線形結合で表せているから$23, 16$ の線形結合で表せて、

最後に$1$ は $7, 2$ の線形結合で表せているから$23, 16$ の線形結合で表せる。

と、、、

「$23$ と $16$ の線形結合で表せる」が次の割り算へ連鎖していくことになります。

というわけでしたー

そして具体的な変形の手順は、

最後の１以外の余り（ここでは2と7）の、割る数と割られる数の線形結合としての表し方（右辺）を最後の余り１の割り算の式に代入していけばいいです。具体的には、

$7-2 \times 3 = 1$

に$16 -7 \times 2 = 2$ を代入して、

$7- (16 - 7 \times 2) \times 3 = 1$
⇔  $7 \times 7 - 16 \times 3 = 1$

に$23 -16 \times 1 =7$ を代入して、

$(23 - 16 \times 1 ) \times 7 -16 \times 3 = 1$
⇔ $23 \times 7 - 16 \times 10 = 1$

とやって、$23x + 16y = 1$ の特殊解 $(x,y) = (7, -10)$ が求まりました。

（「⇔」という記号が馴染み無いかもしれませんね。同値、同じ意味、という意味です）

まとめ

以上、なぜユークリッドの互除法で特殊解が求められるのか？、について重要なポイントだけ申しますと

• ２つの互いに素な数から始めたユークリッドの互除法では、最終的に余り１の割り算に行き着くことが保証されている
• $m$ と $n$ の線形結合(定数倍して足し合わせたもの)の線形結合は、それまた $m$ と $n$ の線形結合で表せる。
  ここで「$m$ と $n$」というのは、「23と16」、「$\vec{a}$ と $\vec{b}$」、「$f(x)$ と $g(x)$」とか、足せるならなんでも
• 割り算たちの中の、「互いに素」と「線形結合で表せる」の連鎖に注目

まーよくできてんなあ、と思いましたかね。なぜ使えるか理解できても、どうやってこんなよくできた方法を思いつくんだろうとはまだ思いますね。天才じみてるユークリッドさん。

ここまで読んでくださって、ありがとうございますた、お疲れ様です、すきです。

余談

上記のことを理解すれば、

全ての整数は、互いに素な２つの数の線形結合で表せる

ということが分かってしまいます。(当たり前のような、そうでもないような)

余裕があればこれがなんでか、頑張って考えてみてください。

また、こんなのが何の役に立つのだろうと思った方へ、ぼくもそう思っていました。

がしかし、ぼくには役立つときがあったんですよ。

ぼくは大学で物理工学系の人だったんですが、

ある結晶の結晶面の間隔を求めるときに必要になったんですよー（？？？？？）

わけわからんと思いますが、とにかくなんか物質の構造を理解するのに必要になったということでした。

もしかしたら他の学問でも必要になるときがあるのかもしれませんね。