2. 소수와 소인수분해

II. 소수와 소인수분해

1. 소수

소수란 더 이상 분해되지 않는 수로서 수를 형성하는 근원이다.

n∈Z에 대하여 (1) n : 소수 ⇔ (i) n>1 (1이상의)                    (ii) 0< k|n ⇒ k=1 or k=n (더 이상 쪼개지지 않는 수) (2) n : 합성수 ⇔ (i) n>1                       (ii) ∃k,l ∈Z s.t. n=kl, 1 <k ≤l <n

소수는 어떤 수를 나누지 않으면 서로소인 성질이 있다.

p∤a ⇔ (a, p)≠p ⇔ (a, p)=1 ⇔ (a, p^n)=1

여러가지 성질이 있겠지만 생략한다.

소수의 판정법은 에라토스테네스의 체 라는 개념을 통해 설명한다. 간단히 말하자면 제곱근보다 작은 소수들을 직접 나눠서 알아보는 것이다. 이를 간단히 표현하면 다음과 같다.

1<n 에 대하여 n≠소수 ⇔ ∃p : 소수  s.t. p|n, p≤[√n] 그렇지 않으면 소수

그외에도 소수는 무수히 많다라는 사실도 증명이 가능하다. 방법은 유한개의 소수가 있다고 가정하고 모두 곱한후 1을 더하면 그 어떤소수도 나눌 수 없는 수가 나오게 되는데 이는 가정에 모순임을 밝히면 된다.

2. 소인수분해와 표준분해

소인수분해는 전편에서 언급하였던 정수가 유일인수분해정역이라는 것과 연관있다. 

유일인수분해정역의 정의에 따라 모든 정수는 인수분해를 유일하게 가지며 소수의 곱으로 표현된다 이를 소인수분해라고 한다.

이때, 서로 다른 소수들을 나누어 인수분해하고 이를 표준분해라고 한다. 

3. 페르마소수와 메르센소수

(물론 역은 성립하지 않는다.)

위 두 사실을 통해 우리는 2가지 형태의 수를 정의한다.

전자와 같은 형식의 수를 페르마수 라고 한다.

후자와 같은 형식의 수를 메르센수 라고 한다.

페르마 수가 소수일 때 이를 페르마소수라고 한다.

메르센 수가 소수일 때 이를 메르센소수라고 한다.

페르마수와 메르센수과 관련된 몇가지 정리를 소개하고자 한다. 

<페르마수와 관련된 정리> $m,n \ge 1$ 에 대하여 (1) ${F_0}{F_1} \cdots {F_{n - 1}} = {F_n} - 2$ (2) $m \ne n \Leftrightarrow ({F_m},{F_n}) = 1$       (페르마수끼리는 서로소이다.)

<메르센수와 관련된 정리>  $a \ge 2$, $m,n \ge 1$에 대하여 (1) $n|m \Rightarrow {2^n} - 1|{2^m} - 1$ (지수를 나누면 메르센수도 나눈다.)   (2) $({2^m} - 1,{2^n} - 1) = {2^{(m,n)}} - 1$                                  (3) $(m,n) = 1 \Leftrightarrow ({M_m},{M_n}) = 1$  (지수끼리 서로소이면 메르센수도 서로소이다.) (1), (2)는 물론 꼭 밑이 2가 아니어도 성립하나 이렇게 적겠다.

4. 양의 약수의 개수와 합

 양의 약수의 개수와 합을 구하는 방법은 우리가 익히 알고 있는 방법을 통해 구하면 된다.

양의 약수의 개수를 구하는 방법은 표준분해를 하고 지수에 1씩을 더해서 서로 곱하면 된다.

양의 약수의 합을 구하는 방법은 표준분해를 하고 0승부터 n승까지 더해서 더한것을 곱해서 (분배법칙) 구한다.