ユークリッドの互除法 数学A 整数の性質

ユークリッドの互除法で一次不定方程式の整数解を見つける方法

一次不定方程式

ax+by=c

の整数解を見つける方法は、主に

  • ユークリッドの互除法をトップダウン方式で辿っていく方法
  • 合同式を使う方法

の2種類があります。合同式を使う方法については、次の記事をお読みください。

個人的には、合同式を使う方法の方が圧倒的に高速に求められるのでおすすめですが、今回はユークリッドの互除法を辿っていくことで整数解を見つける方法を解説します。

一次不定方程式の整数解を求める手順

最初に、ax+by=cの整数解を求める手順をまとめます。

一次不定方程式の整数解をユークリッドの互除法で求める方法

  1. a,\,bにユークリッドの互除法を余りが1になるまで繰り返す
  2. 最初の式から余りが1になるまでの式をすべてabで書き直す
  3. 上から順に\square a+\triangle b = \bigstar になっている完成形の\bigstarを代入していき、\square a+\triangle b = 1を目指す
  4. 最後のabの係数が求める整数解になる

この方法は、

  • 上から順に機械的に代入していくため、順番がわかりやすい
  • 文字で置いてしまうため、計算ミスをしにくい

という大きなメリットがあります。正直、他の方法では考えられなくなるぐらい簡単です。

実際にやってみましょう。

step
1
a,\,bの最大公約数をユークリッドの互除法を使って求める


一次不定方程式

ax+by=c

の整数解を求めるときには、まず最初にa,\,bに対してユークリッドの互除法を余り1になるまで繰り返します。

ユークリッドの互除法とは、次のような定理です。

ユークリッドの互除法

自然数a,\,bについて、abで割ったときの余りをrとすると、abの最大公約数は、brの最大公約数に等しい。

このように覚えておくとよいでしょう。

ココがポイント

2つの数があるとき、片方の数から、残りの数を整数倍したものを引いても最大公約数は変わらない。

ユークリッドの互除法を使うと、2つの数a,\,bや文字式の最大公約数を簡単に求めることが出来ます。ユークリッドの互除法を使って最大公約数を求める方法と実戦での使い方についてはこちらの記事で扱っているので、ぜひご覧ください。ユークリッドの互除法は、こちらの使い方のほうが重要です。

 

例題

今回は、例題として一次不定方程式

154x+69y=1

の整数解を求めます。

まずは15469に対してユークリッドの互除法を余りが1になるまで繰り返します

154から692倍して引くと

154-69\times2=16

69から164倍して引くと

69-16\times4=5

16から53倍して引くと

16-5\times3=1

となり、余りが1になりました。ここで終了です。

余りが1になったということは、15469の最大公約数が1、つまり互いに素だということです。

一次不定方程式ax+by=cが整数解を持つ条件は、abが互いに素であることなので、整数解があるならば最後は必ず余り1になります。もし余り1にならなければ、元の一次不定方程式の整数解が存在しないということなので、方針を見直す必要があります。

ax+by=cの整数解を求めるには、ユークリッドの互除法の履歴をこの後に使うので残しておく必要があります。次のように書いておきましょう。

\begin{aligned} 154-69\times2&=16\\ 69-16\times4&=5\\ 16-5\times3&=1 \end{aligned}

これでステップ1は終了です。次のステップ2に進みます。

step
2
最初の係数abで書き換える

次に、先ほどのユークリッドの互除法の計算過程を最初の係数abで置き直します

これは、このあと計算していく上でどこを計算したら良いのかの見通しをつけやすくするためです。このまま計算を続けると、数字がゴチャゴチャして訳が分からなくなります。

今、最初の係数はa=154,\,b=69だったので、次のように書き換えます。

\begin{aligned} a-b\times2&=16\\ b-16\times4&=5\\ 16-5\times3&=1 \end{aligned}

一行目の2文字と2行目の1文字の合計3文字abに書き換わるはずです。それ以外は書き換えないでください。

これでステップ2は終わりです。最後のステップ3に進みます。

step
3
完成形を作り上から代入していく


ユークリッドの互除法の途中変形で

\square a+\triangle b = \bigstar

の形になっている式を完成形と呼ぶことにします。これは私が勝手に名付けているだけで、数学用語としてあるわけではありません。この形になっていれば完成しているという意味で、これ以上やることはないので次の式に進むという意味です。

1行目の

a-b\times2=16

を見ます。これは完成形\square a+\triangle b = \bigstar(\square=1,\,\triangle=-2,\,\bigstar=16)になっているのでこれ以上やることがありません。この式はこれで終了です。これを16は完成した」と呼ぶことにします。1行目は必ず既に完成しています

完成形になったら、完成形の\bigstar次の行の同じ\bigstarに代入します。今は完成した16を次の行の

b-16\times4=5

に代入します。したがって、

b-(a-2b)\times 4=5

になります。これを計算します。そうすると

-4a+9b=5

になり、これは完成形になっています。よって、これで終了です。新たに5が完成しました。

完成した5を次の式の5に代入します。このとき、既に完成している16も同時に代入します。目標は次の式を完成形にすることなので、既に完成している余りを2種類同時に使います。今は完成した16516-5\times3=1に代入して

(a-2b)-(-4a+9b)\times 3=1

になります。このとき、2種類代入するのを忘れて片方しか代入しないと定数が余ってしまい上手くいかないので注意してください。3行目以降は、必ず2種類代入します。

計算すると、

13a-29b=1

となります。右辺が1になったらすべて終了です。これは

154\times 13 + 69\times(-29)=1

を意味しているので、154x+69y=1の整数解のひとつはx=13,\,y=-29と得られます。目標は達成です。

よくある他の方法のデメリット

教科書や参考書には次の方法が載っていることが多いでしょう。

余り1になるまで互除法をするところまでは同じですが、次に余りを左辺に移し、残りを右辺に残して

\begin{aligned} 16&=154-69\cdot 2\\ 5&=69-16\times4\\ 1&=16-5\times3 \end{aligned}

とし、1から逆に辿っていって

\begin{aligned} 1&=16-5\cdot 3\\ &=16-(69-16\times4)\cdot3\\ &=16\cdot13+69\cdot(-3)\\ &=(154-69\cdot2)\cdot 13+69\cdot(-3)\\ &=154\cdot13+69\cdot(-29) \end{aligned}

より154\cdot13+69\cdot(-29)=1となります。

しかし、こんな大変な計算を本番でできるでしょうか。途中で何を計算したら良いのか訳が分からなくなりませんか。あと、そもそも余りを左辺に移したりする必要がありません。

計算に時間と手間がかかりミスが多く、まったく実戦向きではありませんので、逆側から求めていくこのボトムアップ方式はおすすめ出来ません。

おすすめは、上から順に代入していくトップダウン方式です。この方が

  • 計算の順番を見失わない
  • 文字で置いてしまうので式が見やすい
  • 完成形を作って行くだけなので単純

といったメリットが多いです。

ただし、そもそも整数解を求めるだけでいいのなら合同式を使った方法が早いです。

ユークリッドの互除法は、

  • 最大公約数を求めるとき
  • 2つの文字式の公約数を考えるとき

に使うのがおすすめで、一次不定方程式を解くために使うのはあまり向きません。

目的に応じて方法を使い分けられるようにしておきましょう!

今回のまとめ

  • 一次不定方程式の整数解をユークリッドの互除法で見つける
  • ユークリッドの互除法のトップダウン方式の使い方
  • ボトムアップ方式はわかりにくい
  • この記事を書いた人
  • 最新記事

岡田

ラディカル高校数学管理人の岡田です。地方公立高校から一浪して東京大学理科一類に合格。現在工学部在学中。都内で塾講師として高校数学を教え、100人以上の生徒を見てきました。自分の経験を活かして高校数学をわかりやすく教える活動をしています!

-ユークリッドの互除法, 数学A, 整数の性質