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

1. 問題の内容

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

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

2. 解き方の手順

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

$8633 = 1 \times 6052 + 2581$

$6052 = 2 \times 2581 + 890$

$2581 = 2 \times 890 + 801$

$890 = 1 \times 801 + 89$

$801 = 9 \times 89 + 0$

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

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

まず、$8633x + 6052y = 89$ の整数解をユークリッドの互除法を逆にたどって求める。

$89 = 890 - 1 \times 801$

$801 = 2581 - 2 \times 890$

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

$890 = 6052 - 2 \times 2581$

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

$2581 = 8633 - 1 \times 6052$

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

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

次に、$8633x + 6052y = 1068$ の整数解を求める。

$1068 = 89 \times 12$ であるから、$8633x + 6052y = 89 \times 12$

$8633 \times (-7) + 6052 \times 10 = 89$ の両辺を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$ の一つの解である。

$8633(-84) + 6052(120) = 1068$

$8633x + 6052y = 1068$

辺々引くと

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

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

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

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

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

$\frac{8633}{89} = 97$

$\frac{6052}{89} = 68$

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

$97(x+84) = -68(y-120)$

97と68は互いに素なので、$x+84 = 68k$, $y-120 = -97k$ (kは整数) と書ける。

したがって、$x = 68k - 84$, $y = -97k + 120$

3. 最終的な答え

(1) 89

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