線形ディオファントス方程式38x+13y=1の整数解を求める場合、拡張ユークリッドの互除法を使うと効率的に解を見つけることができます。本記事では、その手順と考え方を解説します。
ディオファントス方程式とは
ディオファントス方程式とは、整数係数の一次方程式で整数解を求める方程式です。今回の方程式は38x+13y=1の形で、xとyが整数である解を探します。
この方程式は互いに素な係数（38と13）の場合、必ず整数解が存在します。
拡張ユークリッドの互除法を使う
まず38と13の最大公約数を求めます。
38 = 13×2 + 12
13 = 12×1 + 1
12 = 1×12 + 0
したがって最大公約数は1であり、整数解が存在することが確認できます。
逆に解を求める
次に逆順に計算して1を38と13の組み合わせで表します。
1 = 13 – 12×1
12 = 38 – 13×2
1 = 13 – (38 – 13×2) = 3×13 – 38
よって整数解の一つはx=-1, y=3となります。
一般解の表現
線形ディオファントス方程式の解は一般解として表すことができます。今回の場合、整数tに対して
x = -1 + 13t
y = 3 – 38t
の形で無限に解が存在します。
まとめ
38x+13y=1の整数解の一つはx=-1, y=3です。拡張ユークリッドの互除法を使うことで、効率よく整数解を求めることができます。また、一般解としてx=-1+13t, y=3-38t(tは整数)と表せます。
コメント