ユークリッドの互除法を用いて、以下の2つの不定方程式を満たす整数解をそれぞれ1つ求める。 (1) $53x + 37y = 1$ (2) $19x - 43y = 1$

1. 問題の内容

ユークリッドの互除法を用いて、以下の2つの不定方程式を満たす整数解をそれぞれ1つ求める。

(1) $53x + 37y = 1$

(2) $19x - 43y = 1$

2. 解き方の手順

(1) $53x + 37y = 1$ の場合

まず、53と37に対してユークリッドの互除法を行う。

$53 = 37 \cdot 1 + 16$

$37 = 16 \cdot 2 + 5$

$16 = 5 \cdot 3 + 1$

$5 = 1 \cdot 5 + 0$

次に、余りを逆順にたどって、1を表す。

$1 = 16 - 5 \cdot 3$

$1 = 16 - (37 - 16 \cdot 2) \cdot 3 = 16 - 37 \cdot 3 + 16 \cdot 6 = 16 \cdot 7 - 37 \cdot 3$

$1 = (53 - 37 \cdot 1) \cdot 7 - 37 \cdot 3 = 53 \cdot 7 - 37 \cdot 7 - 37 \cdot 3 = 53 \cdot 7 - 37 \cdot 10$

したがって、$53 \cdot 7 + 37 \cdot (-10) = 1$ となる。

よって、$x = 7$, $y = -10$ が解の一つである。

(2) $19x - 43y = 1$ の場合

19と43に対してユークリッドの互除法を行う。

$43 = 19 \cdot 2 + 5$

$19 = 5 \cdot 3 + 4$

$5 = 4 \cdot 1 + 1$

$4 = 1 \cdot 4 + 0$

次に、余りを逆順にたどって、1を表す。

$1 = 5 - 4 \cdot 1$

$1 = 5 - (19 - 5 \cdot 3) \cdot 1 = 5 - 19 + 5 \cdot 3 = 5 \cdot 4 - 19$

$1 = (43 - 19 \cdot 2) \cdot 4 - 19 = 43 \cdot 4 - 19 \cdot 8 - 19 = 43 \cdot 4 - 19 \cdot 9$

したがって、$19 \cdot (-9) + 43 \cdot 4 = 1$となる。

求める方程式は $19x - 43y = 1$であるから、$19x + (-43)y = 1$ と変形できる。

よって、$x = -9$, $y = -4$が $19x+ (-43)y=1$の解である。

したがって、$x = -9$, $y = -4$とすると、$19(-9)-43(-4)=1$となり、$19(-9) - 43(-4) = -171 + 172 = 1$を満たす。

3. 最終的な答え

(1) $x = 7$, $y = -10$

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