정수론 #0 :: 소인수분해의 존재성과 유일성

존재성 : Existence ∃
유일성 : Uniqueness !

 

---

소인수분해의 존재성

소수면 소인수분해가 필요 없다.

소수가 아니면 나누어지는 소인수가 무조건 존재한다.

 

$N =p_1... p_n$

 

소인수분해를 하다보면 각 소수들은 일단 N보다 작으며 점점 1까지 작아지므로 유한개이다.

 

$N=p_1a, \ \ \ \ \ a< N$

• p1의 범위 : 2 ~ N/2

---

소인수분해의 유일성

소인수분해가 유일하지 않은 경우

예시) 짝수들만의 세계

 

$60 = 2*30=6*10$

 

⇒ 소인수분해의 서로 다른 결과가 두가지 생긴다. (6, 10, 30은 짝수세계에서 소수이다.)

⇒ 즉, 짝수세계에서는 소인수분해가 유일하지 않다.

⇒ 현실세계에서는 어떨까? (답 : 유일하다.)

 

---

 

소인수분해의 유일성 귀류법(모순 찾기) 증명

$\begin{gather*}N=p_1...p_k=q_1...q_l \\ p_i \not= q_j, \ \ \ \forall i,j\end{gather*}$

 

서로 다른 소인수분해가 존재한다고 가정한다.

서로 다르다는 것은 두 소인수분해 사이에는 공통 소수가 존재하지 않다는 것이다.

 

$\begin{gather*}\Rightarrow p_1|(q_1...q_l) \\ \end{gather*} $

 

p1은 N의 소인수이므로 N=q1…ql을 나눌 수 있다.

 

$\begin{gather*}\Rightarrow p_1|q_1 \ or \ p_1|q_2 \ or \ ... \ p_1|q_l \\ \end{gather*}$

 

q들은 전부 소수이므로 p1은 q들 중 하나로 나눌 수 있다.

이부분을 Prime divisor property라고 부른다.

 

$\begin{gather*}\Rightarrow p_1=q_1 \ or \ ... \ p_1=q_l \end{gather*} $

 

따라서 p1은 나누어 떨어지는 q들 중에 하나이다. (소수이기 때문에 ‘=’가 성립한다.)

하지만 p1은 q와 다르다고 처음 전제를 세웠기 때문에 모순된다.

따라서 소인수분해는 유일하게 존재한다.

 

---

 

Prime divisor property

p가 소수(prime)일 때

 

$\begin{gather*}p|ab \Rightarrow p|a \ or \ p|b\end{gather*} $

 

소수가 ab를 나눌 수 있다면 소수는 a와 b중에 하나로 나눌 수 있다. 증명 필요.

 

---

 

Zermelo’s Proof (또다른 증명 방법)

$\begin{gather*}l=p_1...p_m=q_1...q_n\end{gather*} $

 

서로 다른 소인수분해가 존재한다고 가정한다.

서로 다르다는 것은 두 소인수분해 사이에는 공통 소수가 존재하지 않는다는 것이다.

l은 소인수분해가 유일하지 않은 수 중에서 가장 작은 수이다.

 

$\begin{gather*}p_1< q_1\le q_2 \le ... \le q_n\end{gather*} $

 

비교 정렬을 통해 가장 작은 소수 p1을 찾는다.

 

$\begin{gather*}k=p_1(p_2...p_m - q_2...q_n)\end{gather*} $

 

p1은 k의 소인수이다.

 

$\begin{gather*}=l-p_1q_2...q_n \\ =q_1q_2...q_n - p_1q_2...q_n \\ =(q_1-p_1)q_2...q_n \end{gather*}$

 

q2…qn은 전제에서 소수라고 이미 정해졌다. q1 - p1은 소수일까?

 

k = l - p1q2…qn에 의하여 k < l을 알 수 있다. (l에서 무언가를 뺐으므로)

 

$\begin{gather*}p_1|(q_1-p_1) \\ \Rightarrow q_1-p_1 = ap_1 \\ \Rightarrow q_1 = p_1 + ap_1 = p_1(1+a) \\ \Rightarrow p_1|q_1 \\ \Rightarrow p_1 = q_1 \end{gather*}$

 

p1은 q2…qn과 다른 소수이므로 나눌 수 없다.

그리고 위의 내용에 의하여 p1이 q1 - p1을 나눌 수 있다면 p1=q1이 되는데 이것은 전제에 모순된다.

따라서 p1은 q1 - p1을 나눌 수 없다.

 

즉, 나눌 수 있는 항이 없으므로 k는 p1을 소인수로 가지지 않는다.

하지만 p1은 k의 소인수이다. 두 결과가 모순되므로 서로 다른 소인수분해가 존재한다는 전제가 틀렸다.

 

따라서 소인수분해는 유일하게 존재한다.