[이산수학] 정수론

 

 

정수론

---

1. 정수론

정수론은 암호학, 알고리즘 이론 등에서 사용되는 정수에 관한 수학적인 구조와 성질을 연구합니다.

 

2. 나눗셈(Division)

2.1. 기본 개념

나눗셈은 앞으로 다룰 소수, 최대공약수, 모듈러 등에서 가장 기본이 되는 개념입니다. 나눗셈의 정의는 다음과 같습니다.

a는 정수, b는 양의 정수일 때,
a = bq + r
를 만족하는 정수 q, r이 존재한다. (단, 0 ≤ r ＜ b)

a: 나눠지는 수
b: 나누는 수
q: 몫
r: 나머지

이때 r = 0인 경우 a는 b의 "배수(multiple)"라고 하며, b는 a의 "약수(divisor)"라고 합니다. 그리고 이때 a와 b의 관계를 b | a로 표현합니다.

 

또한, 나눗셈은 아래와 같은 관계를 만족합니다.

a, b, c가 임의의 정수일 때, (단, a ≠ 0)
① a | b 이고 a | c 이면, a | (b + c)
② a | b 이면, a | bc
③ a | b 이고 b | c 이면, a | c

 

2.2. 최대공약수(Greatest common divisor)

최대공약수는 0이 아닌 2개 정수가 각각 가질 수 있는 약수의 집합 중 가장 큰 공통 약수입니다. 정수 a, b의 최대공약수는 gcd(a, b)라고 표현합니다. 또한, gcd(a, b) = 1을 만족하는 a, b는 서로소(relatively prime) 관계라고 합니다.

 

3. 모듈로(Modular)

모듈로는 정수를 임의의 양의 정수로 나누었을 때 나머지를 의미하고, a = bq + r 일때 아래와 같이 표현합니다.

$$a(\mathrm{mod}b)=r$$

 

3.1. 모듈로 합동(Modular congruene)

모듈로 합동은 두 정수 a, b가 임의의 양의 정수 m으로 나누었을 때 나머지가 같은 경우를 의미하고, 이런 관계를 "모듈로-m 합동"이라고 말하며 다음과 같이 표현합니다.

$$a\equiv b(\mathrm{mod}m)$$

 

또한, 모듈로 합동은 아래와 같은 관계를 만족합니다.

a, b, c, d는 임의의 정수이고 m은 1보다 큰 정수일 때, a ≡ b (mod m)과 c ≡ d (mod m)를 만족하면,
① a + c ≡ b + d (mod m)
② a - c ≡ b - d (mod m)
③ ac ≡ bd (mod m)

 

4. 소수(Prime number)

소수는 암호학 분야에서 자주 사용되는 개념 중 하나입니다. 

4.1. 기본 용어

• 소수: 1과 자기 자신 이외의 양의 정수로 나누어 떨어지지 않는 1이 아닌 자연수 (예시. 2, 3, 5)
• 합성수: 소수 이외의 1이 아닌 자연수 (예시. 4, 6, 8)
• 소인수: 소수인 약수

 

4.2. 소인수분해(Prime factorization)

소인수 분해는 말 그대로 임의의 자연수를 소인수로 분해를 하는, 즉 소수의 곱으로 나타내는 것입니다. 예를 들어 8 = 2 * 2 * 2, 12 = 2 * 2 * 3처럼 분해합니다.

 

4.3. 무한히 많은 소수

소수는 무한히 많이 존재합니다. 이는 다음과 같은 방법으로 증명됩니다.

1. 소수가 n개의 유한 집합이라 가정하고, 소수들을 오름차순으로 정렬했을 때 p₁, p₂, ..., p_n이라고 가정합니다.
2. a = p₁ * p₂ * ... * p_n + 1인 정수 a라고 정의합니다. 이때 a는 정의에 의해 소수 또는 합성수가 됩니다.
3. 만약 a가 합성수라면 n개의 소수 중 적어도 1개로는 나누어져야 하는데, 모든 임의의 소수 p_k에 대해 a mod p_k = 1 이므로 a는 합성수가 아닌 1 또는 소수입니다.
4. 만약 a가 소수라면 a는 n개의 소수 집합에 포함되어야 하는데, 포함될 수 없기 때문에 a는 소수가 아닌 1 또는 합성수입니다.
5. 만약 a가 1이라면 p₁ * p₂ * ... * p_n = 0이 되어야 하는데, 이는 소수는 1보다 큰 자연수라는 정의에 위배되기 때문에 a는 1이 아닌 소수 또는 합성수입니다.
6. 결론적으로 3, 4, 5번 과정으로 인해 a는 1, 소수, 합성수 그 어떠한 가정에도 포함될 수 없으므로 소수가 n개의 유한 집합이라는 가정은 모순입니다. 따라서 소수는 무한히 많이 존재해야 합니다.

---

연관 게시글

 

[이산수학] 이산수학?

[이산수학] 이산수학?

---

참조

•