(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$ の整数解を求めます。

まず、方程式を最大公約数89で割ります。

$\frac{8633}{89}x + \frac{6052}{89}y = \frac{1068}{89}$

$97x + 68y = 12$

次に、$97x + 68y = 1$ の整数解を求めます。ユークリッドの互除法を利用します。

$97 = 1 \times 68 + 29$

$68 = 2 \times 29 + 10$

$29 = 2 \times 10 + 9$

$10 = 1 \times 9 + 1$

$1 = 10 - 1 \times 9$

$1 = 10 - 1 \times (29 - 2 \times 10) = 3 \times 10 - 1 \times 29$

$1 = 3 \times (68 - 2 \times 29) - 1 \times 29 = 3 \times 68 - 7 \times 29$

$1 = 3 \times 68 - 7 \times (97 - 1 \times 68) = 10 \times 68 - 7 \times 97$

したがって、$97(-7) + 68(10) = 1$ です。

$97x + 68y = 12$ の特殊解は、$x = -7 \times 12 = -84$, $y = 10 \times 12 = 120$ です。

$97(-84) + 68(120) = 12$

$97x + 68y = 12$

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

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

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

$x = 68k - 84$, $y = -97k + 120$

3. 最終的な答え

(1) 最大公約数: 89

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