(+)분류 : 가져온 문서/오메가
Polynomial Congruence
정수 계수 다항식에 대한 합동식이다.
목차
1. 정의
2. 해법
2.1. 해의 개수
2.1.1. 차수와의 관계
2.1.1.1. 증명
2.1.2. 차수와 해의 개수가 같을 필요충분조건
2.1.2.1. 증명
2.2. 해 구하기
2.2.1. 증명
3. 영상
1. 정의
2. 해법
2.1. 해의 개수
2.1.1. 차수와의 관계
2.1.1.1. 증명
2.1.2. 차수와 해의 개수가 같을 필요충분조건
2.1.2.1. 증명
2.2. 해 구하기
2.2.1. 증명
3. 영상
1. 정의 ✎ ⊖
f(x) \\in \\Bbb{Z}[x],\\ m \\in \\Bbb{Z}에 대하여 다음과 같은 꼴의 합동식을 말한다.
f(x) \\equiv 0 \\pmod{m}
f(x) \\equiv 0 \\pmod{m}
2. 해법 ✎ ⊖
2.1. 해의 개수 ✎ ⊖
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인 경우만 고려해줘도 충분하다.
양변에 \\bmod p를 취하면
f(x) \\equiv r(x) \\pmod{p}
따라서 f(x)와 r(x)의 해집합은 같게 되므로
f(x) \\equiv 0 \\pmod{p} 꼴의 다항합동식은 \\deg\\ f<p인 경우만 고려해줘도 충분하다.
2.1.1. 차수와의 관계 ✎ ⊖
다항합동식 f(x) \\equiv 0\\ \\pmod{p}에서 f(x)의 계수 중 p의 배수가 아닌 것이 있을 때 그 해의 개수는 \\deg\\ f개 이하이다.
2.1.1.1. 증명 ✎ ⊖
\\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개 이하이다. 이로써 증명이 끝난다.
이제 \\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의 배수인 것과 동치이다.
2.1.2.1. 증명 ✎ ⊖
(\\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)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의 배수이다.
2.2. 해 구하기 ✎ ⊖
다음과 같은 절차를 통해 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}의 모든 해를 구할 수 있다.
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}의 모든 해를 구할 수 있다.
2.2.1. 증명 ✎ ⊖
우선 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가 존재하지 않는다.
따라서 증명되었다.
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가 존재하지 않는다.
따라서 증명되었다.
