コンテンツ

• ステップ
• パート1/4：方程式の書き方
• パート2/4：ユークリッドのアルゴリズムの書き方
• パート3/4：ユークリッドのアルゴリズムを使用して解決策を見つける方法
• パート4/4：無限の他のソリューションを見つける

線形ディオファントス方程式を解くには、整数である変数「x」と「y」の値を見つける必要があります。整数解は通常よりも複雑で、特定のアクションのセットが必要です。まず、係数の最大公約数（GCD）を計算してから、解を見つける必要があります。一次方程式の整数解を1つ見つけたら、単純なパターンを使用して、他の無数の解を見つけることができます。

ステップ

パート1/4：方程式の書き方

1. 1 方程式を標準形式で書き留めます。 一次方程式は、変数の指数が1を超えない方程式です。このような一次方程式を解くには、最初に標準形式で記述します。一次方程式の標準形式は次のようになります。 ${ displaystyle Ax + By = C}$、 どこ ${ displaystyle A、B}$ と ${ displaystyle C}$ -整数。
   • 方程式が別の形式で与えられている場合は、基本的な代数演算を使用して標準形式にします。たとえば、次の方程式が与えられます ${ displaystyle 23x + 4y-7x = -3y + 15}$..。同様の用語を与え、次のような方程式を書きます。 ${ displaystyle 16x + 7y = 15}$.
2. 2 方程式を単純化します（可能な場合）。 方程式を標準形式で書くときは、係数を見てください ${ displaystyle A、B}$ と ${ displaystyle C}$..。これらのオッズにGCDがある場合は、3つのオッズすべてをGCDで割ります。このような単純化された方程式の解は、元の方程式の解にもなります。
   • たとえば、3つの係数がすべて偶数の場合は、少なくとも2で割ります。次に例を示します。
     • ${ displaystyle 42x + 36y = 48}$ （すべてのメンバーは2で割り切れます）
     • ${ displaystyle 21x + 18y = 24}$ （現在、すべてのメンバーは3で割り切れます）
     • ${ displaystyle 7x + 6y = 8}$ （この方程式はもはや単純化できません）
3. 3 方程式が解けるかどうかを確認します。 場合によっては、方程式に解がないことをすぐに述べることができます。係数「C」が係数「A」と「B」のGCDで割り切れない場合、方程式には解がありません。
   • たとえば、両方の係数が ${ displaystyle A}$ と ${ displaystyle B}$ 偶数の場合、係数 ${ displaystyle C}$ 均等でなければなりません。しかし、 ${ displaystyle C}$ 奇妙なことに、解決策はありません。
     • 方程式 ${ displaystyle 2x + 4y = 21}$ 整数解はありません。
     • 方程式 ${ displaystyle 5x + 10y = 17}$ 方程式の左辺は5で割り切れ、右辺は割り切れないため、整数の解はありません。

パート2/4：ユークリッドのアルゴリズムの書き方

1. 1 ユークリッドのアルゴリズムを理解します。 これは、前の剰余が次の除数として使用される一連の繰り返し除算です。数値を完全に除算する最後の除数は、2つの数値の最大公約数（GCD）です。
   • たとえば、ユークリッドのアルゴリズムを使用して、番号272と36のGCDを見つけましょう。
     • ${ displaystyle 272 = 7 * 36 + 20}$ -大きい数（272）を小さい数（36）で割り、余り（20）に注意してください。
     • ${ displaystyle 36 = 1 * 20 + 16}$ -前の除数（36）を前の剰余（20）で割ります。新しい残基（16）に注意してください。
     • ${ displaystyle 20 = 1 * 16 + 4}$ -前の除数（20）を前の剰余（16）で割ります。新しい残基（4）に注意してください。
     • ${ displaystyle 16 = 4 * 4 + 0}$ -前の除数（16）を前の剰余（4）で割ります。余りは0なので、4は元の2つの数値272と36のGCDであると言えます。
2. 2 ユークリッドのアルゴリズムを係数「A」と「B」に適用します。 一次方程式を標準形式で書くときは、係数「A」と「B」を決定し、ユークリッドのアルゴリズムをそれらに適用してGCDを見つけます。たとえば、線形方程式が与えられた場合 ${ displaystyle 87x-64y = 3}$.
   • 係数A = 87およびB = 64に対するユークリッドのアルゴリズムは次のとおりです。
     • ${ displaystyle 87 = 1 * 64 + 23}$
     • ${ displaystyle 64 = 2 * 23 + 18}$
     • ${ displaystyle 23 = 1 * 18 + 5}$
     • ${ displaystyle 18 = 3 * 5 + 3}$
     • ${ displaystyle 5 = 1 * 3 + 2}$
     • ${ displaystyle 3 = 1 * 2 + 1}$
     • ${ displaystyle 2 = 2 * 1 + 0}$
3. 3 最大公約数（GCD）を見つけます。 最後の除数が1だったので、GCD 87と64は1です。したがって、87と64は相互に相対的な素数です。
4. 4 結果を分析します。 gcd係数を見つけたら ${ displaystyle A}$ と ${ displaystyle B}$、係数と比較してください ${ displaystyle C}$ 元の方程式。もしも ${ displaystyle C}$ gcdで割り切れる ${ displaystyle A}$ と ${ displaystyle B}$、方程式には整数解があります。それ以外の場合、方程式には解がありません。
   • たとえば、方程式 ${ displaystyle 87x-64y = 3}$ 3は1で割り切れるので解決できます（gcd = 1）。
   • たとえば、GCD = 5であるとします。 3は5で割り切れないため、この方程式には整数解がありません。
   • 以下に示すように、方程式に1つの整数解がある場合、他の整数解も無限にあります。

パート3/4：ユークリッドのアルゴリズムを使用して解決策を見つける方法

1. 1 GCDを計算するためのステップに番号を付けます。 一次方程式の解を見つけるには、置換および単純化プロセスの基礎としてユークリッドアルゴリズムを使用する必要があります。
   • GCDを計算するためのステップに番号を付けることから始めます。計算プロセスは次のようになります。
     • ${ displaystyle { text {ステップ1}}：87 =（1 * 64）+23}$
     • ${ displaystyle { text {ステップ2}}：64 =（2 * 23）+18}$
     • ${ displaystyle { text {ステップ3}}：23 =（1 * 18）+5}$
     • ${ displaystyle { text {ステップ4}}：18 =（3 * 5）+3}$
     • ${ displaystyle { text {ステップ5}}：5 =（1 * 3）+2}$
     • ${ displaystyle { text {ステップ6}}：3 =（1 * 2）+1}$
     • ${ displaystyle { text {ステップ7}}：2 =（2 * 1）+0}$
2. 2 残りがある最後のステップに注意してください。 このステップの方程式を書き直して、残りを分離します。
   • この例では、剰余のある最後のステップはステップ6です。剰余は1です。ステップ6の方程式を次のように書き直します。
     • ${ displaystyle 1 = 3-（1 * 2）}$
3. 3 前のステップの残りを分離します。 このプロセスは、段階的な「上へ」です。前のステップで方程式の残りを分離するたびに。
   • 手順5で方程式の残りの部分を分離します。
     • ${ displaystyle 2 = 5-（1 * 3）}$ また ${ displaystyle 2 = 5-3}$
4. 4 代用して簡素化します。 手順6の式には数値2が含まれており、手順5の式では数値2が分離されていることに注意してください。したがって、ステップ6の式の「2」の代わりに、ステップ5の式に置き換えます。
   • ${ displaystyle 1 = 3-2}$ （ステップ6の式）
   • ${ displaystyle 1 = 3-（5-3）}$ （2の代わりに、式が置換されました）
   • ${ displaystyle 1 = 3-5 + 3}$ （白抜きの括弧）
   • ${ displaystyle 1 = 2（3）-5}$ （簡略化）
5. 5 置換と簡略化のプロセスを繰り返します。 説明したプロセスを繰り返し、ユークリッドアルゴリズムを逆の順序で進めます。前のステップの方程式を書き直して、最後に取得した方程式にプラグインするたびに。
   • 私たちが見た最後のステップはステップ5でした。したがって、ステップ4に進み、そのステップの方程式の残りを分離します。
     • ${ displaystyle 3 = 18-（3 * 5）}$
   • 最後の式の「3」をこの式に置き換えます。
     • ${ displaystyle 1 = 2（18-3 * 5）-5}$
     • ${ displaystyle 1 = 2（18）-6（5）-5}$
     • ${ displaystyle 1 = 2（18）-7（5）}$
6. 6 置換と簡略化のプロセスを続行します。 このプロセスは、ユークリッドアルゴリズムの最初のステップに到達するまで繰り返されます。このプロセスの目標は、解くべき元の方程式の係数87と64を使用して方程式を書くことです。この例では：
   • ${ displaystyle 1 = 2（18）-7（5）}$
   • ${ displaystyle 1 = 2（18）-7（23-18）}$ （ステップ3の式を置き換えました）
     • ${ displaystyle 1 = 2（18）-7（23）+7（18）}$
     • ${ displaystyle 1 = 9（18）-7（23）}$
   • ${ displaystyle 1 = 9（64-2 * 23）-7（23）}$ （ステップ2の式を置き換えました）
     • ${ displaystyle 1 = 9（64）-18（23）-7（23）}$
     • ${ displaystyle 1 = 9（64）-25（23）}$
   • ${ displaystyle 1 = 9（64）-25（87-64）}$ （ステップ1の式を置き換えました）
     • ${ displaystyle 1 = 9（64）-25（87）+25（64）}$
     • ${ displaystyle 1 = 34（64）-25（87）}$
7. 7 結果の方程式を元の係数に従って書き直します。 ユークリッドアルゴリズムの最初のステップに戻ると、結果の方程式に元の方程式の2つの係数が含まれていることがわかります。項の順序が元の方程式の係数と一致するように方程式を書き直します。
   • この例では、元の方程式 ${ displaystyle 87x-64y = 3}$..。したがって、係数が一直線になるように、結果の方程式を書き直してください。係数「64」に特に注意してください。元の方程式では、この係数は負であり、ユークリッドアルゴリズムでは正です。したがって、係数34は負にする必要があります。最終的な方程式は次のように記述されます。
     • ${ displaystyle 87（-25）-64（-34）= 1}$
8. 8 適切な乗数を適用して解決策を見つけます。 この例では、GCD = 1であるため、最終的な方程式は1ですが、元の方程式（87x-64y）は3です。したがって、解を得るには、最終的な方程式のすべての項に3を掛ける必要があります。
   • ${ displaystyle 87（-25 * 3）-64（-34 * 3）= 1 * 3}$
   • ${ displaystyle 87（-75）-64（-102）= 3}$
9. 9 方程式の整数解を書き留めます。 元の方程式の係数を掛けた数値は、その方程式の解です。
   • この例では、ソリューションを座標のペアとして記述します。 ${ displaystyle（x、y）=（-75、-102）}$.

パート4/4：無限の他のソリューションを見つける

1. 1 解決策は無数にあることを理解してください。 一次方程式に1つの整数解がある場合、無限に多くの整数解が必要です。これが（代数形式の）簡単な証明です：
   • ${ displaystyle Ax + By = C}$
   • ${ displaystyle A（x + B）+ B（y-A）= C}$ （「x」に「B」を加算し、「y」から「A」を減算すると、元の式の値は変更されません）
2. 2 元のx値とy値を記録します。 次の（無限の）解を計算するためのテンプレートは、すでに見つけた唯一の解から始まります。
   • この例では、解は座標のペアです ${ displaystyle（x、y）=（-75、-102）}$.
3. 3 「x」値に「B」係数を追加します。 これを実行して、新しいx値を見つけます。
   • この例では、x = -75、およびB = -64：
     • ${ displaystyle x = -75 +（-64）= --139}$
   • したがって、新しい値 "x"：x = -139。
4. 4 「y」値から「A」係数を引きます。 元の方程式の値が変わらないように、「x」に1つの数値を加算するときは、「y」から別の数値を減算する必要があります。
   • この例では、y = -102、およびA = 87です。
     • ${ displaystyle y = -102-87 = -189}$
   • したがって、「y」の新しい値：y = -189。
   • 新しい座標のペアは次のように記述されます。 ${ displaystyle（x、y）=（-139、-189）}$.
5. 5 解決策を確認してください。 新しい座標ペアが元の方程式の解であることを確認するには、値を方程式にプラグインします。
   • ${ displaystyle 87x-64y = 3}$
   • ${ displaystyle 87（-139）-64（-189）= 3}$
   • ${ displaystyle 3 = 3}$
   • 平等が満たされているので、決定は正しいです。
6. 6 多くの解決策を見つけるために式を書き留めてください。 「x」値は、元の解に「B」係数の倍数を加えたものに等しくなります。これは、次の式で記述できます。
   • x（k）= x + k（B）、ここで「x（k）」は「x」値のセットであり、「x」は見つけた「x」の元の（最初の）値です。
     • この例では：
     • ${ displaystyle x（k）= --75-64k}$
   • y（k）= y-k（A）、ここでy（k）はy値のセットであり、yは最初に見つけた（最初の）y値です。
     • この例では：
     • ${ displaystyle y（k）= --102-87k}$