소수 판별법, 왜 루트 N 이하의 수만 나눠보면 되는 것일까?

에라토스테네스의 체 라는 개념을 읽어보면 n이 소수인지 아닌지 판별하기 위해서는 sqrt(n) 이하의 수만 나눠보면 된다고 한다. (sqrt는 루트를 의미함)

근데 왜 sqrt(n) 이하의 수를 나눠보면 알 수 있는 것인가?

감으로는 알 것 같으면서도 손으로 증명해 보려고 하니 잘 이해가 가지 않았고, 명쾌하게 해답을 주는 정보를 찾지 못해서 직접 생각해 보다 답이 나와 포스팅을 한다.

어떤 수 X가 합성수라고 하자.

그럼 X는 M x N의 형태로 나타날 수 있다.

그럼 여기서 M >= N 이라고 하자.

그럼 아래와 같은 식이 성립한다.

-> X = M x N 

-> M x M >= M x N .... (N <= M)

-> M^2 >= X (M x N = X)

-> M >= sqrt(X)

즉 어떤 수 M의 최소값은 sqrt(X)이다.

그리고 N <= M 이므로 N의 최대값은 sqrt(X)이 된다.

그러므로 어떤 수 X가 합성수라면 sqrt(x)보다 같거나 큰수 M과, sqrt(X) 보다 같거나 작은 수 N의 합성수로 이루어 진다.

그래서 N보다 같거나 작은수들로만 모듈러 연산을 해서 0이 나오면 합성수, 나오지 않으면 소수가 되는 것이다.

* 논리적 오류가 있으면 지적해주세요. 제가 생각한 것을 그대로 쓴 것이기 때문에 오류가 있을 가능성이 높습니다.