一次不定方程式ax+by=cの整数解

この記事では,一次の不定方程式,つまり ax+by=cax+by=c を満たす整数 (x,y)(x,y) を探す問題を考えます。

重要な定理の証明と,不定方程式の一般解を求める方法を説明します。

不定方程式の例

この記事では,a,ba,b は正の整数,cc は整数とします。

ax+by=cax+by=c という不定方程式は,整数解を持たない場合と,無数の整数解を持つ場合があります。

それぞれの例を見てみましょう。

例題1

2x+4y=12x+4y=1 という不定方程式を満たす整数 (x,y)(x,y) は存在するか?

解答

(x,y)(x,y) が整数のとき,2x+4y2x+4y は偶数になる。

よって,2x+4y=12x+4y=1 になることはない。よって,この不定方程式に整数解は存在しない。

例題2

3x+5y=23x+5y=2 という不定方程式を満たす整数 (x,y)(x,y) は存在するか?

解答

実は,mm を整数として, (x,y)=(4+5m,23m)(x,y)=(4+5m,-2-3m) とすると,(x,y)(x,y) は解になる。実際,

3(4+5m)+5(23m)=23(4+5m)+5(-2-3m)=2

となる。なお,上記の解の見つけ方は記事の後半で説明する。

不定方程式の整数解についての定理

2x+4y=12x+4y=1整数解無しで,3x+5y=23x+5y=2整数解が無数にありました。では,ax+by=cax+by=c が整数解を持つのはどのような場合でしょうか? その答えが,以下の定理です。

定理1

x,yx,y に関する不定方程式 ax+by=cax+by=c が整数解を持つ
    \iffccgcd(a,b)\mathrm{gcd}(a,b) の倍数

ただし,gcd(a,b)\mathrm{gcd}(a,b)aabb の最大公約数を表します。

例えば,

  • 2x+4y=12x+4y=1 という不定方程式については,11gcd(2,4)=2\mathrm{gcd}(2,4)=2 の倍数ではないので,整数解を持たないことが分かります。

  • 3x+5y=23x+5y=2 という不定方程式については,22gcd(3,5)=1\mathrm{gcd}(3,5)=1 の倍数なので,整数解を持つことが分かります。

特に,定理1で c=1c=1 とした,以下の定理2が重要です。

定理2

ax+by=1ax+by=1 が整数解を持つ
    \iffaabb は互いに素

定理2の証明

まず,定理2「ax+by=1ax+by=1 が整数解を持つ     \iff aabb が互いに素」を証明します。

方針

\Rightarrow は対偶を取れば簡単です。 \Leftarrow の証明は 非常に有名なテクニックを使うのでまるごと覚えておくとよいでしょう。

証明

\Rightarrow の対偶を証明します。

aabb が互いに素でないとき,aabb の公約数の1つを d2d\geq 2 とおくと ax+byax+bydd の倍数となり解を持たない。

\Leftarrow を証明します。

aabb が互いに素なとき a,2a,3a,,(b1)aa,2a,3a,\cdots,(b-1)abb で割った余りは全て異なる(※)ので,余りが1となるようなものが存在する。

それを mama とおき,bb で割った商を nn とおくと,

ma=bn+1ma=bn+1

つまり,ambn=1am-bn=1 となり (m,n)(m,-n) は整数解になっている。

※の証明(背理法)

iaiaja(i>j)ja\:(i>j)bb で割った余りが同じだと仮定すると,(ij)a(i-j) abb の倍数となるはずだが,1ij<b1\leq i-j < b かつ aabb は互いに素なのでこれは矛盾。

定理1の証明

ax+by=cax+by=c が整数解を持つ     \iff ccgcd(a,b)\mathrm{gcd} (a,b) の倍数,を証明します。

方針

\Rightarrow はさきほどと同様に簡単です。 \Leftarrow もさきほどの結果からすぐに分かります。

証明

\Rightarrowを証明します。

a,ba,bgcd(a,b)\mathrm{gcd} (a,b) の倍数なので整数解 m,nm,n に対して am+bnam+bngcd(a,b)\mathrm{gcd} (a,b) の倍数。つまり ccgcd(a,b)\mathrm{gcd} (a,b) の倍数。

\Leftarrow を証明します。

a=pgcd(a,b)a=p\cdot\mathrm{gcd} (a,b) , b=qgcd(a,b)b=q\cdot\mathrm{gcd} (a,b) とおける(ただし p,qp,q は互いに素)。

さきほどの結果から pm+qn=1pm+qn=1 は整数解を持つので両辺を gcd(a,b)\mathrm{gcd}(a,b) 倍して,

am+bn=gcd(a,b)am+bn = \mathrm{gcd} (a,b)

も整数解を持つことが分かる。

よって,ccgcd(a,b)\mathrm{gcd}(a,b) の倍数のとき,両辺を適当に整数倍すれば右辺が cc となるので ax+by=cax+by=c は整数解を持つ。

なお,ユークリッドの互除法を用いた構成的な証明方法もあります。 →ユークリッドの互除法の証明と不定方程式

一次不定方程式の解き方

不定方程式 ax+by=1ax+by=1 に解が存在する場合に,その一般解を求める問題は頻出です。

一次不定方程式の解き方
  1. 定理2の証明中の方法,またはユークリッドの互除法,または直感で解 (x0,y0)(x_0,y_0) を1つ求める。

  2. もとの方程式と引き算して a(xx0)+b(yy0)=0a(x-x_0)+b(y-y_0)=0 の形にする。

  3. 一般解を求める

具体例で説明します。

例題2(再掲)

3x+5y=23x+5y=2 の整数解を求めよ。

解答

1. まず整数解を1つ求める。

直感で求めても良い。難しい場合は,定理2の証明中の方法を使う。つまり,a=3a=3 の倍数 3,6,9,123,6,9,12 の中で b=5b=5 で割って 22 余るものを見つけると 1212 が当たり。よって,割り算の式を書くと

34=52+23\cdot 4=5\cdot 2+2

となり,(4,2)(4,-2)3x+5y=23x+5y=2 の整数解になっていることが分かる。

2. もとの方程式と引き算する。

見つけた解: 34+5(2)=23\cdot 4+5\cdot (-2)=2

と元の方程式を辺々引き算して

3(x4)+5(y+2)=03(x-4)+5(y+2)=0

を得る。

3. 一般解を求める

3355 が互いに素なので,

x4=5mx-4=5m とおける。このとき y+2=3my+2=-3m となる。

つまり,一般解は (x,y)=(4+5m,23m)(x,y)=(4+5m,-2-3m)

数が非常に大きい問題は入試では出ないと思いますが,その場合は1つの解をユークリッドの互除法を用いて求めた方が早いです。どちらの方法も使えるようになっておきましょう。

ちなみに,一次不定方程式 ax+by=cax+by=c には「ベズーの等式(Bezout’s identity)」という立派な名前がついています。

→高校数学の問題集 ~最短で得点力を上げるために~の97では,不定方程式の問題と計算ミスを減らすコツを解説しています。

特殊解と同次方程式の一般解の和で表すのは大学に入ってからもよく出てくる形です。

Tag:不定方程式の解き方まとめ

Tag:素数にまつわる覚えておくべき性質まとめ

Tag:数学Aの教科書に載っている公式の解説一覧