1 一次不定方程式とベズーの等式
整数a,b,cに対し、ax+by=cを満たす整数の組(x,y)を求める方程式を、一次不定方程式といいます。解を一つ固定したとき、その解を特殊解と呼びます。
補題 1.1.a,bを少なくとも一方が0でない整数とし、d=gcd(a,b)とする。整数r,sが存在してar+bs=dが成り立つ。この等式をベズーの等式という。
証明.a=0ならr=0,s=b/∣b∣とし、b=0ならr=a/∣a∣,s=0とすると、ar+bs=dとなる。a,bがともに0でない場合、∣a∣,∣b∣に互除法を適用する。§A4.1 定理 3.3により、互除法は有限回で停止し、最後の除法で割る数はdである。最初の二数∣a∣=(a/∣a∣)a,∣b∣=(b/∣b∣)bは、a,bの整数係数の和である。各段の余りは、直前の二数の一方から他方の整数倍を引いたものなので、余りもa,bの整数係数の和である。したがって最後の除法で割る数dも整数係数の和となり、ar+bs=dを満たす整数r,sが得られる。▨
2 整数解の存在と一般解
定理 2.1.a,b,cを整数とし、a,bの少なくとも一方が0でないとする。d=gcd(a,b)とおく。ax+by=cが整数解をもつための必要十分条件は、dがcを割り切ることである。整数解(x0,y0)が一つ存在するとき、すべての整数解は
x=x0+dbt,y=y0−dat(t∈Z)で表され、各解に対応する整数tはただ一つに定まる。
証明. 整数解(x,y)が存在するとき、dはa,bをともに割り切るので、c=ax+byを割り切る。逆にdがcを割り切るとき、補題 1.1によりar+bs=dを満たす整数r,sを取ると、(x0,y0)=((c/d)r,(c/d)s)は整数解である。
任意の特殊解(x0,y0)を固定する。任意の整数tから定理の表示式で定めた(x,y)は整数の組であり、
ax+by=ax0+by0+dabt−dabt=cを満たす。任意の整数解(x,y)について、u=x−x0,v=y−y0,A=a/d,B=b/dとおく。Au+Bv=0であり、上で取った整数r,sはAr+Bs=1を満たす。したがって
u=(Ar+Bs)u=B(su−rv),v=(Ar+Bs)v=−A(su−rv)となる。整数t=su−rvを取ると、(x,y)は定理の表示式で表される。同じ解を与える二つの整数t,t′に対してB(t−t′)=A(t−t′)=0となる。A,Bの少なくとも一方は0でないので、t=t′である。▨
3 互除法からの計算
例 3.1.1071x+1029y=21を解く。互除法により
- 1071=1×1029+42
- 1029=24×42+21
- 42=2×21+0
であり、gcd(1071,1029)=21である。余りの式を逆にたどると
21=1029−24×42=1029−24(1071−1029)=−24×1071+25×1029となるので、(−24,25)は特殊解である。定理 2.1より、一般解は
x=−24+49t,y=25−51t(t∈Z)である。右辺が63=3×21の場合には、特殊解を3倍して(−72,75)を得る。この場合の一般解はx=−72+49t,y=75−51t（t∈Z）である。
4 非負整数解
問題 4.1. 方程式7x+11y=100の非負整数解をすべて求めよ。また、7x+11y=10は整数解をもつが、非負整数解をもたないことを示せ。
解答.
7×(−3)+11×11=100なので、定理 2.1より、第一の方程式の一般解はx=−3+11t,y=11−7t（t∈Z）である。整数tに対して、x≥0はt≥1と同値であり、y≥0はt≤1と同値である。したがってt=1に限られ、非負整数解は(8,4)だけである。
第二の方程式では7×3+11×(−1)=10なので整数解が存在し、定理 2.1より、一般解はx=3+11t,y=−1−7t（t∈Z）である。整数tに対して、x≥0はt≥0と同値であり、y≥0はt≤−1と同値である。両方を満たす整数tは存在しないので、非負整数解はない。▨
閑話休題：ダイ・ハード3の水差しパズル 映画『ダイ・ハード3』には、爆弾を止めるために、3ガロンと5ガロンの容器だけを使って正確に4ガロンの水を作る場面があります。同じ容量の関係をもつ3リットルと5リットルの容器で、4リットルを量る操作を考えます。
許された操作は、容器を満たすこと、空にすること、他方が満杯になるか注ぐ側が空になるまで水を移すこととします。
3Lと5Lの容器に入っている水量を、この順に組で表します。空の状態から
(0,0)→(3,0)→(0,3)→(3,3)→(1,5)→(1,0)→(0,1)→(3,1)→(0,4)と操作すると、5Lの容器に4Lが残ります。外から加えた水は3Lを3回、捨てた水は5Lを1回なので、残った水量は3×3−5=4です。この操作により、3x+5y=4の整数解(3,−1)に対応する水量が実現します。
6Lと9Lの容器では、空の状態から同じ種類の操作を何回行っても、それぞれの容器の水量は3の倍数です。満たす操作と空にする操作はこの性質を保ちます。移す操作では、注ぐ側の水量と受ける側の空き容量はいずれも3の倍数です。移す操作で移る水量はこの二つの量の小さい方なので、操作後の水量も3の倍数です。したがって4Lを量ることはできません。また、gcd(6,9)=3は4を割り切らないので、定理 2.1により6x+9y=4に整数解はありません。
5 例題
次の1次不定方程式の整数解を1組求め、一般解を書け。
解法の型互除法を逆にたどって特殊解を1組見つける
例 5.1.
14x+11y=−200答(−8, −8)（一般解x=−8+11t, y=−8−14t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.2.
9x+7y=−117答(−6, −9)（一般解x=−6+7t, y=−9−9t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.3.
7x+2y=−23答(−1, −8)（一般解x=−1+2t, y=−8−7t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.4.
3x+14y=23答(3, 1)（一般解x=3+14t, y=1−3t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.5.
4x+13y=−110答(−8, −6)（一般解x=−8+13t, y=−6−4t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.6.
4x+3y=−17答(−8, 5)（一般解x=−8+3t, y=5−4t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.7.
4x+5y=−12答(2, −4)（一般解x=2+5t, y=−4−4t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.8.
14x+13y=−137答(−7, −3)（一般解x=−7+13t, y=−3−14t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.9.
10x+3y=−9答(−3, 7)（一般解x=−3+3t, y=7−10t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
例 5.10.
5x+13y=−55答(2, −5)（一般解x=2+13t, y=−5−5t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）
6 演習
次の1次不定方程式の整数解を1組求め、一般解を書け。
解法の型互除法を逆にたどって特殊解を1組見つける
問題 6.1.
11x+9y=−78解答.
答(−3, −5)（一般解x=−3+9t, y=−5−11t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.2.
11x+2y=29解答.
答(3, −2)（一般解x=3+2t, y=−2−11t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.3.
13x+10y=−101解答.
答(−7, −1)（一般解x=−7+10t, y=−1−13t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.4.
11x+6y=37解答.
答(−1, 8)（一般解x=−1+6t, y=8−11t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.5.
11x+8y=−15解答.
答(3, −6)（一般解x=3+8t, y=−6−11t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.6.
9x+14y=67解答.
答(−5, 8)（一般解x=−5+14t, y=8−9t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.7.
8x+11y=68解答.
答(3, 4)（一般解x=3+11t, y=4−8t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.8.
7x+6y=2解答.
答(2, −2)（一般解x=2+6t, y=−2−7t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.9.
6x+7y=41解答.
答(8, −1)（一般解x=8+7t, y=−1−6t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.10.
13x+15y=−196解答.
答(−7, −7)（一般解x=−7+15t, y=−7−13t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.11.
6x+5y=−1解答.
答(4, −5)（一般解x=4+5t, y=−5−6t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.12.
2x+3y=−10解答.
答(−8, 2)（一般解x=−8+3t, y=2−2t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.13.
14x+11y=59解答.
答(5, −1)（一般解x=5+11t, y=−1−14t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.14.
13x+9y=8解答.
答(2, −2)（一般解x=2+9t, y=−2−13t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨
問題 6.15.
4x+11y=−48解答.
答(−1, −4)（一般解x=−1+11t, y=−4−4t）
注意 解は1組見つかれば一般解が書ける（答えの特殊解は一例）▨