📂정수론

산술의 기본정리 증명

정리 ¹

자연수 $n >2$ 은 유일한 소인수분해 $n = p_{1} p_{2} \cdots p_{r}$ 를 가진다. 이때 소수 $p_{1} , p_{2} , \cdots , p_{r}$ 의 순서는 무시한다.

설명

초등학교부터 자연스럽게 써오던 성질이니만큼 증명이 필요하다는 사실이 낯설겠지만 굉장히 중요하다. 어쩌면 이렇게나 쉽다는 것 자체가 기본정리라는 이름을 달만한 자격이 있다는 증거가 될 것이다.

증명

초등적 증명

Part 1. 존재성

$2=2$ 이고 $3= 3$ , 그리고 $4 = 2^2$ 으로 유일한 소인수분해가 존재한다. 이런 식으로 가능한 모든 $n$ 에 대해서 소인수분해를 찾아보고, 그 마지막 수가 $N$ 이라고 해보자. 여기서 $N+1$ 은 소수거나 합성수이므로 두가지 경우를 체크해보도록 하자.

• Case 1. $N+1$ 가 소수
  $N+1$ 가 소수라는 것은 그 스스로가 하나의 소수로써 소인수분해가 된다는 것이다.
• Case 2. $N+1$ 가 합성수
  $N+1$ 가 합성수라면 두 자연수의 곱 $N+1 = n_{1} n_{2}$ 으로 나타낼 수 있다.

우리는 $N$ 까지의 모든 자연수에 대해서는 소인수분해를 찾을 수 있었으므로, $$ n_{1} = p_{1} p_{2} \cdots p_{m} \\ n_{2} = q_{m+1} q_{m+2} \cdots q_{r} $$ 를 알고 있다. 이를 그냥 곱해주면 $N+1 = p_{1} p_{2} \cdots p_{r}$ 이므로, $N+1$ 의 소인수분해를 구할 수 있다. 두 가지 모든 케이스에 대해서 $N+1$ 의 소인수분해를 찾을 수 있으므로, $2$ 보다 큰 모든 자연수는 소인수분해를 갖는다.

---

Part 2. 유일성

이제 $n = p_{1} p_{2} \cdots p_{r}$ 이 유일함을 보이면 된다.

$n$ 의 소인수분해가 유일하지 않아서 $n = p_{1} p_{2} \cdots p_{r} = q_{1} q_{2} \cdots q_{s}$ 이 성립한다고 가정하자.이들의 순서는 유일성에 영향을 미치지 않으므로 편의상 $p_{1} \le p_{2} \le \cdots \le p_{r}$ 이라고 하자.

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

어떤 수를 나누는 소수는 그 약수 중 적어도 하나를 나누어야하므로, $p_{1}$ 은 $q_{1} , q_{2} , \cdots , q_{s}$ 중 하나를 나눠야한다. 순서는 자유로우므로 $p_{1}$ 으로 나눠지는 $q_{i}$ 를 $q_{1}$ 로 두고 $q_{1}$ 를 $q_{i}$ 로 잡는 식으로 바꿔도 상관 없다.

그런데 $q_{1}$ 역시 $p_{1}$ 과 마찬가지로 소수이므로, $p_{1} = q_{1}$ 이 성립하고 $$ p_{1} p_{2} \cdots p_{r} = q_{1} q_{2} \cdots q_{s} $$ 의 양변에서 그 둘을 소거시키면 $$ p_{2} \cdots p_{r} = q_{2} \cdots q_{s} $$ 을 얻는다. 같은 방법으로 둘 중 한 쪽이 $1$ 이 될 때까지 소거를 반복할 수 있다. 이 때 다른 쪽 한 변이 $1$ 이 아닌 경우, 소수들의 곱은 반드시 $1$ 보다 크므로 등식이 성립하지 않는다. 따라서 $$ p_{1} =q_{1} \\ p_{2} = q_{2} \\ \vdots \\ p_{i} = q_{i} \\ \vdots $$ 가 성립하고 마지막으로 $p_{r} = q_{s}$ 이 성립해야한다.

■

대수적 증명

산술의 기본정리의 대수적 증명: 정수환 $\mathbb{Z}$ 는 PID이므로 UFD다.

■

코드

아래는 소인수분해를 R 로 구현한 코드다. 소수 목록을 가져다 놓고 계산하기 때문에 소수인지 판별하는 과정이 없어 빠르다. 당연히 알고리즘으로썬 아무런 가치도 없다. 소인수분해를 쭉 나열하는 형태로 반환하기 때문에 가독성이 떨어질 수 있다. 지수꼴로 바꿔보고 싶다면 그냥 반환된 벡터에 내장함수인 table() 함수를 사용하면 된다.

prime = read.table("../attachment
                   /cfile8.uf@25411C3C5968BBE322F0D4.txt"); prime = prime[,1]
 
factorize<-function(p)
{
  q=p
  factors<-numeric(0)
  i=1; j=1
  while(q!=1)
  {
    if(q%%prime[i]) {i=i+1}
    else
    {
      q<-q/prime[i]
      factors[j]<-prime[i]
      i=1
      j=j+1
    }
  }
  return(factors)
}
 
factorize(54)
factorize(101)
factorize(256)
factorize(420)
table(factorize(420))

다음은 코드를 실행한 결과다.