2017-02-04 62 views
6

異なるモジュロ空間で表される方程式の系を解くアルゴリズムはありますか?このシステムのソリューションの異なるモジュロでリンクされた方程式のシステムを解く

(x1 + x2 ) % 2 = 0 
( x2 + x3) % 2 = 0 
(x1 + x2 + x3) % 3 = 2 

一つである:

x1 = 0 
x2 = 2 
x3 = 0 

は、どのように私は算術(ブルートフォースアルゴリズムを使用せずに)この解決策を見つけることができexempleについては は、この連立方程式を検討しますか?

おかげ

+0

興味深い問題です。確かに、プレスバーガー算術の決定手順はうまくいくが、複雑で遅い。興味深いケースは、モジュロが同じ素数のべき乗である場合です。与えられた方程式... = ... mod(pq)ここで、gcd(p、q)= 1とすると、... = ... mod pと... = ... mod q、中国の剰余定理を用いて最終解を組み立てる。 –

答えて

0

最初の行は、X1を言うと同じであり、x2はすべて偶数またはすべて奇数。 2行目はx2と同じですが、x3はすべて偶数または奇数です。 したがって、x1、x2、x3はすべて偶数またはすべての奇数です。 3行目から「3k + 2に累積する3つの奇数または3つの偶数」を置き換えることができます。

3

あなたは文学のソリューションが存在し、これはのための線形ディオファントス方程式の問題であり、今

x1 + x2 = 2*n1 
x2 + x3 = 2*n2 
x1 + x2 + x3 = 3*n3 + 2 

としてこれらの式を書き換えることができます。

例:http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

また参照:https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdf

アルゴリズム:この場合NKS

の関数として

書き込みXI:

x3 = 3*n3 + 2 - 2*n1 
x2 = 2*n2 - (3*n3 + 2 - 2*n1) 
x1 = 2*n1 - (2*n2 - (3*n3 + 2 - 2*n1)) 

があるので右の部分に分割はありません。任意の(n1、n2、n3)を選択すると、解決策が得られます。

+0

まあ、このようなディオファンタス方程式の**システム**を自動的に解決するアルゴリズムはありますか?私は何も見つけませんでした... –

+0

@ThomasBernard更新された解決策を見てください – ElKamina

+0

答えをありがとう。行列単項式生の縮小法を使って、nisの関数としてxiを自動的に表現することができました。しかし、私は基本的に未知の変数がm個ある代わりにm個の未知数の変数を持つシステムになってしまい、アルゴリズムが自動的に正しいniの値をどのように選ぶことができないのか分かりません(この例では、 niは無料ですが、それはいつもそうでしょうか、そのniに制約を課すことはできませんか?) –

0

システムをモジュロLCM(最小公倍数)に変換できます。すべての等式のモジュロのLCMを見つけて、各方程式を適切に掛けます。

+0

あなたの答えをありがとう。あなたはもう少しそれを開発できますか? 「各方程式を適切に乗算する」と言うと、正確にはどういう意味ですか?私が掲示した例では、LCMは6であるので、システムはどのようにモジュロ6に変換されますか? –

+0

@ThomasBernardはい、正確です。最初の2は3で、最後は2で乗算する必要があります。 – valdo

+0

ありがとうございます。しかし、私は今や別の問題に終わる。私のモジュロnの一次方程式系を解くために、私はガウス・ジョーダン除去アルゴリズムを使用しました。このアルゴリズムでは、ある行をその逆モジュロで乗算して、行エシェロン行列の対角に「1」だけの値を求めます。しかし、ここでは2^-1 mod 6と3^-1 mod 6が存在しないので不可能です(そして私の行列には2、3、0の値しかありません) –

関連する問題