다항합동식 (편집) (8)

=== 해 구하기 ===
다음과 같은 절차를 통해 [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})]([math(p)]는 소수)를 구할 수 있다.

그리고 [math(m)]을 소인수분해한 후 CRT를 이용하면 [math(f(x) \equiv 0\ \pmod{m})]의 모든 해를 구할 수 있다.

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.