(1) 8633と6052の最大公約数を求める。 (2) 方程式 $8633x + 6052y = 1068$ の整数解を全て求める。
2025/5/11
1. 問題の内容
(1) 8633と6052の最大公約数を求める。
(2) 方程式 の整数解を全て求める。
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) 方程式 の整数解を求める。
まず、方程式を最大公約数で割る。
よって、方程式は となる。
次に、特殊解を求める。
ユークリッドの互除法を逆からたどる。
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
したがって、
の特殊解を探すために、を と書き換える。(, )
上記の式を89で割ると、
の特殊解は、, である。
一般解を求める。
辺々引くと、
97と68は互いに素なので、, (kは整数)
,
3. 最終的な答え
(1) 89
(2) , (kは整数)