Linear Diophantine Equation
Problem Solving/Algorithm notes 2011. 1. 25. 00:07
Linear Diophantine Equation (디오판토스 방정식) 푸는 방법에 관한 괜찮은 자료를 찾아서 한번 읽어봤다..
관련자료:
간단히 예를 들어보자..
을 만족하는 integer x, y 를 구하고 싶다면..
일단 GCD(3, 4) = 1 이므로 우선 다음 식을 풀어야한다..
Extended Euclid 에 의해서 x = -1, y = 1 을 구했다..
자, 이제 원래 식으로 환원하면.. x = -43, y = 43 이 나온다..
따라서 위 식을 만족하는 모든 integer (x, y) 는
즉,
(-43, 43),
(-39, 40),
(-35, 37),
...
...
이렇게 구할 수 있다.. ㅎㅎ
근데.. ax+ by = c 에서 x, y 를 구하는 법은 이해했는데..
ax - by = c 인 경우에는 어떻게 구하면 될까..???? -_-;
관련자료:
Introduction to Diophantine Equations.pdf간단히 예를 들어보자..
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 = 임의의 정수)
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 |