약수와 소수

• 약수

어떤 수를 나누어 떨어지게 하는 수, 수식으로 쓰면  \( N = A \times B \) 이 된다.

이때, A와 B를 N의 약수라고 한다.

다음은 1 ~ 10까지 정수에 대한 약수이다. (1은 모든 정수의 약수이다.)

정수 N	N의 약수	비고
1	1
2	1, 2	소수
3	1, 3	소수
4	1, 2, 4
5	1, 5	소수
6	1, 2, 3, 6
7	1, 7	소수
8	1, 2, 4, 8
9	1, 3, 9
10	1, 2, 5, 10

 

 

• 소수 

1과 자기 자신으로만 나누어 떨어지는 수, 즉 약수가 없는 숫자이다.

위의 표에서 2, 3, 5, 7 이 소수이다. 2는 유일한 짝수 소수이다.

 

 

• 약수의 특징

\( N = A \times B \) 를 보면 약수는 항상 쌍(A, B)으로 존재한다.

그리고 A,B 둘 중 하나는 반드시 \( \sqrt{N} \) 보다 작다. 

왜냐하면

\( N = A \times B \) 는

\( N = A \times \frac{N}{A} \) 로 표현할 수 있고,

여기서 A는 \( A \leq \frac{N}{A} \) 이기 때문이다. 예)  \( 4 = 2 \times 2 \) , \( 6 = 2 \times 3 \)

단, N이 약수의 제곱( \( N = A \times A \) )일 때는 약수가 쌍으로 존재하지 않는다.  예)  \( 4 = 2 \times 2 \) , \( 9 = 3 \times 3 \)

 

 

• 소수의 판별

합성수(N)은 최소 소인수 A로 소인수분해가 된다. \( N = A \times \frac{N}{A} \)

A는 최소 소인수이므로, \( A \leq \frac{N}{A} \) 이다. 

양변을 정리하면, \( A^{2} \leq N \) 이 되고, \( A \leq \sqrt{N} \) 이 된다.

즉, N이 합성수라면, \( 2 \ldots \sqrt{N} \) 사이에 반드시 최소 소인수 A(나누어 떨어지는 수)가 있어야 한다. 만약 없다면, N은 소수가 된다.