(1) 8633と6052の最大公約数を求める。 (2) 方程式 $8633x + 6052y = 1068$ の整数解をすべて求める。

1. 問題の内容

(1) 8633と6052の最大公約数を求める。

(2) 方程式 $8633x + 6052y = 1068$ の整数解をすべて求める。

2. 解き方の手順

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

$8633 = 6052 \times 1 + 2581$

$6052 = 2581 \times 2 + 890$

$2581 = 890 \times 2 + 801$

$890 = 801 \times 1 + 89$

$801 = 89 \times 9 + 0$

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

(2) 方程式 $8633x + 6052y = 1068$ の整数解を求める。

まず、$8633x + 6052y = 89$ の整数解を求める。

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

$89 = 890 - 801 \times 1$

$89 = 890 - (2581 - 890 \times 2) \times 1 = 890 \times 3 - 2581$

$89 = (6052 - 2581 \times 2) \times 3 - 2581 = 6052 \times 3 - 2581 \times 7$

$89 = 6052 \times 3 - (8633 - 6052 \times 1) \times 7 = 6052 \times 10 - 8633 \times 7$

よって、 $8633 \times (-7) + 6052 \times 10 = 89$

$8633x + 6052y = 1068$ について、

$1068 = 89 \times 12$ であるから、

$8633 \times (-7 \times 12) + 6052 \times (10 \times 12) = 89 \times 12 = 1068$

したがって、$8633 \times (-84) + 6052 \times 120 = 1068$

よって、$x = -84, y = 120$ は、$8633x + 6052y = 1068$ の解の一つである。

$8633x + 6052y = 1068$ と $8633 \times (-84) + 6052 \times 120 = 1068$ の差をとると、

$8633(x + 84) + 6052(y - 120) = 0$

$8633(x + 84) = -6052(y - 120)$

$\frac{x + 84}{6052} = \frac{-(y - 120)}{8633}$

ここで、8633と6052の最大公約数は89なので、

$\frac{x + 84}{68} = \frac{-(y - 120)}{97} = k$ (kは整数)とおける。

$x + 84 = 68k$

$x = 68k - 84$

$-(y - 120) = 97k$

$y = -97k + 120$

3. 最終的な答え

(1) 89

(2) $x = 68k - 84$, $y = -97k + 120$ (kは整数)