소수란? 정의, 목록, 그리고 찾는 방법

소수는 $1$보다 큰 정수 중에서 양의 약수가 정확히 두 개, 즉 $1$과 자기 자신뿐인 수입니다. 따라서 $2, 3, 5,$ $7$은 소수이고, $1$은 소수가 아니며, $12$ 같은 수는 합성수입니다.

$1$보다 큰 정수가 양의 약수를 두 개보다 많이 가지면 그 수를 합성수라고 합니다. 예를 들어 $12$는 $1, 2, 3, 4, 6,$ $12$로 나누어떨어지므로 합성수입니다.

50까지의 소수

다음은 $50$까지의 소수입니다:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47$$

간격이 단순하게 반복되는 규칙은 없습니다. 예를 들어 $11$과 $13$은 서로 가깝지만, 그다음 $23$에서 $29$까지의 간격은 더 큽니다.

어떤 수가 소수일까?

어떤 수가 소수이려면 다음 두 조건을 모두 만족해야 합니다:

1. $1$보다 커야 합니다.
2. 양의 약수가 $1$과 자기 자신뿐이어야 합니다.

그래서 $1$은 소수가 아니고, 짝수인 $2$는 소수입니다. $2$의 양의 약수는 정확히 $1$과 $2$ 두 개뿐입니다.

어떤 수가 소수인지 판별하는 방법

정수 $n > 1$에 대해, $2$부터 $\lfloor \sqrt{n} \rfloor$까지의 어떤 정수가 $n$을 나누어떨어지게 하는지 확인하면 소수인지 판별할 수 있습니다.

이유는 실용적입니다. 만약 $n = ab$라면, 두 인수 중 하나는 반드시 $\sqrt{n}$보다 작거나 같아야 합니다. 따라서 $\sqrt{n}$에 도달할 때까지 약수가 나오지 않으면, 그보다 큰 쪽에 숨어 있는 인수쌍도 없습니다.

실제로는 먼저 간단한 나눗셈 규칙부터 확인하는 경우가 많습니다:

1. $n$이 짝수이고 $2$보다 크면 소수가 아닙니다.
2. 각 자리 숫자의 합이 $3$의 배수이면, $n$은 $3$으로 나누어떨어집니다.
3. $n$의 끝자리가 $0$ 또는 $5$이고 $5$보다 크면, $n$은 $5$로 나누어떨어집니다.

이런 빠른 확인법만으로 소수임이 증명되지는 않지만, 많은 합성수를 빠르게 걸러내는 데 도움이 됩니다.

예제: $29$는 소수인가?

$29$를 판별하려면 먼저 다음을 봅니다.

$$\sqrt{29} \approx 5.38$$

따라서 $5$까지의 정수 약수만 확인하면 충분합니다.

• $29$는 홀수이므로 $2$로 나누어떨어지지 않습니다.
• $29$는 $2 + 9 = 11$이고, $11$은 $3$의 배수가 아니므로 $3$으로 나누어떨어지지 않습니다.
• $29$는 끝자리가 $0$이나 $5$가 아니므로 $5$로 나누어떨어지지 않습니다.

여기서는 $4$를 확인해도 새로운 정보가 없습니다. $4$의 배수는 모두 짝수인데, $29$는 이미 $2$로 나누어떨어지지 않기 때문입니다.

$5$까지 확인해도 약수가 없으므로, $29$는 소수입니다.

소수에서 자주 하는 실수

$1$을 소수라고 말하는 경우

그렇지 않습니다. 정의에 따르면 양의 약수가 정확히 두 개여야 하는데, $1$은 하나뿐입니다.

모든 홀수가 소수라고 생각하는 경우

많은 홀수는 합성수입니다. 예를 들어 $21$은 홀수이지만,

$$21 = 3 \times 7$$

이므로 소수가 아닙니다.

너무 멀리까지 확인하는 경우

소수 판별만 하는 것이라면 $n$보다 작은 모든 수를 다 확인할 필요는 없습니다. $\sqrt{n}$까지만 보면 충분합니다.

소수는 어디에 쓰일까?

소수는 인수분해, 나눗셈 성질, 최대공약수 문제, 최소공배수 문제에서 자주 등장합니다. $1$보다 큰 모든 정수는 순서를 제외하면 유일한 방식으로 소인수분해할 수 있기 때문에 중요합니다.

또한 소수는 모듈러 산술과 암호학에서도 등장합니다. 암호학에서는 훨씬 더 전문적인 맥락에서, 큰 소수들이 추가적인 규칙과 알고리즘과 함께 사용됩니다.

비슷한 문제를 풀어 보세요

같은 제곱근 방법으로 $47$과 $51$을 판별해 보세요. 하나는 소수이고 하나는 합성수이므로, $\sqrt{n}$에서 멈추는 규칙이 잘 이해되는지 빠르게 확인할 수 있습니다.