ディオファントス方程式計算機

この ディオファントス方程式計算機 　 数学的 解決するために設計されたツール 線形ディオファントス方程式は、次のような方程式である。 ax + by = cここで、 a, b, c 与えられる 整数, x および y は、私たちが解くべき未知数です。これらの方程式は数論の基礎であり、暗号学、コンピュータサイエンス、符号理論などの分野で実用的な応用があります。

この計算機は、 整数解 for x および y 方程式が解ける場合。ディオファントス方程式を解くプロセスを自動化し、 特定のソリューション そして表現する 一般的な解決策 整数パラメータの観点から。これらの方程式を解く方法を理解することで、ユーザーは数値とその関係性についての洞察を得ることができます。 可分性 プロパティ。

ディオファントス方程式の公式計算機

基本的なディオファントス方程式

線形ディオファントス方程式の一般的な形式は次のとおりです。

ax + by = c

どこ：

• a, b, c 整数（指定された定数）です。
• x および y は、私たちが解こうとしている未知の整数変数です。

線形ディオファントス方程式を解く

線形ディオファントス方程式 ax + by = c 整数解を持つのは、 最大公約数（gcd） of a および b 分ける cつまり、次の場合です:

gcd(a, b)はcを割り切る

解決手順:

1. aとbの最大公約数を求めよ
   ユークリッドアルゴリズム の最大公約数を計算する a および b. ユークリッドの互除法: gcd(a, b) = gcd(b, a mod b)
2. gcdがcを割り切るか確認する
   • If gcd(a, b) 分割しない c、それからあります 解決策はありません.
   • If gcd(a, b) 分ける c、次のステップに進みます。
3. 特定の解決策を見つける
   • 拡張ユークリッド アルゴリズム 整数を求める x₀ および y₀ そのような：
     a * x₀ + b * y₀ = gcd(a, b)
4. x₀とy₀の両方にc / gcd(a, b)を掛けます。 特定の解決策を見つける ax + by = c.
   • x = x₀ × (c / gcd(a, b))
   • y = y₀ × (c / gcd(a, b))
5. 一般解
   ディオファントス方程式の一般解は次のように与えられます。
   x = x₀ + (b / gcd(a, b)) * t
   y = y₀ – (a / gcd(a, b)) * t 場所 t は任意の整数です。

ディオファントス方程式の一般用語

以下の表は、ディオファントス方程式の計算で使用される重要な用語を説明しています。

契約期間	シンボル	定義
ディオファントス方程式	ax + by = c	整数 a、b、c と未知数 x および y を含む方程式。
gcd（最大公約数）	gcd(a, b)	a と b の両方を割り切れる最大の整数。
特異解	x₀, y₀	方程式を満たす x と y の特定の整数値。
拡張ユークリッド アルゴリズム	–	ディオファントス方程式の整数解を求めるために使用されるアルゴリズム。
一般的な解決策	x、y	自由パラメータ t で表現された整数解の集合。

この表は、 ディオファントス方程式計算機.

ディオファントス方程式計算機の例

例1: 簡単なディオファントス方程式を解く

方程式を解いてみましょう 3x + 5y = 7.

ステップ 1: ユークリッドのアルゴリズムを使用して 3 と 5 の gcd を見つけます。

gcd(3, 5) = gcd(5, 3) = gcd(3, 2) = gcd(2, 1) = 1

Since gcd(3, 5) = 1, 1を7で割る、この方程式には整数解が存在します。

ステップ 2: 拡張ユークリッドの互除法を使用して x₀ と y₀ を見つけます。

ユークリッドの互除法の手順から次のことがわかります。
x₀ = -1 および y₀ = 1.

ステップ3: x₀とy₀の両方にc / gcd(a, b)を掛けます。.

Since c = 7 および gcd(3, 5) = 1:

x = -1 × (7 / 1) = -7
y = 1 × (7 / 1) = 7

そう、 x = -7 および y = 7 は、1 つの特定の解決策です。

ステップ 4: 一般的な解決策。

一般解は次のようになります。

x = -7 + (5 / 1) * t = 14 + 5t
y = 7 – (3 / 1) * t = -7 – 3t

場所 t は任意の整数です。

例2: 大きな係数を持つディオファントス方程式

方程式 14x + 9y = 31:

ステップ 1: ユークリッドのアルゴリズムを使用して 14 と 9 の gcd を見つけます。

gcd(14, 9) = gcd(9, 5) = gcd(5, 4) = gcd(4, 1) = 1

Since gcd(14, 9) = 1, 1を31で割る整数解が存在します。

ステップ 2: 拡張ユークリッドの互除法を使用して x₀ と y₀ を見つけます。

ユークリッドの互除法から次の式が得られます。
x₀ = 2 および y₀ = -3.

ステップ3: c / gcd(a, b)を掛ける:

x = 2 × (31 / 1) = 62
y = -3 × (31 / 1) = -93

ステップ 4: 一般的な解決策。

一般的な解決策は次のとおりです。

x = 62 + (9 / 1) * t = 62 + 9t
y = -93 – (14 / 1) * t = -93 – 14t

場所 t は任意の整数です。

最も一般的な FAQ