1. 소수 (素數) (Prime Number)
ㅇ 더이상 나누어지지 않는 수
- 1과 자기자신 외 다른 수로는 나누어지지 않는, 1보다 큰 자연수(양의 정수)
. 무한개의 소수가 있음
.. 例) 2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31, 37, 41, 43, 47, 53, ...
ㅇ 소수의 주요 성질
- 소수 p > 1
- p의 양의 약수로는, 1 과 자기자신 p 뿐임
- 소수는 무수히 많이 존재함
* 정수를 소수로 분해(소인수 분해)하는 것의 어려움 => 현대 암호기술의 핵심
. (소인수 분해 : 정수를 소수들의 곱으로 표현하는 것)
ㅇ 소수의 판정
- 에라토스테라스의 체가 유명
. (2부터 시작하여, 모든 정수의 배수를, 체로 걸러내는 방법) ☞ 소수 판정 참조
ㅇ 소수의 정리 (prime number theorem)
- 자연수가 무한히 커질 때, 그 안에 들어 있는 소수의 개수를 근사적으로 밝히는 정리
- 구체적으로, 자연수 x가 충분히 클 때, x 보다 작은 소수의 개수는, 약 x/ln(x)
[# \lim_{x \to \infty} \frac{π(x)}{x/\ln(x)} = 1 #]
. π(x) : 자연수 x을 넘지 않는 소수의 개수
2. 합성수 (Composite Number)
ㅇ 소수가 아닌 수
- 1과 자기 자신이 아닌 다른 양의 정수의 곱으로 나타낼 수 있는 양의 정수
. 즉, 합성수 c = a b
- 그 약수를 3개 이상의 수 (1,자기자신,소수) 로써 표현 가능함
3. 자연수에서 소수,합성수
ㅇ `1` => 소수도 합성수도 아님
ㅇ `1` 보다 큰 모든 정수 => 소수이거나 합성수
ㅇ 모든 자연수의 표현 => 소수들의 거듭제곱 및 곱으로 표시 가능
- 例) 36 = 22 x 32, 120 = 23 x 3 x 5 등
ㅇ 소수는 무한히 많이 있음
4. [참고사항]
ㅇ 두 정수의 공약수가 1 뿐일 때 ☞ 서로소 (Coprime,Relatively Prime)