이산수학 | 소수, GCD

DN_07, p.32

소수 (Prime)

정의 : 1보다 크고 1과 자기 자신 외에 positive factors가 없는 정수 $p$를 소수라고 부른다

정리 : 1보다 큰 모든 양의 정수는, 소수이거나, 오름차순 정렬된 두 개 이상의 소수의 곱으로 쓸 수 있다

예시

• $100 = 2 \cdot 2 \cdot 5 \cdot 5 = 2^2 \cdot 5^2$
• $641 = 641$ (소수)
• $999 = 3 \cdot 3 \cdot 3 \cdot 37 = 3^3 \cdot 37$

에라스토스테네스의 체

소수를 간단하고 빠르게 찾는 방법

1. 2를 제외하고 2로 나눌 수 있는 모든 수를 제거
2. 3를 제외하고 3로 나눌 수 있는 모든 수를 제거
3. 오름차순으로 남은 수에 대해 동일하게 반복한다
4. 1을 제외하고 남은 수가 소수이다

소수의 무한대

정의 : 소수는 무한하다

증명(proof)

소수가 유한하다고 가정하고 다음 집합을 소수의 집합이라 하자 : $P = \set{p_1, p_2, \cdots p_n}$

그럼 $p_1 \cdot p_2 \cdot … \cdot p_n + 1$은 어떤 소수로도 나누어지지 않으므로 소수이다

하지만 소수의 집합 $P$에 들어있지 않는다. 따라서 처음 가정과 대치되므로 소수는 무한하다

함수 표현

정의 : $p$가 소수고 $2^p-1$ 형식의 소수를 메르센 소수(Mersenne Prime)이라고 한다

아래 메르센 소수의 예시이다

• $2^2-1 = 3$
• $2^3-1 = 7$
• $2^5-1 = 31$
• $2^7-1 = 127$

그러나 $2^{11}-1 = 2047 = 23 \cdot 89$는 소수가 아니다

소수 분포

소수 정리 : 무작위로 선택된 $n$보다 작은 양의 정수가 소수일 확률은 다음과 같다

\[\frac{x}{\ln x}\]

소수 생성

수백 자리의 큰 소수를 찾는 것은 암호학에서 큰 관심사이다

그러나 소수를 항상 생성하는 유용한 함수는 발견되지 않았다

양의 정수 $n$에 대해 $f(n)$이 소수가 되도록 하는 간단함 함수 $f(n)$은 존재하지 않는다

소수에 대한 추측

WIP

DN_07, p.43

최대 공약수 (Greatest Common Divisor)

정의 : $a, b$는 모두 0이 아닌 큰 정수라고 하자. $d \mid a$이면서 $d \mid b$가 되는 가장 큰 정수를 $a$와 $b$의 최대 공약수라고 한다. 이를 $\gcd(a,b)$로 표시한다

• $\gcd(24, 36) = 12$
• $\gcd(17, 22) = 1$

정의 : $a$, $b$의 gcd가 1이라면, 그 둘을 relatively prime(서로소)라고 한다

*예시: * 17과 22

정의 : $a_1, a_2, \cdots, a_n$이며 $\gcd(a_i, a_j), 1 \le i \le j \le n$이라면, 이를 pairewise relatively prime라고 한다

*예시: * 10, 17, 21은 각각 gcd가 1이므로 pairewise relatively prime이다

소인수 분해를 이용한 최대 공약수 찾기

$a, b$을 0이 아닌 정수라고 가정하면 다음과 같이 표현할 수 있다

\[a = p_1^{a_1} \cdot p_2^{a_2} \cdots p_n^{a_n}\] \[b = p_1^{b_1} \cdot p_2^{b_2} \cdots p_n^{b_n}\]

각 지수는 음수가 아닌 정수이며, $p_i$는 소수이다

그럼 gcd를 다음과 같이 표현할 수 있다

$\gcd(a,b) = p_1^{\min(a_1,b_1)} \cdot p_2^{\min(a_2,b_2)} \cdots p_n^{\min(a_n,b_n)}$

예시

$120 = 2^3 \cdot 3 \cdot 5$이고 $500 = 2^2 \cdot 5^3$이다

따라서 최대공약수는 $2^2 \cdot 3^0 \cdot 5 = 20$ 이다

최소공배수 (Least Common Multiple)

정의 : $a$와 $b$로 나눌 수 있는 가장 작은 양의 정수를 최소공배수라고 하고 $\text{lcm}(a,b)$로 표시한다

최소공배수는 다음과 같이 나타낼 수 있다

\[\text{lcm}(a,b) = p_1^{\max(a_1,b_1)} \cdot p_2^{\max(a_2,b_2)} \cdots p_n^{\max(a_n,b_n)}\]

이 값은 $a$와 $b$로 나눠지며, $a$와 $b$로 나눠지는 더 작은 수는 존재하지 않는다

정리 : $a, b$가 양의 정수라면, 다음과 같이 정리할 수 있다

\[a \cdot b = \gcd(a, b) \cdot \text{lcm}(a, b)\]

유클리드 알고리즘

효과적으로 gcd를 구하는 방법

예시

Find $ \gcd(91, 287) $

• $287 = 91 \cdot 3 + 14$
• $91 = 14 \cdot 6 + 7$
• $14 = 7 \cdot 2 + 0$

$\gcd(287, 91) = \gcd(91, 14) = \gcd(14, 7) = 7$

유클리드 알고리즘의 정확성

Lemma(보조정리) : $a, b, q, r$을 정수라 하고 $a = bq + r$라고 하자.

그러면 $\gcd(a,b) = \gcd(b,r)$ 이다

WIP. DN_07. p.51

$a \ge b$인 양의 정수 $a, b$가 있다고 하고 $r_{-1} = a, r_0 = b$라고 하자

그럼 다음과 같다

\[r_{i-2} = q_ir_{i-1} + r_i\]

이 때, $a = r_{-1} > r_0 > r_1 > \cdots > r_k = 0$ 이다

Lemma 1에 따라 다음이 성립한다

\[\gcd(r_{-1}, r_0) = \gcd(r_0, r_1) = \gcd(r_1, r_2) = \cdots\]

따라서 최대공약수는 나눗셈 시퀀스에서 0이 아닌 마지막 나머지 부분이다

확장 유클리드 알고리즘 (Extended Euclidean algorithm)

베주 항등식 (BÉZOUT’S IDENTITY)

베주의 정리 : $a,b$가 양의 정수라면, $\gcd(a, b) = sa + tb$가 되는 정수 $s, t$가 존재한다

정의 : $a, b$가 양의 정수인 경우 $\gcd(a,b) = as + bt$ 가 되게 하는 정수 $s, t$를 $a, b$의 베조트 계수(Bézout coefficients)라고 한다

$\gcd(a,b) = as + bt$ 방정식을 베주의 동일성이라고 한다

예시

• $\gcd(6,14) = (-2) \cdot 6 + (1) \cdot 14$

예시

$gcd(252, 198) = 18$ 을 252을 198의 linear combination으로 표현하라

풀이

1. $252 = 192 \cdot 1 + 54$
2. $192 = 54 \cdot 3 + 36$
3. $54 = 36 \cdot 1 + 18$
4. $36 = 18 \cdot 2 + 0$

이제 backwards로 수행한다

• $18 = 54 - 1 \cdot 36$
• $36 = 198 - 3 \cdot 54$

이제 방정식을 대입한다

• $18 = 54 - 1 \cdot (198 - 3 \cdot 54) = 4 \cdot 54 - 1 \cdot 198$

다음 $54 = 252 - 1 \cdot 198$ 방정식을 대입한다

• $18 = 4 \cdot (252 - 198) - 1 \cdot 198 = 4 \cdot 252 - 5 \cdot 198$

위 방법은 two-pass 방식이다. 먼저 유클리드 알고리즘을 사용해 gcd를 찾은 다음 역으로 작업해 gcd를 원래 두 정수의 선형 조합으로 표현한다

베주 정리의 결과

Lemma 2 (중간정리) : 양의 정수 $a, b, c$가 있고 $gcd(a,b) = 1$이면서 $a \mid bc$라면, $a \mid c$이다.

증명 : WIP_DN_07_P55

Lemma 3 (중간정리) : $p$가 소수이고, $p_1 \mid a_1a_2a_3 \cdots a_n$ 라면, 임의의 $i$에 대해 $p \mid a_i$이다

다음 정리는 소인수분해의 고유성을 증명하는데 매우 중요하다

소인수분배의 고유성

양의 정수에 대한 소인수분해가 고유하다는 것을 증명한다 (소수가 오름차순으로 정렬되었을 때)

증명

(by contradiction) 양의 정수 $n$이 두가지 다른 방식의 소수의 합으로 표현할 수 있다고 가정하자

\[n = p_1p_2p_3\cdots p_s \text{ and } n = p_1p_2p_3\cdots p_t\]

• 인수분해에서 모든 공통 소수를 제거한다
• Lemma 3에 따라

WIP_DN_07_P56

합동을 정수로 나누기

유효한 합동의 양변을 정수로 나눈다고 해서 항상 유효한 합동이 되는 것은 아니다

그러나, modulus에 대한 relatively prime(서로소)으로 나누었을 땐 유효한 합동이 된다

정리 7 : $m$을 양의 정수라 하고 $a, b, c$을 정수라 하자.

만약 $ac ≡ bc (\mod m)$이고 $\gcd(c, m) =1$이라면, $a ≡ b (\mod m)$이다

증명

Lemma 2와 $\gcd(c, m)=1$이라는 사실에 의해 다음이 성립한다

\[ac ≡ bc (\mod m)\] \[m \mid ac - bc = c(a-b)\]

따라서 $m \mid a - b$ 가 성립하므로, $a ≡ b (\mod m)$이 된다