Linear Diophantine Equation (디오판토스 방정식) 푸는 방법에 관한 괜찮은 자료를 찾아서 한번 읽어봤다..

관련자료:



간단히 예를 들어보자..

3x + 4y = 43

을 만족하는 integer x, y 를 구하고 싶다면..
일단 GCD(3, 4) = 1 이므로 우선 다음 식을 풀어야한다..

3x + 4y = 1

Extended Euclid 에 의해서 x = -1, y = 1 을 구했다..
자, 이제 원래 식으로 환원하면.. x = -43, y = 43 이 나온다..

따라서 위 식을 만족하는 모든 integer (x, y) 는

x = -43 + 4k,
y = 43 - 3k
(k = 임의의 정수)


즉,
(-43, 43),
(-39, 40),
(-35, 37),
...
...


이렇게 구할 수 있다.. ㅎㅎ


근데.. ax+ by = c 에서 x, y 를 구하는 법은 이해했는데..
ax - by = c 인 경우에는 어떻게 구하면 될까..???? -_-;


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Euler's phi (Totient function)  (0) 2016.08.15
Inversion Count  (0) 2016.01.31
The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유..  (2) 2011.03.02
Linear Diophantine Equation  (0) 2011.01.25
점과 선분과의 거리  (2) 2011.01.22
Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23

Leave a Comment


to Top