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가 존재하지 않는다.
따라서 증명되었다.
