정수론 #5-1 :: 소수의 무한성

Prime number

Prime factorization (소인수 분해)

 소인수분해의 존재성과 유일성

 

$\begin{gather*}n=p_1^{k_1}p_2^{k_2}...p_l^{k_l} \end{gather*}$

 

---

 

Euclid Theorem

There are infinitely many primes

소수는 유한하지 않다.

 

증명 (귀류법)

소수는 유한하다고 가정하면 모든 소수가 들어있는 소수의 리스트를 구할 수 있다.

 

$\begin{gather*}p_1,p_2,...,p_r \end{gather*}$

 

$\begin{gather*}A=p_1p_2...p_r+1 \end{gather*}$

 

A는 소수의 리스트에 존재하지 않는 수다.

따라서 A는 소수가 아니다.

 

그럼 A가 합성수라면 A는 모든 소수 p1,…,pr 중에

적어도 하나 이상으로는 나누어 떨어져야 한다. (그러한 소인수를 가져야 한다.)

하지만 A를 나눌 수 있는 소수는 리스트에 존재하지 않는다.

 

따라서 모순되므로 소수는 유한하지 않다.

 

$\begin{gather*}2\cdot3\cdot7\cdot43\cdot13+1=23479=53\cdot443 \end{gather*}$

소수들의 곱 + 1 = 소수인 것은 항상 성립하는 건 아니다.

단지 유클리드 정리에서는 모든 소수의 리스트가 존재한다고
가정한 것이므로 애초에 A는 불가능한 수.

단, 결과 합성수를 소인수 분해시 등장하는 소수는
이전에 나오지 않았던 소수이다.
ex) 우변의 53과 443은 좌변에서 나오지 않는다.

 

---

 

Dirichlet’s Theorem

There are infinitely many primes

 

$\begin{gather*}p≡3 \mod 4 \end{gather*}$

 

답이 되는 소수는 유한하지 않다.

p = 3, 7, 11, 19, 23, …

 

증명 (귀류법)

답이 되는 소수가 유한하다고 가정한다.

따라서 답이 되는 소수의 리스트를 구할 수 있다.

 

$\begin{gather*}3,p_1,p_2,...,p_r \end{gather*}$

 

이때 3은 따로 빼줘야한다!

ex) p1 = 7, p2 = 11, p3 = 19, …

 

$\begin{gather*}A:=4p_1p_2...p_r+3 \end{gather*}$

 

이때 A ≡ 3 mod 4을 만족한다.

A는 소수의 리스트에 존재하지 않기 때문에 소수가 아니다.

 

그럼 A가 합성수라면 소인수 분해가 가능하다.

 

$\begin{gather*}4p_1p_2...p_r+3=q_1q_2...q_i...q_j \end{gather*}$

 

이때 왼쪽은 홀수다. 따라서 오른쪽 q들도 왼쪽을 나눠야 하므로 q들은 모두 홀수이다.

동시에 양변이 3 mod 4를 만족해야 한다.

 

$\begin{gather*}2k+1 \equiv 1, \ \ \ 3 \mod 4 \end{gather*}$

 

홀수인 q는 mod 4를 했을 때 1 혹은 3이 나온다. (k가 짝수일 때 1, 홀수일 때 3)

근데 모든 q가 1 mod 4라면 왼쪽과 다르므로 모순.

 

즉, q들 중에 하나 이상은 적어도 3 mod 4를 만족한다.

(이때 3 mod 4가 q에 짝수개 있으면 또 1이 되므로 주의. ⇒ 홀수개 있어야 왼쪽과 합동)

 

만약 3 mod 4인 q가 3인 경우

 

$\begin{gather*}(q=3)|(4p_1p_2...p_r+3) \\ \Rightarrow 3|(4p_1p_2...p_r) \end{gather*}$

 

하지만 이것은 불가능하다. p1, …., pr에는 3이 없기 때문이다.

 

만약 q = p인 경우 (p는 3 mod 4를 만족한다.)

 

$\begin{gather*}(q=p_i)|(4p_1p_2...p_r+3) \\ \Rightarrow p_i|3 \end{gather*}$

 

이것 역시 불가능하다. p1, …, pr에는 3이 없기 때문이다.

따라서 q는 3, p1, p2, …., pr과 다른 소수.

즉, 소수의 리스트에 존재하지 않는 새로운 소수이다.

 

모순되므로 소수는 유한하지 않다.

 

---

 

일반화

$\begin{gather*}\gcd(a, m)=1 \\ p\equiv a \mod m \end{gather*}$

 

위를 만족하는 소수는 유한하지 않다.