Number Theory with Code - 3. Prime and Unique Factorization

Prime(소수)

An integer p is called prime if (and only if)

1. $ p \gt 1 $
2. If $ a \;|\; p $, then $a=\pm 1$ or $\pm p$.

귀찮으니 양수로 한정해서 이야기하자. 소수가 아닌 수를 합성수라고 하는데, 1 과 자기자신 외의 양의 약수를 가진다는 말이 된다.

소수(prime) 그 자체를 소수의 곱으로 인정한다면, 경험상 1 보다 큰 자연수는 소수의 곱이었다. 그런데, 정작 이를 증명하라면 막막하다. 다음의 보조 정리의 증명에 '정렬성(Well-Ordering)'을 써보자.

임의의 2 이상인 자연수 $n$은 소수의 곱으로 표현된다.

소수의 곱으로 표현할 수 없는 자연수의 집합을 $X$ 라 하자. 만약 공집합이 아니라면 정렬성에 의해 최소원 $ n (\gt 2)$ 이 존재한다. $n$ 이 소수이면 소수의 곱이라 했으므로 $n$은 합성수여야 한다.

$$ \exists a,b \in \mathbb{P}, \; n=ab $$

여기서 $a,b$ 는 $n$ 보다 작으니, $X$ 의 원소가 아니다. 따라서 이들은 각각 소수의 곱으로 표현되고 둘의 곱인 $n$ 도 역시 그렇다.

이는 $n \not\in X$ 이므로 모순이 발생한다. 결국 $X$ 가 공집합이어야 모순을 피할 수 있다.

이제 $n$이 소수인지 아닌지를 알고 싶은 상황이라고 생각하자. 2부터 시작해서 3,4,$\cdots$ 차례로 $n$ 을 나눈 나머지가 0인지를 확인해야 할 것이다.

언제까지? $\sqrt{n}$ 까지 조사하면 충분하다!

정수 $a$ 가 $n$ 의 약수이면 어떤 정수 $b$ 가 존재해서 $ab=n$ 을 만족한다는 것인데, 이 식을 관찰하면 합성수 $n$ 의 1이 아닌 약수 중에는 $\sqrt{n}$ 이하인 것이 존재함을 알게 된다. $$ n=ab \ge a^2 \Rightarrow \sqrt{n} \ge a$$

하여간 정렬성을 적용한 이후에는 말장난에 불과한 위의 증명은, 무한 집합에서 가능성 증명을 존재 증명으로 바꾸어 공리를 쓰는 연습으로서는 중요해 보인다.

Euclid's Lemma

$p$를 소수라 하자. 그러면 $$ p\;|\; ab \Rightarrow p\;|\;a \;\mbox{or} \; p\;|\;b $$

소스의 정의로부터 $\gcd(p,a)=1 \;\;\mbox{또는}\;\; p$ 이다.

$\gcd(p,a)=1$ 이면 $p\;|\;a$ 이므로 증명은 끝난다.

$\gcd(p,a)=1$ 이면 최대공약수를 일차결합 $px+ay=1$ 로 표현하고 양변에 $b$를 곱하면

$$ pbx+aby=b $$ 등식 좌변의 각 항이 $p$ 의 배수이므로 $p|b$ 이어야 한다.

이 증명은 앞서 공부한 $$\gcd(a,b)=1 \;\mbox{and}\; a|bc \Longrightarrow a|c$$ 와 같으나 한 번 더 써봤다.

정수론을 정리하면서 어지간하면 자명한 것도 증명을 쓰고 있다. 하지만 다음 정리는 그냥 넘어가자.

Unique Factorization(인수분해의 유일성)

Let $n\gt 1$ be an integer. Then $$ n=p_1p_2 \cdots p_k $$ is a product of primes and this factorization is unique.

증명은 생략한다.

$n$ 이 자연수일 때, $\tau (n)$ 은 $n$ 의 양의 약수의 개수, $\sigma(n)$ 은 $n$ 의 양의 약수의 합으로 약속하자. $ n$ 의 소인수분해가 $$ n=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} $$ 이라 하자. $n$ 의 양의 약수의 개수는 $$\tau(n)=(1+e_1)(1+e_2)\cdots(1+e_k)$$ 이고 약수의 합은 $$\sigma(n)=\frac{p_1^{e_1+1}-1}{p_1-1} \frac{p_2^{e_2+1}-1}{p_2-1} \cdots \frac{p_k^{e_k+1}-1}{p_k-1} $$ 이다. (중고교 과정에서 배웠을 것이다.)

최대공약수와 최소공배수를 소인수분해로부터 구해보자. $$a=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} ,\;\; b=p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k} $$ 라 하자. (지수가 0인 것을 허용하여 두 수가 같은 소인수를 가진 것처럼 표현한 것이다.) 예를 들어 $12, 15$ 는 $$ 12=2^2 3^1 5^0 , \;\; 15=2^0 3^1 5^1 $$ 로 표현하면 된다.

최대공약수는 $$\gcd(a,b) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \cdots p_k^{\min(e_k, k_1)} $$ 일 것이고 최소공배수는 $$\gcd(a,b) = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \cdots p_k^{\max(e_k, k_1)} $$ 일 것이다.

---

다음 증명은 상당히 충격적(?)이다.

Euclid !!!

소수는 무한히 많다.

이 명제의 증명들 중 여기서는 두 개를 다룰 것이다. 두 증명 모두 과정이 다른 유용한 결과들을 생산하기 때문에 반드시 익혀두자.

proof1 proof2

만약 소수가 유한개라면 $p_1=2, p_2=3, \cdots p_k $ 로 모두 열거할 수 있다. 이들을 모두 곱하고 1을 더한 수를 생각한다.

$$ n=p_1p_2 \cdots p_k +1 $$

$n$이 소수라면 $n \gt p_i , i\in \{1,2,\cdots,k \}$ 이므로, $p_1=2, p_2=3, \cdots p_k $ 이외의 새로운 소수가 되어 모순이 발생한다.

$n$이 소수가 아니면 소인수분해가 되어야 하므로, 어떤 소수 $p$가 존재해서 $ p \;|\; n$ 이어야 한다. 즉, $p$ 는 $p_1, p_2, \cdots p_k $ 중 하나여야 한다. $$ p | n \Leftrightarrow p \;|\; p_1p_2\cdots p_k+1 \Rightarrow p\;|\;1$$ (마지막 부분은 $1=n - p_1p_2\cdots p_k$ 에서 1이 $p$ 의 배수의 일차결합이기 때문) 그런데 이건 곤란하다.

만약 소수의 역수들의 합 $$1+\frac1{2} + \frac1{3} +\frac1{5}+\frac1{7} + \frac1{13} +\cdots $$ 이 발산한다면 우리는 자신있게 소수가 무한하다고 말할 수 있을 것이다.

예상 가능하게 조화급수가 등장한다. 조화급수 $$ 1+\frac1{2}+\frac1{3}+\cdots+\frac1{n} $$ 이 발산함은 적분과 비교하여 발산함을 알 수 있다. $$ \int_1^{n+1} \frac1{x} dx \lt 1+\frac1{2}+\frac1{3}+\cdots+\frac1{n} $$

$n$ 이하의 모든 소수들을 $p_1, p_2, \cdots, p_k$라 하자. $$ 1+\frac1{2}+\cdots+\frac1{n} \lt \left(1+\frac1{2}+\frac1{2^2}+\cdots+\right) \cdots \left(1+\frac1{p_k}+\frac1{p_k^2}+\cdots\right) $$ 이 식의 우변의 각 항은 소수들의 거듭제곱들의 역수의 합이다. 식은 번거롭지만 좌변 각 항을 소인수분해해보면 이해가 될 것이다.

우변의 곱해진 각 항이 무한 등비 급수이므로 정리하면 $$ R.H.S = \left(\frac1{1-\frac1{p_1}} \right) \left(\frac1{1-\frac1{p_2}} \right) \cdots \left(\frac1{1-\frac1{p_k}} \right) $$ 혹은 분모, 분자에 $p_i$ 를 곱해서 $$ R.H.S = \left(\frac{p_1}{p_1-1} \right) \left( \frac{p_2}{p_2-1} \right) \cdots \left( \frac{p_k}{p_k-1} \right) $$ 를 얻는다.

$\ln{\frac{p}{p-1}} \lt \frac2{p} $임은 넓이 비교로 얻을 수 있고 위에서 얻은 식들에 $\ln$을 취하면 $$ \ln \left(1+\frac1{2}+\cdots+\frac1{n}\right) \lt \ln\left(R.H.S\right) \lt 2 \sum_{p\le n} \frac1{p} $$

조화급수가 발산하면 $\ln$을 취해도 발산할 것이다. 따라서 소수의 역수들의 합이 발산함이 증명되었다.

위 정리의 첫 증명의 응용을 보자.

$n$ 번째 소수를 $p_n$ 이라 하자. ($p_1=2, p_2=3, \cdots$ 이다.) $$p_n \le 2^{2^{n-1}} $$ 이 성립한다.

$2=p_1 \le 2^{2^0} $ 이 성립한다.

위 증명을 보면 $p_1p_2 \cdots p_n +1 $ 의 소인수는 $p_1, p_2, \cdots p_k $ 중에는 없으니 $$ p_{n+1} \lt p_1p_2 \cdots p_n +1 $$ 임을 알 수 있다.

이제 귀납 가정을 적용하여 부등식을 정리하면 $$ p_{n+1} \le 2^{2^0} \cdot 2^{2^1} \cdot \cdots \cdot 2^{2^{n-1}} +1= 2^{2^n-1} +1 \le 2^{2^n}$$

연습이 필요하다.