数学A 不定方程式 問題 7 解説

方針・初手

まず $629$ と $481$ の最大公約数 $d$ をユークリッドの互除法で求める。その後、同じ互除法を逆にたどって $d$ を $629$ と $481$ の整数係数の一次結合で表す。

1組の整数解が得られれば、一次不定方程式の一般解としてすべての整数解を表せる。

解法1

ユークリッドの互除法を用いる。

$$ 629=481+148 $$

$$ 481=3\cdot 148+37 $$

$$ 148=4\cdot 37 $$

よって、

$$ d=\gcd(629,481)=37 $$

である。したがって、求める方程式は

$$ 629x+481y=37 $$

である。

両辺を $37$ で割ると、

$$ 17x+13y=1 $$

となる。

次に、互除法を逆にたどる。

$$ 37=481-3\cdot 148 $$

また、

$$ 148=629-481 $$

であるから、

$$ \begin{aligned} 37 &=481-3(629-481)\\ &=4\cdot 481-3\cdot 629 \end{aligned} $$

したがって、

$$ 629(-3)+481(4)=37 $$

より、1つの整数解は

$$ (x,y)=(-3,4) $$

である。

ここから一般解を求める。方程式

$$ 17x+13y=1 $$

の1つの解が $x=-3,\ y=4$ であるから、任意の整数 $t$ を用いて

$$ x=-3+13t,\qquad y=4-17t $$

と表される。

実際、

$$ 17(-3+13t)+13(4-17t) =-51+221t+52-221t =1 $$

となるので、これは確かに解である。

また、任意の解 $(x,y)$ と $(-3,4)$ の差を考えると、

$$ 17(x+3)+13(y-4)=0 $$

すなわち

$$ 17(x+3)=-13(y-4) $$

である。$17$ と $13$ は互いに素なので、$x+3$ は $13$ の倍数である。よって整数 $t$ を用いて

$$ x+3=13t $$

と書ける。このとき

$$ 17\cdot 13t=-13(y-4) $$

より、

$$ y-4=-17t $$

である。

したがって、すべての整数解は

$$ (x,y)=(-3+13t,\ 4-17t)\qquad (t\in\mathbb{Z}) $$

である。

解説

この問題では、まず最大公約数 $d$ を求めるだけでなく、その $d$ を $629$ と $481$ の整数係数の一次結合として表す必要がある。したがって、ユークリッドの互除法を逆にたどる処理が中心である。

$629x+481y=d$ を直接扱ってもよいが、$d=37$ と分かれば、両辺を $37$ で割って $17x+13y=1$ とする方が見通しがよい。

1つの整数解から一般解に移るときは、係数 $17,13$ が互いに素であることを使う。ここを省くと「すべての解」であることの説明が不足する。

答え

$$ d=37 $$

$$ (x,y)=(-3+13t,\ 4-17t)\qquad (t\in\mathbb{Z}) $$