ユークリッドの互除法を用いて、以下の2つの不定方程式を満たす整数 $x, y$ の組を全て求めます。 (1) $58x + 15y = 1$ (2) $86x - 25y = 2$

1. 問題の内容

ユークリッドの互除法を用いて、以下の2つの不定方程式を満たす整数 $x, y$ の組を全て求めます。

(1) $58x + 15y = 1$

(2) $86x - 25y = 2$

2. 解き方の手順

(1) $58x + 15y = 1$

まず、58と15に対してユークリッドの互除法を行います。

$58 = 15 \times 3 + 13$

$15 = 13 \times 1 + 2$

$13 = 2 \times 6 + 1$

$2 = 1 \times 2 + 0$

よって、58と15の最大公約数は1です。

次に、上の式を逆にたどって、1を表す式を作ります。

$1 = 13 - 2 \times 6$

$1 = 13 - (15 - 13 \times 1) \times 6 = 13 - 15 \times 6 + 13 \times 6 = 13 \times 7 - 15 \times 6$

$1 = (58 - 15 \times 3) \times 7 - 15 \times 6 = 58 \times 7 - 15 \times 21 - 15 \times 6 = 58 \times 7 - 15 \times 27$

したがって、$58 \times 7 + 15 \times (-27) = 1$ となります。

よって、$x = 7, y = -27$ は特殊解の一つです。

一般解を求めます。

$58x + 15y = 1$

$58 \times 7 + 15 \times (-27) = 1$

辺々引くと

$58(x-7) + 15(y+27) = 0$

$58(x-7) = -15(y+27)$

58と15は互いに素なので、$x-7$ は15の倍数、$y+27$ は58の倍数となります。

$x-7 = 15k$, $y+27 = -58k$ （$k$は整数）とおけます。

$x = 15k + 7$, $y = -58k - 27$

(2) $86x - 25y = 2$

まず、86と25に対してユークリッドの互除法を行います。

$86 = 25 \times 3 + 11$

$25 = 11 \times 2 + 3$

$11 = 3 \times 3 + 2$

$3 = 2 \times 1 + 1$

$2 = 1 \times 2 + 0$

よって、86と25の最大公約数は1です。

次に、上の式を逆にたどって、1を表す式を作ります。

$1 = 3 - 2 \times 1$

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

$1 = (25 - 11 \times 2) \times 4 - 11 = 25 \times 4 - 11 \times 8 - 11 = 25 \times 4 - 11 \times 9$

$1 = 25 \times 4 - (86 - 25 \times 3) \times 9 = 25 \times 4 - 86 \times 9 + 25 \times 27 = 25 \times 31 - 86 \times 9$

したがって、$86 \times (-9) + 25 \times 31 = 1$ となります。

両辺を2倍すると、$86 \times (-18) - 25 \times (-62) = 2$ より、$86 \times (-18) - 25 \times (-62) = 2$ となります。

よって、$x = -18, y = -62$ は特殊解の一つです。

一般解を求めます。

$86x - 25y = 2$

$86 \times (-18) - 25 \times (-62) = 2$

辺々引くと

$86(x+18) - 25(y+62) = 0$

$86(x+18) = 25(y+62)$

86と25は互いに素なので、$x+18$ は25の倍数、$y+62$ は86の倍数となります。

$x+18 = 25k$, $y+62 = 86k$ （$k$は整数）とおけます。

$x = 25k - 18$, $y = 86k - 62$

3. 最終的な答え

(1) $x = 15k + 7$, $y = -58k - 27$ (kは整数)

(2) $x = 25k - 18$, $y = 86k - 62$ (kは整数)