gcd(12378, 3054)= 6의 계산 시, 유클리드 알고리즘의 나눗셈 순서가 다음과 같은데
다음 그림과 같이 나눗셈 수행할 때 나머지에 조건을 부과해서 나눗셈을 하면 단계 수를 줄일 수 있다고 합니다.
(조건 : 나머지의 절댓값이 이전 단계의 나머지의 절반보다 작도록)
그런데 이 방법에서는 나머지가 음수가 될 수 있는데, 다음 단계의 나눗셈에서 그 음수의 나머지를 그대로 가져가서 나눗셈을 하는건지 양수로 바꿔주는건지 의문이네요.
- 2단계에서의 나머지 -24가, 3단계에서는 -24가 아닌 24를 가지고 썼고요.
- 3단계에서의 나머지 -6은, 4단계에서 그대로 -6을 가져다 썼네요.
방식이 일관적이지 않아 어떻게 하는 것인지 궁금합니다...
상관없음 gcd는 양수라서 gcd(a, -b) = gcd(a, b)여야함 책에서는 편하게 하려고 좌변을 양수로한듯
아ㅏㅏㅏ 이해했습니다 감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
근데 좌변을 항상 양수로 두더라도, 몫을 양/음으로 바꿔서 일관되게 만들 수 있는 거아님?
나머지를 그대로 가져오는 것으로 통일한다고 하면 - 2단계는 162 = (-7)*(-24) - 6가 되면 될 것이고 - 3단계는 24 = (-4)*(-6) + 0처럼 그대로이면 될 것이고 나머지에 항상 절댓값을 취하는 것으로 통일한다고 하면 - 2단계는 162 = 7*24 - 6처럼 그대로이면 될 것이고 - 3단계는 24 = 4*6 + 0가 되면 될 것이고