The Prime Number
Definition 1. An integer $p > 1$ is called a prime number (or prime) if its only positive divisors are 1 and $p$.
An integer greater than 1 that is not a prime is called a composite.
양의 약수로 1과 자기 자신 밖에 가지지 않는 수를 소수라고 하고, 그렇지 않은 수를 합성수라 한다. 나눗셈이라는 연산의 관점에서 볼 때 더이상 쪼개지지 않는, 마치 원자와 동일한 역할을 수행하는 대상이다. 소인수분해라는 개념이 괜히 있는 것이 아니다. 정수들을 이루는 벽돌과도 같은 기본 단위가 소수이기 때문에 소수를 기준으로 정수를 분해하는 것이다.
Theorem 1
Theorem 1. If $p$ is a prime and $p \,|\, ab$, then $p \,|\, a$ or $p \,|\, b$.
Proof. Suppose that $p \nmid a$ and $p \nmid b$. Let $ab = kp$ for some $k \in \mathbb{Z}$. Note that $\gcd(b, p) = 1$. Then by Theorem 3, $1 = bx + py$ for some $x, y \in \mathbb{Z}$. Hence we have $$ab = kp \Longrightarrow abx = a(1 - py) = kpx \\ \Longrightarrow a = apy + kpx = (ay + kx)p.$$ Then $p \,|\, a \bigotimes$. Thus $p \,|\, a$ or $p \,|\, b$. $\blacksquare$
소수 $p$가 $ab$를 나눈다면 $a, b$ 둘 중 하나는 반드시 $p$를 기본 단위, 즉 소인수로서 가지고 있다는 것이다. $n$개의 정수로 확장하면 다음과 같다.
Corollary 1
Corollary 1. If $p$ is a prime and $p \,|\, a_1 \cdots a_n$, then $p \,|\, a_k$ for some $k$, where $1 \leq k \leq n$.
Proof. Suppose that $p \nmid a_k, \forall k \in \{1, ..., n\}$. Then $\gcd(a_k, p) = 1, \forall k \in \{1, ..., n\}$. Let $a_1x + py = 1$ for some $x, y \in \mathbb{Z}$, and let $a_1 \cdots a_n = tp$ for some $t \in \mathbb{Z}$. Then we have $$(a_1x)a_2 \cdots a_n = (1 - py)a_2 \cdots a_n = tpx \\ \Longrightarrow a_2 \cdots a_n = (a2 \cdots a_ny + tx)p \Longrightarrow p \,|\, a_2 \cdots a_n.$$ By repeating this process, we have $p \,|\, a_{n-1}a_n$. Thus by Theorem 1, $p \,|\, a_{n-1}$ or $p \,|\, a_n$ $\bigotimes$. Hence $p \,|\, a_k$ for some $k$, where $1 \leq k \leq n$. $\blacksquare$
Corollary 2
Corollary 2. If $p, q_1, ..., q_n$ are all primes and $p \,|\, q_1 \cdots q_n$, then $p = q_k$ for some $k$, where $1 \leq k \leq n$.
Proof. By corollary 1, $p \,|\, q_k$ for some $k$, where $1 \leq k \leq n$. By definition of a prime, it is clear that $p = q_k$. $\blacksquare$