導入
方程式 ax + by = c (係数 a、b、c は 3 つの相対整数、未知数 x と y は相対整数) は、解くのが最も簡単なディオファントス方程式の 1 つです。その解決策は、 Euclidアルゴリズム、 Bachet-Bézout の定理、およびガウスの定理に基づいています。 c が a と b の GCD に等しい場合、それはベズー恒等式と呼ばれることがあります。
相対整数のセットでは、そのような方程式には解がないか、無限に解が存在します。係数と未知数が自然数の場合、方程式の解の数は有限になります。パオリの定理により数値は 1 以内になります。
相対整数のセット内の解を見つける
方程式ax + by = 1 ここで、a と b は互いに素です
バシェ・ベズーの定理は、この方程式は常に少なくとも 1 つの解を許容すると述べています。
解決の最初のステップは、特定の解を見つけることで構成されます。つまり、ax 0 + by 0 = 1 を検証する相対整数のペア (x 0 , y 0 ) を見つけます。
- 拡張 Euclid アルゴリズムを使用すると、そのアルゴリズムをデモンストレーションできます。
- もう 1 つの方法は、a/b の連分数展開を使用することです。最後から 2 番目の換算により問題の解決策が得られます。 $$ {\frac{h_{n-1}}{k_{n-1}}} $$最後から 2 番目は次のように減算されます$$ {\frac ab} $$するとk n − 1 a − h n − 1 b = (− 1) n + 1 となります。
- しかし、b が大きすぎない場合は、b を法として計算し、1 と |b| の間の整数 x 0を探す単純なスキャンによって解を探すこともできます。 – 1、チェック中$$ {ax \equiv 1 \pmod b} $$、整数 y 0は次と等しいものとして計算されます。$$ {\frac{1-ax_0}{b}} $$。
解のセット—特定の解 (x 0 , y 0 ) が既知である場合、解のセットはペア (x 0 +bk, y 0 – ak) で構成されます。ここで、k は任意の相対整数です。
実際、このようなカップルが問題の解決策であることを検証するのは簡単です。
- $$ {\forall k \in \mathbb Z ,\, a(x_0+bk)+b(y_0-ak)=ax_0+by_0=1} $$
これからは、これらのカップルだけが解決策であることを証明することが重要です。したがって、カップル (x, y) が方程式の解であると仮定しましょう。したがって、私たちは
- $$ {(1):\qquad ax+by=1=ax_0+by_0} $$
用語を別の方法で再グループ化すると、次のようになります。
- $$ {(2):\qquad a(x-x_0)=-b(y-y_0)} $$
したがって、整数 b は積 a(x – x 0 ) を除算します。 a と b は互いに素であるため、ガウスの補題により、 b は x – x 0を除算すると言えます。したがって、x – x 0 = kb となるような相対整数 k が存在します。あるいはもう一度
- $$ {(3):\qquad x=x_0+kb} $$
(2) で x – x 0 をkb に置き換えると、次のようになります。
- $$ {(4) \qquad akb=-b(y-y_0)} $$
次に -b で簡略化します
- $$ {(5) \qquad y-y_0=-ak} $$
あるいはもう一度
- $$ {(6) \qquad y=y_0-ak} $$
したがって、(x,y) が (1) の解である場合、(x,y) = (x 0 +bk, y 0 – ak) となる相対整数 k が存在します。
方程式 ax + by = c ここで、a と b は互いに素です
特定の解は、方程式 ax + by = 1 の特定の解に c を掛けることで見つけることができます。実際、(x 0 , y 0 ) が ax 0 + by 0 = 1 を満たす場合、ax 0 c + by 0 c = c、対 (x 0 c, y 0 c) は、方程式 ax + by = c の解になります。
前と同様の推論により、すべての解決策を見つけることが可能になります。
解のセット—特定の解 (x 1 , y 1 ) が既知である場合、解のセットはペア (x 1 +bk, y 1 – ak) で構成されます。ここで、k は任意の相対整数です。
一般的な場合
d を a と b の gcd と呼びます。
c が d の倍数でない場合—方程式には解がありません。
確かに、d で a と b を割ると、d は ax + の形式の式でも除算されます。ここで、a と b は相対的な整数であるため、d は c を除算する必要があります。
ここで、d が c を除算すると、a 1 、b 1 、および c 1に対して次のような 3 つの整数が存在すると仮定します。
- a = ダ1
- b = デシベル1
- c = 直流1
a 1と b 1は互いに素です。
方程式 ax + by = c は、a 1と b 1が互いに素である方程式 a 1 x + b 1 y = c 1と等価であり、このケースはすでに解決されています。次に、一般的な場合の解決策を取得します。
- 特定の解（ｘ １ 、ｙ １ ）が知られている場合、解のセットはペア（ｘ １ ＋ｂ １ ｋ、ｙ １ −ａ １ ｋ）で形成され、ｋは任意の相対整数である。
したがって、プロパティは次のようになります。
c が d の倍数の場合—この方程式には常に解が認められます。特定の解 (x 1 , y 1 ) が既知である場合、解のセットはペアで形成されます。
最小限のシステム
このセクションでは、c が d の倍数であると仮定します。与えられた方程式 ax + by = c のすべての解の中で、 x 2 + y 2が可能な限り最小となるものを探すことができます。
これには、値( x 1 + b 1 k ) 2 + ( y 1 − a 1 k ) 2を最小にすることが含まれます。 f ( t ) = ( x 1 + b 1 t ) 2 + ( y 1 − a 1 t ) 2で定義される実変数t の関数を考慮すると、この 2次関数の研究により、この関数が次のような性質を持つことがわかります。最小値
- $$ {t=\frac{a_1y_1-b_1x_1}{a_1^2+b_1^2}} $$
t が整数の場合、解のペアは( x 1 + b 1 t , y 1 − a 1 t )になります。それ以外の場合、 f を最小にする整数は、t に近い整数 k le(s) になります。
x 2 + y 2の値が最小である ax + by = c の解の整数のペアは( x 1 + b 1 k , y 1 − a 1 k )です。ここで、k は整数( s) に最も近い k
a と b が互いに素である場合、t が整数である場合を説明する価値があります。整数 c がa 2 + b 2の倍数である場合に限り、t が整数であることを証明します。最小システムの解は次のようになります。
a と b が互いに素である場合、a と b が奇数であり、整数 c が