基礎問題集
数学A 整数問題「不定方程式」の問題7 解説
数学Aの整数問題「不定方程式」にある問題7の基礎問題と解説ページです。問題と保存済み解説を公開し、ログイン後はAI質問と学習履歴も利用できます。
MathGrAIl の基礎問題集にある公開問題ページです。ログイン前でも問題と保存済み解説を確認でき、ログイン後はAI質問と学習履歴の保存を利用できます。
- 基礎問題の問題画像と保存済み解説を公開
- ログイン後にAI質問で復習
- ログイン後に学習履歴を保存
解説
方針・初手
まず $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})
$$