고1 나머지정리 문제
A(x)=B(x)+R(x) 라고 할때 B(x)와 R(x) 의 최대공약수가 x-1
이라는데 B(x)로 나누었는데 어떻게 B(x)가 나머지와 공약수가 있는지 의문이네요...
답변부탁드립니다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
적중되지 않아도 1도 원망하지 않을 학생들을 대상으로, 출제예상 주제 강의를 7일...
-
『미래를 바꾼 아홉 가지 알고리즘』(에이콘출판사)이라는 책을 작년 말 개인블로그에...
수에서도 마찬가지 일이 일어남을 잘 생각해보세요. 12를 8로 나눈 나머지는 4지만, 세 수 모두 4의 배수가 됩니다.
잘 생각해보시면, 나누는 식 B(x)와 나눠지는 식 A(x)가 공통인수 G(x)를 가질 경우, 나머지 R(x) 역시 그 공통인수를 가져야 합니다. 왜냐하면
A(x) - Q(x)B(x) = R(x)
이고, 좌변은 G(x)의 배수이기 때문이지요. 이는 G(x)가 A(x)와 B(x)의 최대공약수인 경우에도 마찬가지입니다.
사실, 유클리드 호제법(Euclidean algorithm)이라고 해서 이러한 관찰의 일반화가 있습니다. 나누는 과정을 계속 하면 결국 두 수의 '최대공약수'에 다다른다는 것이지요!