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

【爆速】一次不定方程式の整数解を合同式で見つける方法

a,\,b,\,cを整数の定数,x,\,yを整数の変数として、

ax+by=c

の形をした方程式を一次不定方程式といいます。一次不定方程式を満たす整数x,\,yの組をすべて見つけることを不定方程式を解くといいます。

一次不定方程式を解くために、まずは一次不定方程式を満たす整数解を一組見つけます。そのための方法として、

  1. ユークリッドの互除法の利用
  2. 合同式

の2種類があります。どちらでも構いませんが、合同式でやるほうが早いのでおすすめです。今回は、合同式を使って一次不定方程式を解く方法を解説します。

低い係数を法にする

それでは、合同式を使って一次不定方程式の整数解を見つけましょう。

一次不定方程式

ax+by=c

があるとき、低い係数を法として合同式をとります。仮にa>bだとすれば、\bmod{b}とすればby\equiv 0なので

ax\equiv c

となります。

この合同式を、合同式の変形規則を用いて

x\equiv \alpha

の形に変形することが目標です。これを合同式を解くと言います。

合同式を解くときには、次の変形規則を使います。

合同式の変形規則

x\equiv y,\,z\equiv w\pmod{p}のとき、

  • x+z\equiv y+w
  • x-z\equiv y-w
  • xz\equiv yw
  • x\equiv y \implies x^n\equiv y^n
  • kpが互いに素なとき、kx\equiv ky\implies x\equiv y
  • x\equiv y \implies x^n\equiv y^n

規則はシンプルで、両辺に法として同じ数を加法、減法、乗法してよいということです。ただし、除法は法と割る数が互いに素であることが条件なので注意してください

③において、z=x,\,w=yとおくと、

x\equiv y\implies x^2\equiv y^2

となり、これを繰り返せば④が導けます。

これを使えば、指数部をそのままにして底を合同な数同士で変換することが出来ます。

例えば、\bmod\ 3として、11\equiv 2なので、

11^4\equiv 2^4 \equiv 1

が成立します。

ココに注意

指数部を変換することはできません

例えば、\bmod\ 5だからと言って、

3^7\equiv 3^2

成り立ちません。うっかりやってしまうことが多いミスなので、気をつけてください。

合同式で変換できるのは底の数だけです。

また、⑤は合同式の除法として使えます。ただし、これは法と割る数が互いに素じゃないと使えないので要注意です。ただし、基本的に除法をしたくなるケースはほとんど出てこないので、出来るだけ使わないことをおすすめします。

一次不定方程式と例題

それでは、実際に一次不定方程式で使ってみましょう。

26x+11y=1

を満たす整数x,\,yの組を1つ求めます。このときは、2611で小さい方の11を法に設定します(大きい方でもいいのですが、解を見つけるのが大変になるかもしれません)。以下\bmod\ 11を法とします。11y\equiv 0より、

26x\equiv 1

です。26\equiv 4\pmod{11}より

4x\equiv 1

この両辺を定数倍して、11で割ったときに余りが1になるようにします。今は3倍すると、

12x\equiv 3

となり、12x\equiv xなので

x\equiv 3

になります。よって、例えばx=3が整数解のひとつです。これを26x+11y=1に代入すれば、y=-7も分かります。

これで整数解がひとつわかったので、あとは通常の不定方程式の解法に従って、すべての解を求めることができます。

ちなみに、合同式を使うと、そのまま任意の整数解を一気に求めることも出来ます

先程の問題の続きから、

x\equiv 3\pmod{11}

なので、kを任意の整数としてx=11k+3と表せます。

これを元の式に代入すれば、y=-26k-7がわかりますね。

任意の整数解まで一気に分かるのがこの方法のメリットです。

慣れるまでは合同式を変形するのが難しいかもしれませんが、慣れると簡単です。さらに練習してみます。

練習問題

第1問

30x+17y=5

の整数解を求めます。

\bmod\ 17として

\begin{aligned} 13x&\equiv 5\\ 52x&\equiv 20\\ x&\equiv 20\\ &\equiv 3 \end{aligned}

となります。最後はx\equiv 20になるので、x\equiv 3に落としたほうがよいでしょう。よって整数解のひとつはx=3,\,y=-5となり、任意の整数解はx=17k+3,\,y=30k-5と表されます。

第2問

43x-32y=4

\bmod\ 32として

\begin{aligned} 11x&\equiv 4\\ 33x&\equiv 12\\ x&\equiv 12 \end{aligned}

より、x=12,\,y=16は整数解のひとつです。

一般解は、x=32k+12,\,y=43k+16です。

第3問

36x+25y=2

\bmod\ 25として

\begin{aligned} 11x&\equiv 2\\ 22x&\equiv 4\\ -3x&\equiv 4\\ -24x&\equiv 32\\ x&\equiv 32\\ &\equiv 7 \end{aligned}

より、x=7,\,y=10は整数解のひとつです。

一般解は、x=25k+7,\,y=36k+10です。

一次不定方程式は、合同式を使うことで高速に解くことが出来るので、ぜひ身に着けておきましょう。

高評価&応援のお願い

ラディカル高校数学は、2021年11月から大規模更新を開始します!

高校数学全分野をカバーする記事を皆様にお届けするために、毎日更新で全300記事を目指します

今回の記事がいいなと思ったら、ぜひ下の❤を押して高評価をお願いします皆さんの応援がとても励みになります。

今後ともラディカル高校数学をよろしくお願い致します!

  • この記事を書いた人
  • 最新記事

岡田

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

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