(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は整数)

「数論」の関連問題

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

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

整数 $n$ について、命題「$n^2$ が奇数ならば、$n$ は奇数である」を証明します。

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

$n$ は整数であるとき、「$n^2$ が奇数ならば、$n$ は奇数である」という命題を証明する。

命題証明対偶整数の性質偶数奇数
2025/6/8

問題は、群数列に関する以下の2つの問いです。 (7) 先頭から数えて100番目に現れる分数は何か。 (8) 先頭から100番目までの総和を求めよ。 与えられた数列は、 $\frac{1}{1}, \f...

数列群数列級数分数
2025/6/8

(1) $M$ と $N$ はともに2桁の自然数で、差が36、最大公約数が9である。このような $M, N$ の組をすべて求めよ。 (2) $M$ と $N$ の和が21、最小公倍数が36である。この...

最大公約数最小公倍数約数自然数
2025/6/8

4桁の自然数 $n$ の千の位、百の位、十の位、一の位の数字をそれぞれ $a, b, c, d$ とする。 (1) $a > b > c > d$ を満たす $n$ は何個あるか。 (2) $a < ...

組み合わせ自然数桁数
2025/6/8

自然数 $m, n$ に関する次の2つの命題の真偽を判定し、偽である場合は反例を挙げてください。 (1) 和 $m+n$ は奇数 $\Rightarrow$ 積 $mn$ は偶数 (2) 和 $m+n...

命題真偽判定整数の性質偶数奇数
2025/6/8

素数が無限に存在することを証明する問題です。

素数証明背理法整数の性質
2025/6/8

自然数の列を、第n群に$2^{n-1}$個の数が入るように群に分ける。 (1) 第n群の最初の数をnの式で表す。 (2) 第n群に入るすべての数の和Sを求める。

数列等比数列等差数列群数列和の計算
2025/6/7

整数 $x$ について、命題「$x$ が 6 の倍数ならば、$x$ は 2 の倍数である」が真であるか偽であるかを判定する。

倍数整数の性質命題真偽
2025/6/7