다른 모듈로 공간으로 표현 된 방정식 시스템을 해결하는 알고리즘이 있습니까? 이 시스템의 솔루션서로 다른 모듈로 연결된 방정식 시스템을 해결하십시오
(x1 + x2 ) % 2 = 0
( x2 + x3) % 2 = 0
(x1 + x2 + x3) % 3 = 2
하나입니다 :
x1 = 0
x2 = 2
x3 = 0
어떻게 산술적으로 (무력 알고리즘을 사용하지 않고)이 솔루션을 찾을 수 exemple 들어 는 방정식의 시스템을 고려?
감사
첫 번째 라인 1 개를 말과 동일, X2는 모든 짝수 또는 홀수 번호. 두 번째 줄은 x2와 같으며 x3은 모두 홀수이거나 짝수입니다. 따라서 x1, x2, x3은 모두 짝수 또는 모두 홀수입니다. 세 번째 줄에서 질문을 "3k + 2로 누적되는 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)을 선택하면 솔루션을 얻을 수 있습니다.
음,이 시스템과 같은 Diophantine 방정식의 ** 시스템 **을 자동으로 해결하는 알고리즘이 있습니까? –
@ThomasBernard 업데이트 된 솔루션보기 – ElKamina
답을 고맙습니다. 행렬 단일 모액 감소 방법을 사용하여, nis의 함수로 xi를 자동으로 표현할 수있었습니다. 하지만 기본적으로 알려지지 않은 변수가 아닌 m 변수를 가진 시스템으로 끝나기 때문에 알고리즘이 자동으로 올바른 ni 값을 선택하는 방법을 이해하지 못합니다. ni는 무료입니다.하지만 항상 그런 경우가 있습니까? ni에 대한 제약으로 끝날 수 없습니까?) –
시스템을 모듈로 LCM (최소 공통 배수)으로 변환 할 수 있습니다. 모든 방정식의 모듈러스를 구하고 각 방정식을 적절히 곱하십시오.
답변 해 주셔서 감사합니다. 조금 더 개발할 수 있을까요? "각 방정식을 적절하게 곱하십시오"라고 말하면 정확히 무엇을 의미합니까? 내가 게시 한 예제에서 LCM은 6이므로 시스템이 모듈로 6으로 변환 될 수 있습니까? –
@ThomasBernard 예, 정확하게. 처음 2는 3을, 마지막은 2를 곱해야합니다. – valdo
고마워요. 그러나 이제는 다른 문제로 끝납니다. 내 방정식의 선형 방정식을 풀기 위해 행렬의 대각선에 "1"값만 얻으려면 행을 반전 모듈로 곱해야하는 Gauss-Jordan 제거 알고리즘을 사용했습니다. 그러나 여기서는 2^-1 mod 6과 3^-1 mod 6이 존재하지 않기 때문에 불가능합니다 ... (그리고 저는 단지 제 행렬에 2, 3, 0 값을가집니다) –
흥미로운 문제. 물론 프레스 버거 (Presburger) 산술에 대한 결정 절차는 효과가있을 수 있지만 복잡하고 느립니다. 흥미로운 경우는 moduli가 같은 소수의 힘이면; 주어진 방정식 ... = ... mod (pq) 여기서 gcd (p, q) = 1이면 ... = mod p와 ... = mod q로 분할 할 수있다. Chinese Remainder Theorem을 사용하여 최종 해를 모으십시오. –