[친절한 수론 길라잡이] 7장. 인수분해와 산술의 기본정리

2 이상의 정수 p의 약수가 1과 p 뿐일 때, p를 소수(prime number)라고 부른다.

2 이상의 소수가 아닌 수를 합성수(composite number)라고 부른다.

 

소수 p가 곱 ab를 나눈다고 가정하자. 그러면 p는 a를 나누거나, b를 나눈다.
(또는 a와 b 모두 나눈다.)

 

증명)

 

p가 곱 ab를 나눈다고 하자. 만일 p가 a를 나눈다면 증명이 끝나므로, 나누지 않는다고 가정하면,

gcd(p, a)가 어떤 수인지 생각해야 한다.

이 수는 p를 나누므로, 1 또는 p이다.

p가 a를 나누지 않으므로, p는 1이다.

 

6장의 정리를 이용하여, px + ay = 1에서 양변에 b를 곱한다.

pbx + aby = b

pbx는 p로 나누어지고, p가 ab를 나누므로, aby 역시 p로 나누어진다.

두 수의 합 pbx + aby도 p로 나누어진다. (a+b=p⋅m+p⋅n=p⋅(m+n))

 

따라서 p는 b를 나눈다.

 

소수 p가 곱  를 나눈다고 해보자. 그러면 p는 인수 중 최소한 하나를 나눈다.

 

증명)

만일 p가 a1을 나눈다면, 원하는 결론을 얻는다. 만일 p가 a1을 나누지 않는다면, 위의 보조정리를 다음 곱

에 적용하면, p가 a1과 곱해진 부분을 나누어야 한다.

윗의 증명에 따르면,

a = a1, b = a2*a3*...*ar인 셈이다.

b는 그렇다면 반드시 p에 의해 나누어져야 한다.

 

만일 p가 a2를 나눈다면, 원하는 결론을 얻는다.

아니라면, 위 과정을 r-1번 더 반복하여 결국 p가 나누는 a_i를 찾을 수 있다.

 

짝수의 세계

아래에는 소수의 가약성을 이용하여 모든 자연수는 소수들의 곱으로 표현되고 그 방법은 유일하다는 사실을 증명할 것이다.

하지만 이전에, 여러분들이 당연하게도 느끼던 것을 왜 증명해야 할지 이해를 돕기 위해 짝수의 세계부터 갔다와보자.

 

적당한 (짝)수 k에 대해 n = mk를 만족하면, m은 n의 짝약수라고 불린다.

예시: (6, 12)에서 6은 12의 짝약수이다 (12 = 2 * 6). 단, (6, 18)에서 6은 18의 짝약수가 아니다. 모든 수가 짝수인 세계이기 떄문이다.

 

소수도 정의할 수 있다.

어떤 수 p가 어떤 (짝)수에 대해서도 나누어지지 않으면 짝소수라고 불린다.

{2, 6, 10, 14, 18, 22, 26, 30 ... }

 

일반적인 정수에서 맞던 위 정의가 짝수의 세계에서는 어떨까?

짝소수 6과 a = 10, b = 18에 대해서 살펴보자. 6은 ab = 180의 짝약수가 맞다. 하지만, 6은 10에 대해서도, 18에 대해서도 짝약수가 아니다.

 

소인수분해도 상식의 세계에서는 매우 자명해 보이지만, 짝수의 세계에서는 통하지 않는다.

정상적인 세계에서 모든 수는 소수의 곱으로 표현된다고 하지만...

짝수의 세계에서는?

180 = 6 * 30 = 10 * 18 = 2 * 90

두 가지 이상의 방법의 짝소인수분해를 가진다.

 

이를 통해서, 우리는 늘 당연하게 여겨 오던 명제들에 대해서도 다시 한번 생각해볼 필요가 있다는 것을 배워야 한다.

 

==짝수의 세계 끝

---

2보다 크거나 같은 모든 정수 n은 소수들의 곱 으로 표현되며, 그 표현은 유일하다.

1. n 자신이 소수이면, 간단히 n = n이라고 표현하고 n은 하나의 수 곱으로 표현되는 것으로 간주한다.
2. n = p1p2...pr로 표현할 때, 각각의 p_i들이 서로 다른 소수를 의미하지 않는다.
3. n이 소수들의 곱으로 유일하게 표현된다고 할 때는 소수의 곱하는 순서를 재배열하는 것은 고려하지 않는다.

 

증명)

위 정리(산술의 기본정리)는 두 가지 주장을 내포하고 있다.

1. 정수 n은 소수의 곱으로 표현할 수 있다.
2. 곱하는 소수를 재배열하는 방법을 제외하면 그 방법을 유일하다.

 

주장 1을 귀납적으로 증명해보자.

2 = 2, 3 = 3, 4 = 2^2

n = 2,3,4에 대해 주장 1이 성립한다.

이제, 주장 1이 N보다 작거나 같은 모든 양의 정수 n에 대해 성립한다고 해보자.

즉, n <= N을 만족하는 양의 정수 n은 소수들의 곱으로 효현할 수 있다고 가정하자.

그리고, 이 주장이 N+1에 대해서도 성립함을 증명해보자.

 

두 가지 가능성이 있다. 우선, N+1이 소수라면, N+1은 이미 소수의 곱으로 표현되어 있다.

다음은 N+1이 합성수, 즉 2 <= n_1, n_2 <= N을 만족하면서 N+1 = n1n2와 같이 인수분해될 때이다.

n1, n2는 N보다 작거나 같으므로, 가정에 의해 주장 1이 n1, n2에 대해 성립한다.

n1, n2는 n1 = p1p2...pr, n2 = q1q2...qs와 같이 소수들의 곱으로 표현된다.

이 두 곱을 곱하면, N+1 = p1p2...prq1q2...qs와 같이 표현된다.

따라서, N+1도 역시 소수의 곱으로 표현된다.

 

 

이번엔 주장 2를 증명해보자. 

n이 두 가지 방법의 소수의 곱으로 표현되었다고 가정하자. 즉, n=p1p2p3p4...pr = q1q2q3q4...qs

라 하자.

먼저, p1|n이고, 따라서 p1 = q1q2q3...qs이다.

이번 장 앞 부분 가약성에 의해, p1은 적어도 하나의 qi를 나누어야 한다.

편의상 q_i들을 재배열하여 q1이라 하자. q1도 소수이므로, p1 = q1이여야 한다. p1 = q1으로 양변을 나누면,

n/p1 = p2p3p4...pr = q2q3q4...qs이다.

 

이제 위 과정을 계속 반복하면, p1 = q1, p2 = q2, ... ,pr = qs이다.

따라서, n을 소수의 곱으로 표현하는 방법은 오직 한 가지의 방법 뿐이다.

산술의 기본정리는 n >= 2인 모든 정수는 소수의 곱으로 표현됨을 알려준다.

== 증명 끝==

 

만일 n이 소수가 아니라면, p <= sqrt(n)을 만족하는 소수 중 하나가 n의 약수가 되어야만 한다.

증명)

p가 n을 나누는 가장 작은 소수라 하면, n = mp이고, m >= p이므로, n = mp >= p^2이 성립한다.

 

이 결과로부터 누구라도 임의의 자연수를 소인수분해할 수 있는 쉬운 방법을 찾을 수 있다.

그래서, 만일 큰 소수로 소인수분해를 하려면, sqrt(n)보다 작거나 같은 소수들로 n을 나눠보면 된다.

그러한 소수가 없다면, n은 소수이고, 소수를 찾았다면, 가장 작은 p를 잡아 n = pm인 몫 m을 찾고 이 방법을 m에 다시 적용하는 과정을 반복한다.

 

효율적이지는 않아보이지만, 컴퓨터에서 10자리 자연수의 소인수분해를 할 정도는 된다.

n = 10^128+1과 같은 큰 수는? 초당 10억번이 연산 속도로도 3 * 10^48년의 시간이 걸린다.

 

만약 큰 수가 합성수라면, 어떻게 소인수분해를 계산할 수 있을까?

두 개의 큰 소수 p와 q를 찾아 이들을 곱하면, 이렇게 만들어진 수 n = pq는 소인수분해가 거의 불가능하다. 두 수를 곱하는 건 쉽지만, 소인수분해는 어렵다.

이는 안전한 암호를 만들 때의 가장 핵심적인 부분이다.