📂정수론

소수 분해 원리

정리 ¹

소수 $p$ 가 자연수 $n : = d_{1} d_{2} \cdots d_{r}$ 에 대해 $p \mid n$ 면 $p$ 는 $d_{1} , d_{2} , \cdots , d_{r}$ 중 적어도 하나를 나누어야한다.

설명

$p \mid n$ 은 $n$ 이 $p$ 의 배수, 즉 $p$ 가 $n$ 을 나눈다는 말이다. 언뜻 보면 당연한 소리 같지만 엄연히 증명이 필요한 소수만의 성질이다. 소수가 아니라도 위의 정리가 항상 성립하는지 생각해보자.

증명

일단은 $n$ 이 두 자연수의 곱, 즉 $n = ab$ 라 두고 $p$ 가 $a$ 와 $b$ 둘 다를 나누지 못한다고 가정해보자.

2원 1차 방정식에 대한 정수해의 존재성:두 정수 $a,p$ 에 대해 $ax + py = \gcd (a,p)$ 는 반드시 정수해를 가진다.

$p$ 는 $a$ 를 나누지 않으므로 $a$ 는 $p$ 의 배수가 아니고, $p$ 가 소수기 때문에 $\gcd (a,p) = 1$ 이다. 따라서 $$ax + py = 1$$ 를 만족하는 $(x,y)$ 가 존재한다. 여기서 양변에 $b$ 를 곱하면 $$abx + pby = b$$ 다. 전제에서 $ab = n$ 은 $p$ 의 배수고, $pb$ 는 아예 $p$ 가 곱해져있으니 볼 것도 없이 $p$ 의 배수다. 따라서 $b$ 는 $p$ 의 배수인데, 이는 가정에 모순이고 $p$ 는 $a$ 와 $b$ 둘 중 하나는 나누어야한다.

다시 $n = d_{1} d_{2} \cdots d_{r}$ 로 돌아와보면, 위의 논의에 따라 $p$ 는 $d_{1}$ 혹은 $(d_{2} \cdots d_{r})$ 둘 중 하나를 나눠야한다.

$d_{1}$ 을 나누지 않아도 $d_{2} \cdots d_{r}$ 에 대해 같은 논의를 다시 적용시켜보면 결국 $p$ 는 $d_{1} , d_{2} , \cdots , d_{r}$ 중 하나를 나누어야한다.

■