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