SENSEI AI
About App

与えられた一次不定方程式 $5x + 13y = 1$ の整数解を求める問題です。

数論一次不定方程式整数解ユークリッドの互除法拡張ユークリッドの互除法
2025/3/8

1. 問題の内容

与えられた一次不定方程式 5x+13y=15x + 13y = 1 の整数解を求める問題です。

2. 解き方の手順

まず、ユークリッドの互除法を用いて、5と13の最大公約数を求めます。
13 = 5 * 2 + 3
5 = 3 * 1 + 2
3 = 2 * 1 + 1
2 = 1 * 2 + 0
最大公約数は1であることがわかります。
次に、拡張ユークリッドの互除法を用いて、5x+13y=15x + 13y = 1 を満たす整数解 x,yx, y を一つ求めます。
1 = 3 - 2 * 1
= 3 - (5 - 3 * 1) * 1
= 3 - 5 + 3
= 2 * 3 - 5
= 2 * (13 - 5 * 2) - 5
= 2 * 13 - 4 * 5 - 5
= 2 * 13 - 5 * 5
よって、5(−5)+13(2)=15(-5) + 13(2) = 1 となります。
したがって、x0=−5x_0 = -5, y0=2y_0 = 2 は 5x+13y=15x + 13y = 1 の一つの解です。
次に、一般解を求めます。
5x+13y=15x + 13y = 1
5(−5)+13(2)=15(-5) + 13(2) = 1
辺々引くと、
5(x+5)+13(y−2)=05(x + 5) + 13(y - 2) = 0
5(x+5)=−13(y−2)5(x + 5) = -13(y - 2)
5と13は互いに素なので、x+5x + 5 は13の倍数、y−2y - 2 は5の倍数となります。
したがって、x+5=13kx + 5 = 13k, y−2=−5ky - 2 = -5k (kは整数) と書けます。
x=13k−5x = 13k - 5
y=−5k+2y = -5k + 2

3. 最終的な答え

x=13k−5x = 13k - 5
y=−5k+2y = -5k + 2 (kは整数)

「数論」の関連問題

自然数 $a, b, c$ が $a^2 + b^2 = c^2$ を満たすとき、$a, b, c$ のうち少なくとも1つは偶数であることを証明します。

ピタゴラス数整数の性質背理法偶数奇数
2025/4/3

自然数 $n$ について、「$n^2$ が 3 の倍数ならば、$n$ は 3 の倍数である」という命題を、対偶を用いて証明する。

整数の性質対偶倍数証明
2025/4/3

次の数を素因数分解せよ。 (1) 48 (2) 60 (3) 91

素因数分解素数整数の性質
2025/4/3

自然数Nを3進法で表すと4桁の数 $1ab1_{(3)}$ となり、5進法で表すと3桁の数 $a0b_{(5)}$ となる。 このとき、$a$, $b$, $N$ を求める。

進法整数方程式解法
2025/4/3

次の2つの不定方程式の整数解をすべて求める問題です。 (1) $3x - 5y = 1$ (2) $75x + 64y = 1$

不定方程式整数解ユークリッドの互除法
2025/4/2

$n > 1$ のとき、$n^7 - n$ が42で割り切れることを示す問題です。

整数の性質合同式因数分解フェルマーの小定理
2025/3/31

$n > 1$ のとき、$n^7 - n$ が $42$ で割り切れることを示す問題です。

整数の性質割り算因数分解フェルマーの小定理
2025/3/31

$n$ を自然数とするとき、「$n$ が 3 の倍数ならば $n^2$ も 3 の倍数となる」という命題の逆と裏の真偽を判定し、正しい組み合わせを選ぶ問題です。

命題真偽倍数整数の性質対偶
2025/3/31

自然数 $n$ に対して、「$n$ が 3 の倍数ならば、$n^2$ も 3 の倍数となる」という命題がある。この命題の逆と裏の真偽を判定し、正しい組み合わせを選択する。

命題真偽倍数対偶逆裏
2025/3/31

$n$ を自然数とし、$1$ から $n$ までの異なる $n$ 個の自然数からなる集合を $N$ とする。$N$ の2つの部分集合 $P_1, P_2$ は $P_1 \cap P_2 = \emp...

集合部分集合和整数の性質合同式
2025/3/30