[Discrete Mathematics] 약수(divisor)와 소수(prime) 그리고 최대공약수와 최소공배수

---

약수 (Divisor)

 

정수 $ n $ 과 $ d $ 가 $ d \neq 0 $ 일 때, $ n = dq $ 를 만족하는 정수 $ q $ 가 존재하면 $ d $ 가 $ n $ 을 나눈다(divide)고 정의한다. 이때 $ q $ 를 몫(quotient), $ d $ 를 $ n $ 의 약수 또는 인수(factor)라 한다. 만약 $ d $ 가 $ n $ 을 나누면 $ d \mid n $ 으로 표기하고, 나누지 못한다면 $ d \nmid n $ 으로 표기한다.

양의 정수 $ n $ 과 $ d $ 가 $ d \mid n $ 이면 $ d \leq n $ 이다. 왜냐하면 $ d \mid n $ 이면 $ n = dq $ 인 양의 정수 $ q $ 가 존재하며 따라서 $ d \leq dq = n $ 이기 때문이다.

몫-나머지 정리에 의해 양의 정수 $ d $ 가 정수 $ n $ 을 나눌 수 있든 없든 유일한 몫 $ q $ 와 나머지 $ r $ 을 얻을 수 있다. 즉 $ n = dq + r $ $ (0 \leq r < d) $ 를 만족하는 $ q $ 와 $ r $ 이 유일하게 존재한다. 나머지 $ r $ 이 $ 0 $ 이 될 필요충분조건은 "$ d $ 가 $ n $ 을 나눌 수 있다" 이다.

이러한 정리를 바탕으로 정수 $ m $, $ n $, $ d $ 가 존재할 때 $ d \mid m \land d \mid n \to d \mid (m + n) $ 와 $ d \mid m \land d \mid n \to d \mid (m - n) $, 그리고 $ d \mid m \land d \mid n \to d \mid mn $ 이 성립한다.

 

---

소수 (Prime)

 

• 소수

$ 1 $ 보다 큰 정수가 $ 1 $ 과 자신만을 양의 약수로 가진다면 소수라 한다. $ 1 $ 보다 큰 정수 중 소수가 아닌 수를 합성수(composite)라 한다.

앞서 약수의 정의를 바탕으로 $ 1 $ 보다 큰 정수 $ n $ 이 합성수일 필요충분조건은 $ 2 \leq d \leq \sqrt{n} $ 인 $ d $ 를 약수로 가지는 것이다. 어떤 수 $ n $ 을 정수의 곱으로 나타낸다면 $ pq = n $ 으로 나타낼 수 있을텐데, $ p $ 와 $ q $ 중 하나만이라도 $ 1 $ 이나 $ n $ 이 아니라면 합성수이므로 $ \sqrt{n} $ 까지만 확인하면 된다.

$ n $ 이 합성수라 가정하면 $ n $ 은 $ 2 \leq d^\prime \leq n $ 인 양의 정수 $ d^\prime $ 를 약수로 가진다. 만약 $ d^\prime \leq \sqrt{n} $ 이면 $ n $ 은 $ 2 \leq d \leq \sqrt{n} $ 인 $ d $ 를 약수로 가진다. 다른 경우인 $ d^\prime > \sqrt{n} $ 을 본다면 $ d^\prime $ 이 $ n $ 을 나눠야 하므로 $ n = d^\prime q $ 인 정수 $ q $ 가 존재하고 역시 $ n $ 의 약수이다.

$ q \leq \sqrt{n} $ 여야 함을 증명하기 위해 $ q > \sqrt{n} $ 이라 가정하면 $ d^\prime > \sqrt{n} $ 과 $ q > \sqrt{n} $ 의 곱은 $ n = d^\prime q > \sqrt{n} \sqrt{n} = n $ 이므로 모순이 발생하는 것을 확인할 수 있고, 따라서 $ q \leq \sqrt{n} $ 이다.

그러므로 $ 2 \leq d \leq \sqrt{n} $ 인 $ d $ 를 약수로 가진다.

합성수의 정의를 역으로 이용하여 만약 $ 2 \leq d \leq \sqrt{n} $ 인 양의 정수 $ d $ 로 나눠지면 소수가 아니라 할 수 있다. 따라서 다음과 같이 소수를 검사할 수 있다. 이 알고리즘은 합성수라면 소수인 약수를, 약수라면 0 을 반환한다.

is_prime(n) {
    for d = 2 to floor(sqrt(n)) {
        if (n mod d == 0) {
            return d
        }
    }
    return 0
}

또한 $ \sqrt{n} $ 까지 반복하기 때문에 이 알고리즘의 시간복잡도는 최악의 경우 $ \varTheta (\sqrt{n}) $ 이다.

 

• 소인수 (Prime Factor)

만약 $ 1 $ 보다 큰 정수가 있다면 이 정수는 소수의 곱으로 나타낼 수 있다. 이때의 소수를 소인수라 한다. 소인수들을 비감소 순서로 나열한다면, 이 인수분해는 유일하다. 이를 산술의 기본 정리 또는 인수분해 유일성 정리라 한다. 이 때문에 위 소수 검사 알고리즘에서 처음 만난 $ d $ 를 반환했을 때 $ d $ 가 소수이다.

 

• 소수의 무한성

또한 소수는 무한히 많다. 즉 어떤 수 $ p $ 가 소수이면 $ p $ 보다 큰 소수가 있다. 증명하기 위해 $ p_1, p_2, \dots , p_n $ 을 $ p $ 이하인 서로 다른 모든 소수라 할 때 $ m = p_1 p_2 \cdots p_n + 1 $ 을 가정하자. 만약 어떤 $ j $ 에 대해 $ p_j \mid m $ 이라 가정하면, $ p_j \mid p_1 p_2 \cdots p_n $ 이므로 $ p_j \mid m - p_1 p_2 \cdots p_n = 1 $ 이다. 그런데 $ p_j $ 는 소수이므로 $ p_j \geq 2 $ 이고 따라서 앞선 정의에 따라 $ p_j \nmid 1 $ 이므로 모순이고, 따라서 $ i = 1, \dots, n $ 에 대하여 $ p_i \nmid m $ 이다.

$ p^\prime $ 을 $ m $ 의 소인수라 하면 $ p^\prime \neq p_i (i = 1, \dots, n) $ 이고, $ p_1, p_2, \dots, p_n $ 은 $ p $ 이하인 모든 소수이므로 $ p^\prime > p $ 이어야 한다.

 

---

최대공약수와 최소공배수

 

정수 $ m $ 과 $ n $ 중 하나는 $ 0 $ 이 아니라 할 때, $ m $ 과 $ n $ 의 공약수(common divisor)는 $ m $ 과 $ n $ 을 나누는 정수이며, 최대공약수는 그 중 가장 큰 공약수이다. $ \gcd(m, n) $ 으로 표기한다.

$ 1 $ 보다 큰 정수 $ m $ 과 $ n $ 에 대한 소인수분해를 $ m = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} $ 이고 $ n = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} $ 이라 하면 $ \gcd(m, n) = p_1^{\min(a_1, b_1)} p_2^{\min(a_2, b_2)} \cdots p_k^{\min(a_k, b_k)} $ 이다.

$ g = \gcd(m, n) $ 이라 할 때 $ g $ 의 소인수분해에 소수 $ p $ 가 포함되었다고 하면 $p $ 는 $ p_1, \dots, p_k $ 중 하나여야 한다. 만약 아니라면 $ g $ 는 $ m $ 또는 $ n $ 으로 나누지 못하기 때문이다.

그러므로 $ c_1, \dots , c_k $ 에 대하여 $ g = p_1^{c_1} \cdots p_k^{c_k} $ 이다.

따라서 $ p_1^{\min(a_1, b_1)} p_2^{\min(a_2, b_2)} \cdots p_k^{\min(a_k, b_k)} $ 는 $ m $ 과 $ n $ 을 모두 나눈다. 그러나 위 지수 $ \min(a_i, b_i) $ 중 하나라도 증가한다면 이 수는 $ m $ 이나 $ n $ 을 나누지 못할 것이고, 즉 더 큰 공약수가 없기에 $ m $ 과 $ n $ 의 최대공약수이다.

양의 정수 $ m $ 과 $ n $ 을 가정할 때 $ m $ 과 $ n $ 으로 모두 나눌 수 있는 정수를 $ m $ 과 $ n $ 의 공배수(common multiple)라 한다. 최소공배수는 그 중 가장 작은 공배수이다. $ \operatorname{lcm}(m, n) $ 으로 표기한다.

$ 1 $ 보다 큰 정수 $ m $ 과 $ n $ 에 대한 소인수분해를 $ m = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} $ 이고 $ n = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} $ 이라 하면 $ \operatorname{lcm}(m, n) = p_1^{\max(a_1, b_1)} p_2^{\max(a_2, b_2)} \cdots p_k^{\max(a_k, b_k)} $ 이다.

$ l = \gcd(m, n) $ 이라 할 때 $ l $ 의 소인수분해에 소수 $ p $ 가 포함되었다고 하면 $p $ 는 $ p_1, \dots, p_k $ 중 하나여야 한다. 만약 아니라면 $ l $ 을 소거하고도 $ m $ 또는 $ n $ 으로 나눌 수 있기 때문이다.

그러므로 $ c_1, \dots , c_k $ 에 대하여 $ l = p_1^{c_1} \cdots p_k^{c_k} $ 이다.

따라서 $ p_1^{\max(a_1, b_1)} p_2^{\max(a_2, b_2)} \cdots p_k^{\max(a_k, b_k)} $ 는 $ m $ 과 $ n $ 에 의해 나누어진다. 그러나 위 지수 $ \max(a_i, b_i) $ 중 하나라도 감소한다면 이 수는 $ m $ 이나 $ n $ 으로 나누어지지 못할 것이고, 즉 더 작은 공배수가 없기에 $ m $ 과 $ n $ 의 최소공배수이다..

위 정리들을 활용하면 $ 1 $ 보다 큰 양의 정수 $ m $ 과 $ n $ 에 대하여 다음이 성립함을 나타낼 수 있다.

$$ \gcd(m, n) \cdot \operatorname{lcm}(m, n) = mn $$