(1) 1183 と 2821 の最大公約数をユークリッドの互除法を用いて求めよ。 (2) $8x + 11y = 1$ を満たす整数 $x, y$ の組を1つ求めよ。

1. 問題の内容

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

(2) $8x + 11y = 1$ を満たす整数 $x, y$ の組を1つ求めよ。

2. 解き方の手順

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

$2821 = 1183 \times 2 + 455$

$1183 = 455 \times 2 + 273$

$455 = 273 \times 1 + 182$

$273 = 182 \times 1 + 91$

$182 = 91 \times 2 + 0$

したがって、1183 と 2821 の最大公約数は 91 である。

(2) 拡張ユークリッドの互除法を用いて $8x + 11y = 1$ を満たす整数解を求める。

まず、ユークリッドの互除法で 8 と 11 の最大公約数を求める。

$11 = 8 \times 1 + 3$

$8 = 3 \times 2 + 2$

$3 = 2 \times 1 + 1$

$2 = 1 \times 2 + 0$

よって、8 と 11 の最大公約数は 1 である。

次に、これらの式を逆順にたどる。

$1 = 3 - 2 \times 1$

$2 = 8 - 3 \times 2$ を代入して、

$1 = 3 - (8 - 3 \times 2) \times 1 = 3 - 8 + 3 \times 2 = 3 \times 3 - 8$

$3 = 11 - 8 \times 1$ を代入して、

$1 = (11 - 8 \times 1) \times 3 - 8 = 11 \times 3 - 8 \times 3 - 8 = 11 \times 3 - 8 \times 4$

よって、$8 \times (-4) + 11 \times 3 = 1$ となる。

したがって、$x = -4, y = 3$ が $8x + 11y = 1$ を満たす整数の組の一つである。

3. 最終的な答え

(1) 91

(2) $x = -4, y = 3$