1. 高校数学の美しい物語
  2. 一次不定方程式ax+by=cの整数解

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

更新日時 2021/03/07

不定方程式とは,3x+5y=23x+5y=2 のように,方程式の数よりも未知変数の数が多いような方程式のことです。

この記事では,ax+by=cax+by=c という不定方程式の整数解について,重要な定理の証明と,実際に不定方程式の一般解を求める方法を説明します。

目次
  • 不定方程式の例

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

  • 定理2の証明

  • 定理1の証明

  • 一次不定方程式の解き方

不定方程式の例

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

(x,y)(x,y) が整数のとき,2x+4y2x+4y は偶数なので,2x+4y=12x+4y=1 になることはありません。よって,この不定方程式に整数解は存在しません。

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) は解になります。

このように,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の証明

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

方針

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

証明

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

aabb の公約数を 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:一般解を求める

具体例で説明します。

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)」という立派な名前がついています。

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

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

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

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

人気記事
  1. 高校数学の美しい物語
  2. 一次不定方程式ax+by=cの整数解