不定方程式と格子点

一次不定方程式の整数解

$ax+by=c$ の整数解は、 $1$ つ見つかれば $x$ を $\dfrac{b}{g}$ ずつ・ $y$ を $\dfrac{a}{g}$ ずつずらして全部書ける( $g=\gcd(a,b)$ )。直線の上に等間隔に並ぶ格子点だよ。

主張

$a,b,c$ を整数とする一次不定方程式 $ax+by=c$ は、 $g=\gcd(a,b)$ が $c$ をわり切るときに限って整数解をもつ。そして整数解が $1$ つ $(x_0,y_0)$ 見つかれば、すべての整数解は $x=x_0+\dfrac{b}{g}t$ 、 $y=y_0-\dfrac{a}{g}t$ ( $t$ は整数)で書ける。座標で見ると、整数解は直線 $ax+by=c$ の上に等間隔で並ぶ格子点(マスの交点)。たとえば $2x+3y=12$ なら $(0,4),(3,2),(6,0),\dots$ で、 $x$ を $3$ 増やすと $y$ は $2$ 減る、同じ歩はばのとびとびの並びになる。

x=x_0+\dfrac{b}{g}\,t,\qquad y=y_0-\dfrac{a}{g}\,t\qquad(t\in\mathbb{Z},\ g=\gcd(a,b))

2x+3y=12

は

1

本の直線。

x,y

がともに整数になる点

(0,4),(3,2),(6,0)

だけが整数解(格子点)。

成り立つ条件

$a,b,c$ は整数で、 $a,b$ は同時に $0$ でない。整数解をもつ条件は $g=\gcd(a,b)$ が $c$ をわり切ること( $g\nmid c$ なら解は $1$ つもない)。 $1$ つの解(特殊解)は、ユークリッドの互除法を逆にたどると必ず作れる。

証明(なぜ成り立つ?)

$1$ つの解を出発点に、ほかの解との差をとって「歩はば」を求める。特殊解の存在は互除法が保証する。

1
まず整数解 $1$ つ(特殊解) $(x_0,y_0)$ があるとする( $g\mid c$ のとき、互除法を逆にたどると必ず作れる)。このとき $ax_0+by_0=c$ 。
2
ほかの整数解 $(x,y)$ との差をとると、右辺の $c$ どうしが消えて $a(x-x_0)+b(y-y_0)=0$ 。移項すると次の形になる。
$a(x-x_0)=-b(y-y_0)$
3
両辺を $g=\gcd(a,b)$ でわると、 $\dfrac{a}{g}$ と $\dfrac{b}{g}$ は互いに素。互いに素な数の積の関係から、 $x-x_0$ は $\dfrac{b}{g}$ の倍数でなければならない。そこで $x-x_0=\dfrac{b}{g}t$ とおける。
$\dfrac{a}{g}(x-x_0)=-\dfrac{b}{g}(y-y_0)$
4
これを戻すと $y-y_0=-\dfrac{a}{g}t$ 。まとめて $x=x_0+\dfrac{b}{g}t$ 、 $y=y_0-\dfrac{a}{g}t$ 。整数 $t$ を動かすと、直線上に等間隔に並ぶすべての整数解が得られる。

逆

解が等間隔に無数に並ぶ理由はこうだ。 $2$ つの解の差をとると $a(x-x')+b(y-y')=0$ 、つまり $a(x-x')=-b(y-y')$ 。両辺を $g$ でわると $\dfrac{a}{g}$ と $\dfrac{b}{g}$ は互いに素になるので、 $x-x'$ は $\dfrac{b}{g}$ の倍数でなければならない。だから歩はばが $\dfrac{b}{g}$ (と $\dfrac{a}{g}$ )にそろう。

補足・つまずきポイント

$2x+3y=12$ では $g=\gcd(2,3)=1$ が $12$ をわり切るので解あり。歩はばは $x$ が $+3\,(=b)$ ・ $y$ が $-2\,(=a)$ 。右辺 $c$ を変えると直線が平行に動き、解も同じ歩はばでずれる。自然数の解だけを数えたいときは、 $x>0$ かつ $y>0$ になる $t$ の範囲をしぼればよい。

見て確かめる

言葉で読んだら、動くアニメと自分の手で確かめてみよう。

不定方程式は直線と格子点

使いどころ

この定理が、実際の問題でどう効くのかを見てみよう。

一次不定方程式の整数解

📐 主張

✅ 成り立つ条件

📝 証明(なぜ成り立つ?)

🔄 逆

💭 補足・つまずきポイント

🔗 関連する定理

🔭 見て確かめる

💡 使いどころ

主張

成り立つ条件

証明(なぜ成り立つ?)

逆

補足・つまずきポイント

関連する定理

見て確かめる

使いどころ