정수론 #3-4 :: 고차방정식

Lagrange’s Theorem

$\begin{gather*}f(x)=a_0x^d+a_1x^{d-1}+...+a_{d-1}x+a_d \end{gather*}$

• d ≥ 1, a0 ≠ 0
• 즉, d차 방정식. (a와 x의 차수 순서 주의!)

$\begin{gather*}If \ \ p\not{|} a_0, \ \ then \ \ f(x) \equiv 0 \mod p \\ has \ \ of \ \ most \ \ d \ \ distinct \ \ solutions \ \ mod \ \ p \end{gather*}$

 

• p가 소수라면 d차 방정식은 최대 d개의 해를 가진다.
• 해는 {0, 1, 2, …, p-1}들 중에 존재. (p부터는 중복 발생.)

 

• 최고차항의 계수가 p의 배수가 아니다. ⇒ d차 다항식. (p의 배수라면 나눠짐..)

 

---

 

고차방정식 풀이 기본 알고리즘

x에 {0, 1, 2, …, p-1}을 넣어서 해인지 확인한다.

 

계수 줄이기 테크닉

$\begin{gather*}7x^2+11x-1 \equiv 0 \mod 5 \\ \Rightarrow 5x^2 + 2x^2 + 10x+1x+5-1 \equiv 0\mod 5 \\ \Rightarrow 2x^2 + x + 4 \equiv 0 \mod 5 \end{gather*}$

위와 같이 간단하게 식을 고칠 수 있다.


ex)

$\begin{gather*}x^2-3x+2 \equiv 0 \mod m \\ \Rightarrow (x-2)(x-1) \equiv0 \mod m \end{gather*}$

이런 경우 x ≡ 2, x ≡ 1은 해에 무조건 들어간다.
(단, m이 해보다 작으면 성립안하므로 그 때는 직접 x에 넣는 기본 알고리즘을 추천)
m이 소수가 아니면 해는 차수보다 많을 수 있다. ex) m = 6인 경우

m	2	3	4	5	6
해	0, 1	1, 2	1, 2	1, 2	1, 2, 4, 5

m이 소수가 아니면 prime divisor property를 적용 못하기에
(x-1)(x-2) ≡ 0 mod m ⇒ x-1 ≡ 0 or x-2 ≡ 0 mod m 이 성립하지 않는다. (역은 성립한다.)

m이 소수인 경우에는 최대 d(차수)개 까지 나온다.

 

---

 

d차 다항식의 해의 개수

• f(x) : d차 다항식
• f(x) = 0 has at most d solutions in R
  실수체계 안에서 최대 d개의 해가 가능.

 

증명

해가 없으면 상관 없다. ex) x^2 + 1 = 0

 

해가 있다면 인수 정리

Long Division을 사용하여 다항식의 몫과 나머지 계산을 할 수 있다.

 

$\begin{gather*}f(x)=g(x)q(x)+r(x) \end{gather*}$

 

이때 r(x)의 차수 < q(x)의 차수를 만족할 때까지 계속 나눠야 한다.

 

f(x)의 해가 x1이라면

 

$\begin{gather*}f(x)=(x-x_1)q(x)+r \end{gather*}$

 

이때 f(x1) = r = 0 이므로 다음과 같다.

 

$\begin{gather*}f(x)=(x-x_1)q(x) \end{gather*}$

 

위의 인수 정리를 d차 다항식에 적용하면 다음과 같다.

 

$\begin{gather*}f(x)=(x-x_1)q(x)=0 \\ \Rightarrow f(x)=(x-x_1)(x-x_2)...(x-x_k)h(x)=0 \end{gather*}$

 

이때 h(x)는 해가 없는 다항식(보통 실수로 나온다)

 

따라서 해는 다음과 같다.

 

$\begin{gather*}x=x_1,x_2,...,x_k, \ \ \ k \le d \end{gather*}$

 

그러므로 해는 최대 d개만 가능하다.

 

---

 

mod p의 몫과 나머지 정리

mod p에서도 몫과 나머지 계산이 가능할까?
ex) x^2+x+1 ≡ (2x-1)q(x) + r(x) mod 7

q(x) = (1/2x + α)일 것 같다. 그래야 x^2의 계수가 1이 되기 때문이다.
하지만 정수 체계에서는 1/2는 존재하지 않는다. ⇒ 역원 개념을 사용하자.

mod 7에서 2의 역원은 4

따라서 q(x) = 4x + 6,
r(x) = 7 ≡ 0 mod 7

 

mod p에서도 역원을 사용하여 몫과 나머지 계산이 가능하다.

단, p가 소수가 아니라면 역원이 존재하지 않을 수도 있으므로 불가능.

 

---

 

d차 다항식 mod p의 해의 개수

• f(x) : d차 다항식
• p : 소수
• f(x) ≡ 0 mod p has at most d solutions in {0, 1, …, p-1}
  0 ~ p-1 안의 값들 중에서 최대 d개의 해가 가능.

 

증명

해가 없으면 상관 없다.

 

해가 있다면 인수 정리.

p가 소수라면 역원이 있기때문에 몫과 나머지 정리가 가능하다.

 

$\begin{gather*}f(x)≡(x-x_1)q(x)≡0 \mod p \\ \Rightarrow f(x)≡(x-x_1)(x-x_2)...(x-x_k)h(x)≡0 \mod p \end{gather*}$

 

이때 h(x)는 해가 없는 다항식(보통 실수로 나온다)

 

여기서 Prime divisor property를 적용한다.

 

$\begin{gather*}\Rightarrow p|(x-x_1)...(x-x_k) \\ \Rightarrow p|(x-x_1),..., p|(x-x_k) \\ \Rightarrow x-x_1 ≡ 0, \ ... \ , x-x_k≡0 \mod p \\ \Rightarrow x≡ x_1, \ ... \ , x≡x_k \mod p \end{gather*}$

 

따라서 해는 다음과 같다.

 

$\begin{gather*}x≡x_1,x_2,...,x_k, \mod p \ \ \ k \le d \end{gather*}$

 

그러므로 소수일 때 해는 최대 d개만 가능하다.

소수가 아니라면 해는 d개보다 더 많을 수도 있다.

 

---

 

Prime divisor property ↔ no Zero Divisiors

Zero Divisors mod m

 

$\begin{gather*}a \not≡0 \ and \ b \not≡0, \ \ ab≡0 \mod p \\ \Rightarrow (a,b) : Zero \ \ Divisors \end{gather*}$

 

Prime divisor Property ↔ There is no Zero Divisors mod p

 

p가 소수라면 Zero Divisors mod p는 없다.

p가 소수가 아니라면 Zero Divisors mod p가 존재한다.