[[분류:가져온 문서/오메가]]
Polynomial Congruence
정수 계수 [[다항식]]에 대한 합동식이다.
== 정의 ==
[math(f(x) \in \Bbb{Z}[x],\ m \in \Bbb{Z})]에 대하여 다음과 같은 꼴의 합동식을 말한다.
[math(f(x) \equiv 0 \pmod{m})]
== 해법 ==
=== 해의 개수 ===
[math(f(x)=(x^p-x)q(x)+r(x)\ (q(x),\ r(x) \in \mathbb{Z},\ \deg\ r<\deg\ (x^p-x)=p\ or\ r(x)=0))]
양변에 [math(\bmod p)]를 취하면
[math(f(x) \equiv r(x) \pmod{p})]
따라서 [math(f(x))]와 [math(r(x))]의 해집합은 같게 되므로
[math(f(x) \equiv 0 \pmod{p})] 꼴의 다항합동식은 [math(\deg\ f<p)]인 경우만 고려해줘도 충분하다.
==== 차수와의 관계 ====
다항합동식 [math(f(x) \equiv 0\ \pmod{p})]에서 [math(f(x))]의 계수 중 [math(p)]의 배수가 아닌 것이 있을 때 그 해의 개수는 [math(\deg\ f)]개 이하이다.
===== 증명 =====
[math(\deg\ f=0)]인 경우는 자명하다.
이제 [math(\deg\ f=n-1)]일 때 성립함을 가정하고 [math(\deg\ f=n-1)]인 경우에 증명을 하면 된다.
[math(f(x) \equiv 0\ \pmod{p})]의 해가 존재하지 않는다면 증명할 것이 없다.
[math(f(x) \equiv 0\ \pmod{p})]의 해 [math(a)]가 존재함을 가정하면
다항식의 나눗셈정리에 의해 [math(f(x)=(x-a)g(x)+r\ (g(x) \in \mathbb{Z}[x],\ r \in \mathbb{Z}))]인 [math(g(x),r)]이 존재한다. [math(x)]에 [math(a)]를 대입하고 양변에 [math(\bmod p)]를 취하면 [math(r \equiv f(a) \equiv 0\ \pmod{p})]를 얻으므로 [math(f(x) \equiv (x-a)g(x)\ \pmod{p})]이다.
따라서 [math(f(x) \equiv 0\ \pmod{p})]와 [math((x-a)g(x) \equiv 0\ \pmod{p})]의 해집합은 동일하다. [math(\deg\ g=n-1)]임은 자명하므로 [math((x-a)g(x) \equiv 0\ \pmod{p})]의 해는 [math(n)]개 이하이다.[* [math(g(x))]의 계수 중 [math(p)]의 배수가 아닌 것이 있음은 자명합니다.] 그러므로 [math(f(x) \equiv 0\ \pmod{p})]의 해의 개수 또한 [math(n)]개 이하이다. 이로써 증명이 끝난다.
==== 차수와 해의 개수가 같을 필요충분조건 ====
[math(\deg\ f \leq p)]이고 최고차항의 계수가 [math(1)]인 [math(f(x) \in \mathbb{Z}[x])]에 대하여 다항식의 나눗셈정리에 의해 [math(x^p-x=f(x)q(x)+r(x))]인 [math(q(x))], [math(r(x))]가 유일하게 존재한다. 이 때, [math(f(x) \equiv 0\ \pmod{p})]의 해의 개수가 정확히 [math(\deg\ f)]개인 것은 [math(r(x))]의 모든 항의 계수가 [math(p)]의 배수인 것과 동치이다.
===== 증명 =====
[math((\Leftarrow))] [math(x^p-x=f(x)q(x)+r(x))]인 [math(q(x))], [math(r(x))]의 양변에 [math(\bmod p)]를 취하면
[math(f(x)q(x) \equiv 0\ \pmod{p})]
즉 [math(f(x)q(x) \equiv 0\ \pmod{p})]의 해집합은 [math(\bmod p)]에 대한 완전잉여계이다.
그런데 [math(f(x) \equiv 0\ \pmod{p})]의 해의 개수는 [math(\deg\ f)]개 이하, [math(q(x) \equiv 0\ \pmod{p})]의 해의 개수는 [math(\deg\ q)]개 이하이므로 [math(f(x)q(x) \equiv 0\ \pmod{p})]의 해의 개수는 [math(\leq \deg\ f + \deg\ q = p)]가 된다. 등호가 성립해야 하므로 [math(f(x) \equiv 0\ \pmod{p})]의 해의 개수는[math(\deg\ f)], [math(q(x) \equiv 0\ \pmod{p})]의 해의 개수는 [math(\deg\ q)]개 이다.
따라서 [math(f(x) \equiv 0\ \pmod{p})]의 해의 개수는 정확히 [math(\deg\ f)]개이다.
[math((\Rightarrow))] [math(\deg\ f=0)]이거나 [math(r(x)=0)]인 경우는 자명하므로 그 이외의 경우만 고려하면 된다.
[math(x^p-x=f(x)q(x)+r(x))]에서 [math(r(x) \equiv 0\ \pmod{p})]의 해집합은 [math(f(x) \equiv 0\ \pmod{p})]의 해집합을 포함한다.
즉 [math(r(x) \equiv 0\ \pmod{p})]의 해는 [math(\deg\ f)]개 이상이다.
그런데 [math(\deg\ r < \deg\ f)]이므로 [math(r(x))]의 모든 항의 계수가 [math(p)]의 배수이어야 한다.
따라서 항상 [math(r(x))]의 모든 항의 계수가 [math(p)]의 배수이다.
=== 해 구하기 ===
다음과 같은 절차를 통해 [math(f(x) \equiv 0\ \pmod{p^k})]([math(p)]는 소수)를 구할 수 있다.
1. [math(f(x) \equiv 0\ \pmod{p})]의 모든 해를 구한다.
2. [math(f(x) \equiv 0\ \pmod{p^k})]의 어떤 해 [math(s_k)]를 잡고 [math(f'(s_k)t \equiv -\frac{f(s_k)}{p^k}\ \pmod{p})]를 푼다(처음엔 [math(k=1)]이다.).
3. [math(\text{(i)}\ p \nmid f'(s_k))] : [math(t \equiv -f(s_k)f'(s_k)^*/p^k\ \pmod{p})]로 [math(t)]가 유일하게 결정된다.
4. [math(\text{(ii)}\ p \mid f'(s_k)\ , p^{k+1} \mid f(s_k))] : [math(\forall t \in \{0,1,\cdots,p-1\})]가 조건을 만족시킨다.
5. [math(\text{(iii)}\ p \mid f'(s_k)\ , p^{k+1} \nmid f(s_k))] : 조건을 만족시키는 [math(t)]가 존재하지 않는다.
6. 위의 t를 이용하여 [math(s_{k+1}=s_k+p^kt)]인 [math(s_{k+1})]를 결정한다.[* 한 개 혹은 [math(p)]개 혹은 0개겠죠.] [math(s_{k+1})]는 [math(f(x) \equiv 0\ \pmod{p^{k+1}})]의 해이다.
7. [math(f(x) \equiv 0\ \pmod{p^k})]의 다른 해를 잡아 2.부터 반복한다.
8. [math(f(x) \equiv 0\ \pmod{p^k})]의 모든 해에 대하여 위 과정을 반복하여 [math(f(x) \equiv 0\ \pmod{p^{k+1}})]의 해를 모두 구했으면 [math(k)]에 1을 더하고 다시 2.부터 반복한다.
9. [math(f(x) \equiv 0\ \pmod{p^n})]의 해를 모두 구할 때까지 계속한다.
그리고 [math(m)]을 소인수분해한 후 CRT를 이용하면 [math(f(x) \equiv 0\ \pmod{m})]의 모든 해를 구할 수 있다.
==== 증명 ====
우선 [math(f(x) \equiv 0\ \pmod{p^{k+1}})]의 해에 대해 생각해보자([math(k \in \Bbb{N})]).
[math(f(x) \equiv 0\ \pmod{p^{k+1}})]의 한 해를 [math(s_{k+1})]라 한다면 [math(f(s_{k+1}) \equiv 0\ \pmod{p^k})] 또한 성립하므로 [math(f(x) \equiv 0\ \pmod{p^k})]의 어떤 해 [math(s_k)]가 존재하여 [math(s_{k+1} \equiv s_k\ \pmod{p^k})]가 성립한다. 그러므로 [math(s_{k+1}=s_k+p^kt\ (0 \leq t \leq p-1))]라고 할 수 있다. 즉 여기서 [math(t)]를 결정해 주면 [math(f(x) \equiv 0\ \pmod{p^k}))]의 해에서 [math(f(x) \equiv 0\ \pmod{p^{k+1}})]의 해를 이끌어낸 것이 된다.
[math(f(s_{k+1}) \equiv 0\ \pmod{p^k})]에서 [math(s_{k+1})]에 [math(s_k+p^kt)]를 대입하면 [math(f(s_k+p^kt) \equiv 0\ \pmod{p^k})]가 되는데, 테일러 전개 [math(f(s_k+p^kt)=f(s_k)+p^ktf^\prime (s_k)+\frac{(p^kt)^2}{2!}f^{\prime \prime} (s_k)+\cdots)]를 이용하면 다음을 얻는다.
[math(f(s_{k+1}) \equiv f(s_k)+p^ktf^\prime (s_k)\ \pmod{p}^{k+1}))]
[math(f^\prime (s_k)t \equiv -\frac{f(s_k)}{p^k}\ \pmod{p})]
여기서 다음과 같이 경우를 나눌 수 있다.
[math(\text{(i)}\ p \nmid f^\prime (s_k))] : [math(t \equiv -f(s_k)f^\prime (s_k)^*/p^k\ \pmod{p})]로 [math(t)]가 유일하게 결정된다.
[math(\text{(ii)}\ p \mid f^\prime (s_k)\ , p^{k+1} \mid f(s_k))] : [math(\forall t \in \{0,1,\cdots,p-1\})]가 조건을 만족시킨다.
[math(\text{(iii)}\ p \mid f^\prime (s_k)\ , p^{k+1} \nmid f(s_k))] : 조건을 만족시키는 [math(t)]가 존재하지 않는다.
따라서 증명되었다.
== 영상 ==
[youtube(TeciHpMt1mw)]
[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]
