(1) 8633と6052の最大公約数を求める。 (2) 方程式 $8633x + 6052y = 1068$ の整数解を全て求める。

数論最大公約数ユークリッドの互除法一次不定方程式整数解
2025/5/11

1. 問題の内容

(1) 8633と6052の最大公約数を求める。
(2) 方程式 8633x+6052y=10688633x + 6052y = 1068 の整数解を全て求める。

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) 方程式 8633x+6052y=10688633x + 6052y = 1068 の整数解を求める。
まず、方程式を最大公約数で割る。
8633=89978633 = 89 * 97
6052=89686052 = 89 * 68
1068=89121068 = 89 * 12
よって、方程式は 97x+68y=1297x + 68y = 12 となる。
次に、特殊解を求める。
ユークリッドの互除法を逆からたどる。
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
したがって、 8633(7)+605210=898633 * (-7) + 6052 * 10 = 89
97x+68y=197x + 68y = 1の特殊解を探すために、8633x+6052y=898633x + 6052y = 8997x+68y=197x + 68y = 1と書き換える。(8633=97898633 = 97 * 89, 6052=68896052 = 68 * 89
上記の式を89で割ると、
97(7)+6810=197 * (-7) + 68 * 10 = 1
97x+68y=1297x + 68y = 12 の特殊解は、x=712=84x = -7 * 12 = -84, y=1012=120y = 10 * 12 = 120 である。
一般解を求める。
97x+68y=1297x + 68y = 12
97(84)+68(120)=1297(-84) + 68(120) = 12
辺々引くと、
97(x+84)+68(y120)=097(x + 84) + 68(y - 120) = 0
97(x+84)=68(y120)97(x + 84) = -68(y - 120)
97と68は互いに素なので、x+84=68kx + 84 = 68k, y120=97ky - 120 = -97k (kは整数)
x=68k84x = 68k - 84, y=97k+120y = -97k + 120

3. 最終的な答え

(1) 89
(2) x=68k84x = 68k - 84, y=97k+120y = -97k + 120 (kは整数)

「数論」の関連問題

$p = n - 1$ が 4 で割ると 3 余る素数であるとする。$F_p^* = F_p \setminus \{0\}$ とする。このとき、以下の問いに答えよ。 (1) $F_p$ 上の 0 で...

素数有限体平方数BIBデザイン直交配列
2025/6/9

## 1. 問題の内容

数列等差数列群数列奇数
2025/6/9

整数 $n$ について、$n^2$ が3の倍数ならば、$n$ は3の倍数であることを、背理法を用いて証明する。

整数倍数背理法証明
2025/6/9

整数 $n$ について、$n^2$ が3の倍数ならば、$n$ は3の倍数であることを、対偶を用いて証明する。

整数の性質倍数対偶証明
2025/6/9

$\sqrt{2}$ が無理数であることを用いて、$3\sqrt{2}$ が無理数であることを証明します。

無理数背理法平方根証明
2025/6/9

$\sqrt{2}$ が無理数であることを用いて、$3\sqrt{2}$ が無理数であることを証明する。

無理数背理法証明
2025/6/9

整数 $a$ について、「$a^2 + 2$ が 3 の倍数ならば、$a$ は 3 の倍数ではない」ことを対偶を用いて証明する問題です。

整数の性質対偶倍数証明
2025/6/9

$m^2 + n^2$ が奇数ならば、$m$ と $n$ の少なくとも一方は奇数であることを証明する問題です。

整数の性質対偶証明偶数奇数
2025/6/9

問題は、「$m^2 + n^2$ が奇数ならば、$m$, $n$ の少なくとも一方は奇数である」という命題が真であることを証明せよ、というものです。

命題証明整数偶数奇数対偶
2025/6/9

$\sqrt{\frac{28n}{5}}$ の値が整数となるような自然数 $n$ のうち、最も小さい数を求めよ。

平方根整数の性質素因数分解最小値
2025/6/9