Number Theory - 6.1 약수의 합과 개수

Chapter 6 - 수론 함수 에 대한 정리를 시작한다.

PS에 직접적으로 쓰이는 중요한 내용들이 많이 등장한다.

수론 함수

수론 함수number-theoretic function또는 산술 함수arithmetic function은 정의역이 양의 정수인 임의의 집합이다.

치역에 제한은 없지만, 정수론에서 다루는 대부분의 함수는 정수의 치역을 갖는다.

양의 약수의 개수와 약수의 합의 수론 함수

Definition 6.1

주어진 양의 정수 $n$에 대해,

$\tau(n)=$ $n$의 양의 약수의 개수

$\sigma(n)=$ $n$의 양의 약수의 합

$n$이 소수일 필요충분조건은 $\tau(n)=2$, 또한 $\sigma(n)=n+1$ 이다.

대형 연산자 밑에 $n$의 약수들을 순회하는 경우를 다음과 같이 표기한다.

$$ \begin{aligned} \tau(n)=\displaystyle \sum_{d \mid n}1\\ \sigma(n)=\displaystyle \sum_{d \mid n}d \end{aligned} $$

소인수분해와 약수

Theorem 6.1

$$ n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} $$

이 $n$의 소인수분해 꼴이면, $n$의 양의 약수는 정확히 다음과 같은 정수 $d$의 형태이다.

$$ \begin{aligned} d=p_1^{a_1}p_2^{a_2} \cdots p_r^{a_r}~~~(0 \le a_i \le k_i) \end{aligned} $$

증명

약수 $d=1$은 $a_1=a_2=\cdots=a_r=0$ 일 때 얻어지고, $d=n$은 $a_1=k_1, \dots, a_r=k_r$ 일 때 얻어진다.

그 외의 경우 $d$가 $n$을 나누어 $dd'=n~(d > 1, d' > 1)$ 이 된다.

$d, d'$를 소수의 곱으로 표현하면,

$$ \begin{matrix} d=q_1q_2\cdots q_s,~~d'=t_1,t_2\cdots t_u\\ n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}=q_1q_2\cdots q_st_1t_2 \cdots t_u \end{matrix} $$

위 두 개는 $n$의 두 개의 소인수분해 형태이다.

소인수 분해의 유일성에 의해 각 소수 $q_i$는 $p_j$ 중 하나이다.

같은 소수를 모아 거듭제곱으로 나타낸다면,

$$ d=q_1q_2\cdots q_s=p_1^{a_1}p_2^{a_2} \cdots p_r^{a_r} $$

을 얻고, 여기서 $a_i=0$도 가능하다.

역 증명

역으로 모든 정수 $d=p_1^{a_1} \cdots p_r^{a_r}~(0 \le a_i \le k)$ 는 $n$의 약수이다.

$$ n=p_1^{k_1} \cdots p_r^{k_r}=p_1^{a_1} \cdots p_r^{a_r} \left( p_1^{k_1-a_1} \cdots p_r^{k_r-a_r} \right) $$

로 쓸 수 있고, 여기서 $k_i-a_i \ge 0$ 이다.

그러면 $d' > 0$ 이고, $d \mid n$ 이다.

---

이 정리를 $\tau$와 $\sigma$에 적용시켜보자.

Theorem 6.2

만약 $n=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$이 $n>1$의 소인수 분해라면,

$$ \begin{aligned} \tau(n)=\displaystyle \prod_{i=1}^{r} (k_i+1)\\\\ \sigma(n)=\displaystyle \prod_{i-1}^{r} \dfrac {p_i^{\large k_i+1}-1}{p_i-1} \end{aligned} $$

증명

Theorem 6.1에 따라 $n$의 양의 약수는 정확히 다음과 같다.

$$ d=p_1^{a_1} \cdots p_r^{a_r}~~(0 \le a_i \le k_i) $$

여기서 지수 $a_i$에 대해서 $k_i+1$ 개의 선택방법$(0 \sim k_i)$이 있으므로, 모두 곱해주면 그것이 약수가 만들어지는 경우의 수이다.

즉, $\tau(n)=\displaystyle \sum_{i=1}^{r} (k_i+1)$

$\sigma(n)$을 계산하기 위해, 다음과 같은 곱을 생각한다.

$$ \begin{aligned} &\left( 1+p_1+p_1^2+\cdots+p_1^{k_1} \right) \cdot \left( 1+p_2+p_2^2+\cdots+p_2^{k_2} \right)\\ &\cdots \left( 1+p_r+p_r^2+\cdots+p_r^{k_r} \right) \end{aligned} $$

각 $n$의 양의 약수는 이 곱의 전개의 하나의 항으로 꼭 한 번씩 나타난다.

등비수열의 합 공식을 이용하면,

$$ \begin{aligned} \sigma(n)&=\left( \dfrac {p_1^{k_1+1}-1}{p_1-1} \right) \cdot \left( \dfrac {p_2^{k_2+1}-1}{p_2-1} \right)\\ &\cdots \left( \dfrac {p_r^{k_r+1}-1}{p_r-1} \right)=\displaystyle \prod_{i=1}^{r} \left( \dfrac {p_i^{k_i+1}-1}{p_i-1} \right) \end{aligned} $$

$\square$

곱의 기호 $\prod$

파이($\prod$) 라고도 불리는 이 기호는 곱의 결과를 표시하는데 쓰인다. 합의 결과는 $\sum$ 인 것과 동일하게 쓰인다.

양의 약수의 곱

$$ \displaystyle \prod_{d \mid n} d=n^{\large \tau(n)/2} $$

$\because$ $n=dd'$를 만족하는 $d$와 $d'$ 쌍은 $tau(n)$ 개가 생기므로,

$$ \begin{aligned} n^{\tau(n)}&=\displaystyle \prod_{d \mid n}d \prod_{d' \mid n}d'\\ &\Downarrow\\ n^{\tau(n)/2}&=\displaystyle \prod_{d \mid n}d ~~~~~~~~~~ \because \prod_{d \mid n}d=\prod_{d' \mid n}d' \end{aligned} $$

하지만 $\tau(n)$이 홀수라면 $n^{\tau(n)/2}$가 값이 정수가 아닐수 있지 않을까?

그럴일은 없다.

$\tau(n)$이 홀수이면 $n$은 완전제곱수이기 때문에 $n=m^2$를 만족하는 $m$이 존재하고,

$$ n^{\tau(n)/2}=m^{\tau(n)} $$

이 되어 모두 정수가 나온다.

승법 함수, 곱셈적 함수

승법함수에 대한 내용과 뫼비우스 반전공식 쪽은 PS와 정수론쪽 챕터로 다시 다룰 예정이다.
여기선 이론만 알아보자.

Definition 6.2

수론 함수 $f$를 $gcd(m,n)=1$ 일 때, $f(mn)=f(m)f(n)$을 만족하면,

함수 $f$를 승법적multiplicative이라 한다.

승법함수가 중요한 점은, 어떤 수 $n$을 소인수 분해하고, $f(p^k)$의 값만 안다면, $f(n)$의 값을 완전히 결정할 수 있다는 것이다.

$f$ 가 승법적 함수라면,

$$ \begin{aligned} n&=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}\\ f(n)&=f(p_1^{k_1})f(p_2^{k_2})\cdots f(p_r^{k_r}) \end{aligned} $$

$f$가 항등적으로 $0$이 아닌 승법 함수이면, $f(n) \ne 0$인 정수 $n$이 존재한다.

이 때, $f(n \cdot 1)=f(n)f(1)$ 이므로, $f(1)=1$ 이다.

즉, 우리가 다룰 대부분의 승법 함수에서는 $f(1)=1$ 이다.

---

Theorem 6.3

$\tau$와 $\sigma$도 승법 함수이다.

증명

$m,n$ 을 서로소라고 하자. $m$또는 $n$이 $1$이면 결과는 당연히 사실이다.

$\because \tau(1)=1,~\sigma(1)=1$

$m > 1,~ n > 1$ 이라 가정하자.

$m=p_1^{k_1} \cdots p_r^{k_r},~~ n=q_1^{j_1} \cdots q_s^{j_s}$ 라 한다.

$gcd(m,n)$ 이므로 모든 $p_i$와 $q_j$ 에 대해서 $p_i \ne q_j$

따라서 곱 $mn$의 소인수분해는

$$ mn=p_1^{k_1} \cdots p_r^{k_r}q_1^{j_1} \cdots q_s^{j_s} $$

Theorem 6.2를 적용하여

$$ \begin{aligned} \tau(mn)&=[(k_1+1)\cdots(k_r+1)] \cdot [(j_1+1)\cdots(j_s+1)]\\ &=\tau(m)\tau(n) \end{aligned} $$

따라서 $\tau$는 승법함수이다.

같은 방법으로,

$$ \begin{aligned} \sigma(mn)&=\left[ \left( \dfrac {p_1^{k_1+1}-1}{p_1-1} \right) \cdots \left( \dfrac {p_r^{k_r+1}-1}{p_r-1} \right) \right]\\ &\cdot \left[ \left( \dfrac {q_1^{j_1+1}-1}{q_1-1} \right) \cdots \left( \dfrac {q_s^{j_s+1}-1}{q_s-1} \right) \right]\\ &=\sigma(m)\sigma(n) \end{aligned} $$

즉, $\tau$와 $\sigma$는 승법함수이다. $\square$

---

다음과 같은 보조정리를 보고가자.

Lemma

정수 $gcd(m,n)=1$ 이면, $mn$의 양의 약수의 집합은

$d_1 \mid m,~d_2 \mid n$ 이고, $gcd(d_1,d_2)=1$ 인 모든 곱 $d_1d_2$ 로 구성된다.

더군다나 이 곱은 모두 다르다.

증명

$m>1$, $n > 1$ 이라고 가정해도 무방하다.

$$ \begin{aligned} m=p_1^{k_1} \cdots p_r^{k_r}\\ n=q_1^{j_1} \cdots q_s^{j_s} \end{aligned} $$

를 각각의 소인수분해라 할 때, 소수 $p_i, q_j$ 가 모두 다르므로 $mn$의 소인수분해는

$mn=p_1^{k_1} \cdots p_r^{k_r}q_1^{j_1} \cdots q_s^{j_s}$ 이다.

따라서 $mn$의 모든 양의 약수 $d$는 다음과 같은 형태로 유일하게 표현된다.

$$ d=p_1^{a_1} \cdots p_r^{a_r}q_1^{b_1} \cdots q_s^{b_s} ~~ (0 \le a_i \le k_i,~0 \le b_i \le j_i) $$

이것은 $d$를 $d_1d_2$ 로 쓸 수 있게 해준다.

어느 $p_i$와 $q_j$도 같지 않기 때문에 $gcd(d_1,d_2)=1$ 이다. $\square$

Theorem 6.4

$f$가 승법 함수이고, $F$가 다음과 같이 정의되면

$$ F(n)=\displaystyle \sum_{d \mid n}f(n) $$

$F$ 도 승법함수이다.

증명

$m,n$을 서로소인 양의 정수라 하자.

$$ F(mn)=\displaystyle \sum_{d_1 \mid m} \sum_{d_2 \mid n}f(d_1d_2) $$

보조정리에 의해 $mn$의 모든 약수 $d$는 $gcd(d_1,d_2)=1$ 인 $m$의 약수 $d_1$과 $n$의 약수 $d_2$ 의 곱 $d_1d_2$ 로 나타낼 수 있다.

승법함수의 정의에 의해 $f(d_1d_2)=f(d_1)f(d_2)$ 이다.

$$ \begin{aligned} F(mn)&=\displaystyle \sum_{d_1 \mid m} \sum_{d_2 \mid n} f(d_1d_2)\\ &=\sum_{d_1 \mid m}\sum_{d_2 \mid n}f(d_1)f(d_2)\\ &=\left( \sum_{d_1 \mid m} f(d_1) \right)\left( \sum_{d_2 \mid n} f(d_2) \right)\\ &=F(m)F(n)~~\square \end{aligned} $$

Corollary

함수 $\tau$와 $\sigma$는 승법 함수이다.

증명

상수 함수는 승법 함수이므로,

$$ \tau(n)=\displaystyle \sum_{d \mid n}1\\ \sigma(n)=\displaystyle \sum_{d \mid n}d $$

$\square$