Top / 不定方程式

不定方程式

Tweet

目次 †

1次の不定方程式 †

　整数a,b,cについて、次の方程式の整数解を求める問題を取り上げる。

ax+by=c　←(*)

　不定方程式(*)を解くことは、幾何学的に考えれば、直線ax+by=c上の整数点（座標が両方とも整数の点）を求めることと同じである。

1次の不定方程式(*)について、次のように完全な答えを与えることができる。

[定理]d=GCD(a,b)と置くと次が成り立つ。
[1]cがdの倍数でなければ、(*)は整数解を持たない。
[2]cがdの倍数ならば、(*)は整数解を（少なくとも1つ）持つ。
また、x=x0,y=y0が(*)の1つの解であれば、(*)のすべての解が次の形で与えられる。
　←(**)
ただし、tは任意の整数である。

[証明]方程式(*)が整数解を持ったとすれば、dは(*)の左辺を割り切るので、dは((*)の右辺である)cを割り切らなくてはならない。これで[1]の待遇が示されたので、[1]が成り立つ。

今度は、逆にdがcを割り切ると仮定する。このときは、ユークリッドの互除法によって、方程式ax+by=dの整数解x=x*,y=y*を求めることができる。

x=x*,y=y*が(*)の解であることより、任意の整数tに対して(**)が(*)の解であることはすぐに確かめられる（代入して計算するだけである）。

逆に、x,yが(*)の解であるとすれば、等式(*)からax0+by0=cを引き算すれば、

a(x-x0)+b(y-y0)=c-c=0

となるので、a(x-x0)=-b(y-y0)が成り立つ。

さらに、d=GCD(a,b)で割れば、次が得られる。

　←(***)

ここで、a/dとb/dは互いに素なので、(***)からb/dがx-x0を割り切ることがわかる。つまり、ある整数tによって、と表される。

これを(***)に代入すると、が得られる。　□

2次の不定方程式 †

√dとの関係 †

　自然数dに対して、√dは有理数かという問題を考える。

　この問題は2じの不定方程式x2-dy2=0が自然数解を持つかどうかという問題と関連している。

不定方程式が解が持たないことを示すために合同式を利用する †

　次の命題は簡単だが、知っていると役に立つことが多い。

[命題]整数xに対して、以下が成り立つ。

x2≡0 or 1 (mod 4)

[証明]整数xは4を法とした場合、0,1,2,3のどれかに合同である。x=0,1,2,3の場合のx2を4で割った余りを計算する。

この表から、x2 (mod 4)の値は0 or 1しかない。　□

　この命題は、言い換えれば、平方数は4を法として2や3に合同になることはない。

[注意]例えば、17≡1 (mod 4)なので、上記の命題より17は平方数というのは間違いである。明らかに17は平方数ではない。

上記の命題は平方数であるためには0または1と合同でなければならないということであり、0または1と合同であれば必ず平方数になるというのはではない。　◇

　さらに、詳しい次の命題も示すこともできる。

[命題]整数xに対して、以下が成り立つ。

x2≡0 or 1 or 4 (mod 8)

[証明]整数xは8を法とした場合、0,1,2,3,4,5,6,7のどれかに合同である。x=0,1,2,3,4,5,6,7の場合のx2を8で割った余りを計算する。

この表から、x2 (mod 4)の値は0 or 1しかない。　□

[別証][1]xが偶数ならx=2y(yは整数)と表すことができ、x2=4y2である。

このとき、yが偶数なら、y2も偶数であるから、「x2=4y2=4×偶数=8の倍数」である。
また、yが奇数なら、y2も奇数であるから、「x2-4=4(y2-1)=4×(奇数-1)=4×偶数=8の倍数」である。

[2]xが奇数ならx=2z+1(zは整数)と表すことができ、x2-1=(2z+1)2-1=4z2+4z=4z(z+1)となる。zかz+1はどちらかが偶数でるため、x2-1は8の倍数である。　□

不定方程式が解を持たないことを平方剰余の性質から求める †

[例]次を満たす整数解を持たないことを示す。

x2-21y2=38　←(*)

[証明]背理法で証明するために、(*)が整数解x,yを持つと仮定する。

このとき、38の素因数である19に注目して、平方剰余の考察を行っていく。

さて、もし19|yであれば、(*)によって、19|x2が成り立つ。

すると、19は素数であるから、19|xとなる。

これで、x,yが共に19で割り切れることになったので、(*)の左辺は192で割り切れる。

しかし、(*)の右辺は192では割り切れないから、これは矛盾する。

したがって、yは19と互いに素でなくてはならない。

(*)の両辺を19を法として考えると、次が成り立つことがわかる。

x2-21y2≡0 (mod 19)
x2-2y2≡0 (mod 19)　←(**)　（∵21≡2 (mod 19)）

yが19で割り切れないので、19を法とするyの逆数y-1が存在する。

(**)の両辺に(y-1)2を掛けると、次が得られる。

(xy-1)2≡2 (mod 19)

これは2が19を法とする平方剰余であることを示しているが、これは(2/19)=-1（2は法19の平方非剰余の1つだから）という事実に矛盾している。　◇

不定方程式が解を持たないことへの応用 †

[例]不定方程式x2-xy-2y2=-1は解を持たないこと（方程式を満たす整数x,yは存在しないこと）を示す。

方程式を満たす整数x,yが存在すると仮定する。

ここで、3を法として、xとyは0,1,2のどれかに合同である。これらの値の組み合わせについて、x2-xy-2y2の値を計算して、表を作る。

よって、x2-xy-2y2≡0 or 1である。

• 1≡2 (mod 3)であるから、x2-xy-2y2は解を持たないことがわかる。　◇

[補講]双曲線x2-xy-2y2=-1（双曲線の漸近線はx+y=0とx+2y=0）が格子点を通らないことを意味している。　◇

参考文献 †

• 『算数からはじめよう！数論』