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

1. 問題の内容

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

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

2. 解き方の手順

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

8633 = 6052 * 1 + 2581

6052 = 2581 * 2 + 890

2581 = 890 * 2 + 801

890 = 801 * 1 + 89

801 = 89 * 9 + 0

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

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

まず、方程式を最大公約数で割る。

$8633 = 89 * 97$

$6052 = 89 * 68$

$1068 = 89 * 12$

よって、方程式は $97x + 68y = 12$ となる。

次に、特殊解を求める。

ユークリッドの互除法を逆からたどる。

89 = 890 - 801 * 1

801 = 2581 - 890 * 2

890 = 6052 - 2581 * 2

2581 = 8633 - 6052 * 1

89 = 890 - 801 * 1 = 890 - (2581 - 890 * 2) = 890 * 3 - 2581 = (6052 - 2581 * 2) * 3 - 2581 = 6052 * 3 - 2581 * 7 = 6052 * 3 - (8633 - 6052) * 7 = 6052 * 10 - 8633 * 7

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

$97x + 68y = 1$の特殊解を探すために、$8633x + 6052y = 89$を $97x + 68y = 1$と書き換える。（$8633 = 97 * 89$, $6052 = 68 * 89$）

上記の式を89で割ると、

$97 * (-7) + 68 * 10 = 1$

$97x + 68y = 12$ の特殊解は、$x = -7 * 12 = -84$, $y = 10 * 12 = 120$ である。

一般解を求める。

$97x + 68y = 12$

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

辺々引くと、

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

$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は整数)