정수론, 그 여덟 번째 이야기 | 소수

 

이 글에서 다룰 소수는 prime number 으로, 과거부터 정수론에서 많은 관심을 두고 있는 대상이다.

소수의 정의는 다음과 같다.

 

어떤 양의 정수 $p$ 에 대해, $p$ 의 양의 약수가 $1$ 과 $p$ 뿐이고, $p > 1$ 이면 $p$ 를 소수라고 한다.      이와 반대로, $1$ 보다 큰 정수 중 소수가 아닌 수를 합성수 (composite) 라고 한다.

 

위처럼 정의된 소수는 일반적인 정수를 분석하는 과정에서 여러 도움을 준다.

예를 들어, 아래와 같은 정리를 보자.

 

$p$ 가 소수이고, $p \mid ab$ 이면 $p \mid a$ 또는 $p \mid b$ 가 성립한다.

 

Proof : 

$p \mid ab$ 일 때, $p \mid a$ 이면 더 이상 증명할 것이 없다. 만약 $p \nmid a$ 라면, $p$ 의 양의 약수는 $1$ 과 $p$ 뿐이므로 $gcd \left ( p, a \right ) = 1$ 이다. 따라서, 유클리드 보조정리에 의해 $p \mid b$ 가 성립한다.

 

위의 정리를 통해 아래의 두 가지 정리를 쉽게 얻을 수 있다.

 

$p$ 가 소수이고 $p \mid a_1 a_2 \cdots a_n$ 이면 $1\leq k \leq n$ 인 어떤 정수 $k$ 에 대해 $p \mid a_k$ 이다.

 

Proof :

수학적 귀납법을 사용하자. 만약 $n = 1$ 이면 이는 지나칠 정도로 자명하다.

$n = 2$ 라면 위에서 쓴 정리 그대로이다.

 

어떤 자연수 $k$ 에 대해, $p \mid a_1 a_2 \cdots a_k$ 이면 $1 \leq b \leq k$ 인 어떤 정수 $b$ 에 대해 $p \mid a_b$ 라고 가정하자.

 

이제 $n = k + 1$ 일 때, $p \mid a_1 a_2 \cdots a_{k+1}$ 이면 위의 정리에 의해 $p \mid a_1 a_2 \cdots a_k$ 또는 $a \cdots a_{k+1}$ 인데

$p \mid a_1 a_2 \cdots a_k$ 는 앞선 가정에 의해 $1\leq b \leq k$ 인 어떤 정수 $b$ 에 대해 $p \mid a_b$ 이다.

 

따라서, 원래 명제는 수학적 귀납법에 의해 모든 정수 $n$ 에 대해 성립한다.

 

두 번째 명제는 이 정리를 이용하면 짧게 증명할 수 있다.

 

$p, q_1 ,q_2, \cdots, q_n$ 이 소수이고, $p \mid q_1 q_2 \cdots q_n$ 이면 $1 \leq k \leq n$ 인 어떤 정수 $k$ 에 대해 $p = q_k$ 이다.

 

Proof :

위의 정리에 의해 $1 \leq k \leq n$ 인 어떤 정수 $k$ 에 대해 $p \mid q_k$ 를 만족한다. 그런데 $q_k$ 는 소수이므로 $1$ 과 자기 자신을 제외한 어떤 양의 정수로도 나누어지지 않는다.

 

그런데 $p > 1$ 이므로 $p = q_k$ 이다.