(1) 89と29の最大公約数をユークリッドの互除法を用いて求める。 (2) 2元1次不定方程式 $89x + 29y = 1$ の整数解を1組求める。 (3) 2元1次不定方程式 $89x + 29y = -20$ の整数解として現れる $x$ の値のうち、正のものを小さい順に $x_1, x_2, x_3, ...$ とする。このとき、自然数 $m$ に対して、$x_m$ を $m$ で表す。

1. 問題の内容

(1) 89と29の最大公約数をユークリッドの互除法を用いて求める。

(2) 2元1次不定方程式 $89x + 29y = 1$ の整数解を1組求める。

(3) 2元1次不定方程式 $89x + 29y = -20$ の整数解として現れる $x$ の値のうち、正のものを小さい順に $x_1, x_2, x_3, ...$ とする。このとき、自然数 $m$ に対して、$x_m$ を $m$ で表す。

2. 解き方の手順

(1) ユークリッドの互除法を用いて89と29の最大公約数を求める。

$89 = 29 \times 3 + 2$

$29 = 2 \times 14 + 1$

$2 = 1 \times 2 + 0$

よって、89と29の最大公約数は1である。

(2) 2元1次不定方程式 $89x + 29y = 1$ の整数解を1組求める。

ユークリッドの互除法の計算を逆にたどると

$1 = 29 - 2 \times 14$

$1 = 29 - (89 - 29 \times 3) \times 14$

$1 = 29 - 89 \times 14 + 29 \times 42$

$1 = 29 \times 43 - 89 \times 14$

$1 = 89 \times (-14) + 29 \times 43$

したがって、$(x, y) = (-14, 43)$ は $89x + 29y = 1$ の整数解の1つである。

(3) 2元1次不定方程式 $89x + 29y = -20$ の整数解を求める。

$89x + 29y = 1$ の整数解の一つが $(x, y) = (-14, 43)$ であるから、

$89(-14) + 29(43) = 1$

両辺を $-20$ 倍すると、

$89(280) + 29(-860) = -20$

よって、$89x + 29y = -20$ の整数解の一つは $(x, y) = (280, -860)$ である。

一般解を求める。

$89x + 29y = -20$

$89(280) + 29(-860) = -20$

辺々引くと、

$89(x - 280) + 29(y + 860) = 0$

$89(x - 280) = -29(y + 860)$

89と29は互いに素なので、$x - 280 = 29k$、$y + 860 = -89k$ (kは整数)とおける。

よって、

$x = 29k + 280$

$y = -89k - 860$

$x > 0$ より、$29k + 280 > 0$

$29k > -280$

$k > -\frac{280}{29} \approx -9.655$

$k$ は整数なので、$k \ge -9$

$x_1$ は $k = -9$ のとき、$x_1 = 29(-9) + 280 = -261 + 280 = 19$

$x_2$ は $k = -8$ のとき、$x_2 = 29(-8) + 280 = -232 + 280 = 48$

$x_3$ は $k = -7$ のとき、$x_3 = 29(-7) + 280 = -203 + 280 = 77$

...

$x_m$ は $k = -9 + (m - 1) = m - 10$ のとき、

$x_m = 29(m - 10) + 280 = 29m - 290 + 280 = 29m - 10$

3. 最終的な答え

(1) 1

(2) $(x, y) = (-14, 43)$

(3) $x_m = 29m - 10$