7. 수론적 함수

7. 수론 함수

\(n\in\mathbb{N}\)에 대하여 \(\tau(n)\)을 \(n\)의 양의 약수의 개수, \(\sigma(n)\)을 양의 약수들의 합이라고 하자. 

예를 들어 \(12\)의 양의 약수는 \(1,\,2,\,3,\,4,\,6,\,12\)이므로$$\tau(12)=6,\,\sigma(12)=1+2+3+4+6+12=28$$이고, \(\tau(n)=2,\,\sigma(n)=n+1\)일 필요충분조건은 \(n\)이 소수이다.

다음의 기호$$\sum_{d|n}{f(d)}$$를 \(n\)의 모든 약수 \(d\)에 대하여 \(f(d)\)들의 합으로 정의한다. 예를 들어$$\sum_{d|12}{f(d)}=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)$$이고, 앞에서 정의한 함수 \(\tau,\,\sigma\)를$$\tau(n)=\sum_{d|n}{1},\,\sigma(n)=\sum_{d|n}{d}$$로 나타낼 수 있다. 이때$$\tau(12)=\sum_{d|12}{1}=1+1+1+1+1+1=6$$이다.

\(n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\)이 \(n\)의 소인수분해 이면, \(n\)의 양의 약수는$$d=p_{1}^{a_{1}}\cdots p_{n}^{a_{n}}\,(0\leq a_{i}\leq k_{i})$$이다.

증명: \(d=q_{1}\cdots q_{s}\)(\(q_{j}\)는 소수)라고 하자. 그러면 \(q_{1}\cdots q_{s}|p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\)이고, 임의의 \(j\)에 대하여 \(q_{j}|p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\)이므로 적당한 \(i\)에 대하여 \(q_{j}|p_{i}\)이다. 그러면 \(q_{j}=p_{i}\)이고, 따라서$$d=q_{1}\cdots q_{s}=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}\,(0\leq a_{i}\leq k_{i})$$이다. 

\(n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}(>1)\)에 대하여

(1) \(\displaystyle\tau(n)=(k_{1}+1)\cdots(k_{r}+1)=\prod_{i=1}^{r}{(k_{r}+1)}\)

(2) \(\displaystyle\sigma(n)=\frac{p_{1}^{k_{1}+1}-1}{p_{1}-1}\cdots\frac{p_{r}^{k_{r}+1}-1}{p_{r}-1}=\prod_{i=1}^{r}{\frac{p_{i}^{k_{i}+1}-1}{p_{i}-1}}\)

증명:

(1): 앞 정리에서 \(n\)의 양의 약수 \(d\)는 \(d=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}\,(0\leq a_{i}\leq k_{i})\)의 꼴이다.

\(p_{1}\)을 고르는 선택의 갯수는 \(k_{1}+1\)이고, ..., \(p_{r}\)을 고르는 선택의 갯수는 \(k_{r}+1\)이다. 그러므로$$\tau(n)=(k_{1}+1)\cdots(k_{r}+1)$$이다.

(2):$$\begin{align*}\sigma(n)&=\sum_{0\leq a_{i}\leq k_{i}}{p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}}\\&=(1+p_{1}+p_{1}^{2}+\cdots+p_{1}^{k_{1}})\cdots(1+p_{r}+p_{r}^{2}+\cdots+p_{r}^{k_{r}})\\&=\frac{p_{1}^{k_{1}+1}-1}{p_{1}-1}\cdots\frac{p_{r}^{k_{r}+1}-1}{p_{r}-1}\end{align*}$$

\(180=2^{2}\cdot3^{2}\cdot5^{1}\)이므로$$\begin{align*}\tau(180)&=(1+2)(1+2)(1+1)=3\cdot3\cdot2=18\\ \sigma(180)&=\frac{2^{3}-1}{2-1}\cdot\frac{3^{3}-1}{3-1}\cdot\frac{5^{2}-1}{5-1}=7\cdot13\cdot6=546\end{align*}$$이다.

*\(n>1\)일 때, \(n\)의 양의 약수의 곱은 \(n^{\frac{\tau(n)}{2}}\)이다.

증명: \(d\)를 \(n\)의 약수라고 하면, \(d'\)이 존재해서 \(n=dd'\)이다. 이때 \(d\)는 총 \(\tau(n)\)개 있으므로$$n^{\tau(n)}=\prod_{d|n,\,dd'|n}{dd'}=\left(\prod_{d|n}{d}\right)\left(\prod_{d'|n}{d'}\right)=\left(\prod_{d|n}{d}\right)^{2}$$이고, 따라서$$\prod_{d|n}{d}=n^{\frac{\tau(n)}{2}}$$이고, 이 값은 정수이다.

\(\tau(n)\)이 짝수이면, 자명하고, \(\tau(n)\)이 홀수이면, \(n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\)라고 했을 때, \(\tau(n)=(k_{1}+1)\cdots(k_{r}+1)\)이 홀수이므로 \(k_{i}\)는 짝수이고 \(n\)이 제곱수가 되므로 따라서 \(n^{\frac{\tau(n)}{2}}\)은 정수이다.

16의 약수는 \(1,\,2(=2^{1}),\,4(=2^{2}),\,8(=2^{3}),\,16(=2^{4})\)이다. \(\tau(16)=5\)이므로 \(16^{\frac{5}{2}}=4^{5}=2^{10}=1024\)이다.

수론적= 함수 \(f\)가 \(\text{gcd}(m,\,n)=1\)인 \(m,\,n\)에 대해 \(f(mn)=f(m)f(n)\)이면, \(f\)를 승법적(multiplicative)이라고 한다.

예를들어 \(f(n)=0,\,g(n)=1,\,h(n)=n\)은 승법적인 수론 함수이다. 

\(f\)가 승법적이면, 서로소인 \(n_{1},\,\cdots,\,n_{r}\)에 대하여 \(f(n_{1}\cdots n_{r})=f(n_{1})\cdots f(n_{r})\)이고, \(n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\)이면, \(f(n)=f(p_{1}^{k_{1}})\cdots f(p_{r}^{k_{r}})\)이므로 승법함수는 \(f(p^{k})\)(\(p\)는 소수)의 값으로 결정된다. 또한 \(f\neq0\)이면, \(n_{0}\in\mathbb{N}\)가 존재해서 \(f(n_{0})\neq0\)이고, \(\text{gcd}(n_{0},\,1)=1\)이므로, \(f(n_{0})=f(1\cdot n_{0})=f(1)f(n_{0})\)이고 따라서 \(f(1)=1\)이다.

함수 \(\tau,\,\sigma\)는 승법적이다.

증명: 서로소인 자연수 \(m,\,n\)의 소인수분해를$$m=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}},\,n=q_{1}^{j_{1}}\cdots q_{s}^{j_{s}}$$라고 하자. 그러면$$\begin{align*}\tau(mn)&=\tau(p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}q_{1}^{j_{1}}\cdots q_{s}^{j_{s}})\\&=(k_{1}+1)\cdots(k_{r}+1)(j_{1}+1)\cdots(j_{s}+1)\\&=\tau(m)\tau(n)\end{align*}$$이고,$$\begin{align*}\sigma(mn)&=\sigma(p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}q_{1}^{j_{1}}\cdots q_{s}^{j_{s}})\\&=\frac{p_{1}^{k_{1}+1}-1}{p_{1}-1}\cdots\frac{p_{r}^{k_{r}+1}-1}{p_{r}-1}\frac{q_{1}^{j_{1}+1}-1}{q_{1}-1}\cdots\frac{q_{s}^{j_{s}+1}-1}{q_{s}-1}\\&=\sigma(m)\sigma(n)\end{align*}$$이다.

\(\text{gcd}(m,\,n)=1\)이면, \(mn\)의 양의 약수의 집합은 \(\{d_{1}d_{2}\,|\,d_{1}|m,\,d_{2}|n\}\)이다.

증명: \(m=1\) 또는 \(n=1\)이면 자명하므로 \(m,\,n>1\)이라 하자. 그러면 산술의 기본정리에 의해 \(m\)과 \(n\)의 소인수 분해는$$m=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}},\,n=q_{1}^{j_{1}}\cdots q_{s}^{j_{s}}$$이고,$$mn=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}q_{1}^{j_{1}}\cdots q_{s}^{j_{s}}$$이므로 \(mn\)의 양의 약수의 집합은 다음과 같다.$$\begin{align*}&\{p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}q_{1}^{b_{1}}\cdots q_{s}^{b_{s}}\,|\,0\leq a_{i}\leq k_{i},\,0\leq b_{i}\leq j_{i}\}\\&=\{d_{1}d_{2}\,|\,d_{1}|m,\,d_{2}|n\}\end{align*}$$

\(f\)가 승법함수이고, \(\displaystyle F(n)=\sum_{d|n}{f(d)}\)이면, \(F(n)\)은 승법적이다.

증명: \(\text{gcd}(m,\,n)=1\)인 \(m,\,n\in\mathbb{N}\)에 대하여$$\begin{align*}F(mn)&=\sum_{d|mn}{f(d)}=\sum_{d_{1}|m,\,d_{2}|n}{f(d_{1}d_{2})}=\sum_{d_{1}|n}{\sum_{d_{2}|n}{f(d_{1}d_{2})}}\\&=\sum_{d_{1}|m}{\sum_{d_{2}|n}{f(d_{1})f(d_{2})}}\\&=\left(\sum_{d_{1}|m}{f(d_{1})}\right)\left(\sum_{d_{2}|n}{f(d_{2})}\right)\\&=F(m)F(n)\end{align*}$$이므로 \(F(n)\)은 승법적이다.

\(g(n)=1\)과 \(h(n)=n\)은 승법적이므로,$$\tau(n)=\sum_{d|n}{1},\,\sigma(n)=\sum_{d|n}{d}$$는 앞의 정리에 의해 승법적이다.

참고자료:

Elementary Number Theory 7th edition, Burton, McGraw-Hill