問題は3つの部分から構成されています。 (1) ユークリッドの互除法を用いて37と11の最大公約数と最小公倍数を求めます。 (2) (1)の結果を利用して、方程式 $37x + 11y = 3$ を満たす整数 $x, y$ の組を1つ求めます。 (3) (2)で求めた結果を利用して、方程式 $37x + 11y = 3$ を満たす全ての整数 $x, y$ の組を求めます。

1. 問題の内容

問題は3つの部分から構成されています。

(1) ユークリッドの互除法を用いて37と11の最大公約数と最小公倍数を求めます。

(2) (1)の結果を利用して、方程式 $37x + 11y = 3$ を満たす整数 $x, y$ の組を1つ求めます。

(3) (2)で求めた結果を利用して、方程式 $37x + 11y = 3$ を満たす全ての整数 $x, y$ の組を求めます。

2. 解き方の手順

(1) ユークリッドの互除法を用いて37と11の最大公約数と最小公倍数を求めます。

$37 = 11 \times 3 + 4$

$11 = 4 \times 2 + 3$

$4 = 3 \times 1 + 1$

$3 = 1 \times 3 + 0$

したがって、37と11の最大公約数は1です。

最小公倍数は $37 \times 11 / 1 = 407$ です。

(2) (1)を利用して、方程式 $37x + 11y = 3$ を満たす整数 $x, y$ の組を1つ求めます。

ユークリッドの互除法の計算を逆にたどります。

$1 = 4 - 3 \times 1$

$1 = 4 - (11 - 4 \times 2) \times 1 = 4 - 11 + 4 \times 2 = 4 \times 3 - 11$

$1 = (37 - 11 \times 3) \times 3 - 11 = 37 \times 3 - 11 \times 9 - 11 = 37 \times 3 - 11 \times 10$

よって、$37 \times 3 + 11 \times (-10) = 1$

両辺を3倍すると、

$37 \times 9 + 11 \times (-30) = 3$

したがって、$x = 9, y = -30$ は $37x + 11y = 3$ の解の1つです。

(3) (2)の結果を利用して、方程式 $37x + 11y = 3$ を満たす全ての整数 $x, y$ の組を求めます。

$37x + 11y = 3$

$37 \times 9 + 11 \times (-30) = 3$

辺々引くと、

$37(x - 9) + 11(y + 30) = 0$

$37(x - 9) = -11(y + 30)$

37と11は互いに素なので、$x - 9 = 11k$, $y + 30 = -37k$ （$k$ は整数）と表せます。

したがって、$x = 11k + 9$, $y = -37k - 30$

3. 最終的な答え

(1) 最大公約数: 1, 最小公倍数: 407

(2) $x = 9, y = -30$

(3) $x = 11k + 9, y = -37k - 30$ (kは整数)