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

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

수론 함수Permalink

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

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

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

Definition 6.1Permalink

주어진 양의 정수 nn에 대해,

τ(n)=\tau(n)= nn의 양의 약수의 개수

σ(n)=\sigma(n)= nn의 양의 약수의 합

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

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

τ(n)=∑d∣n1σ(n)=∑d∣nd \begin{aligned} \tau(n)=\displaystyle \sum_{d \mid n}1\\ \sigma(n)=\displaystyle \sum_{d \mid n}d \end{aligned}

소인수분해와 약수Permalink

Theorem 6.1Permalink

n=p1k1p2k2⋯prkr n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}

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

d=p1a1p2a2⋯prar   (0≤ai≤ki) \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=1d=1은 a1=a2=⋯=ar=0a_1=a_2=\cdots=a_r=0 일 때 얻어지고, d=nd=n은 a1=k1,…,ar=kra_1=k_1, \dots, a_r=k_r 일 때 얻어진다.

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

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

d=q1q2⋯qs,  d′=t1,t2⋯tun=p1k1p2k2⋯prkr=q1q2⋯qst1t2⋯tu \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}

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

소인수 분해의 유일성에 의해 각 소수 qiq_i는 pjp_j 중 하나이다.

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

d=q1q2⋯qs=p1a1p2a2⋯prar d=q_1q_2\cdots q_s=p_1^{a_1}p_2^{a_2} \cdots p_r^{a_r}

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

역 증명

역으로 모든 정수 d=p1a1⋯prar (0≤ai≤k)d=p_1^{a_1} \cdots p_r^{a_r}~(0 \le a_i \le k) 는 nn의 약수이다.

n=p1k1⋯prkr=p1a1⋯prar(p1k1−a1⋯prkr−ar) 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)

로 쓸 수 있고, 여기서 ki−ai≥0k_i-a_i \ge 0 이다.

그러면 d′>0d' > 0 이고, d∣nd \mid n 이다.

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

Theorem 6.2Permalink

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

τ(n)=∏i=1r(ki+1)σ(n)=∏i−1rpiki+1−1pi−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에 따라 nn의 양의 약수는 정확히 다음과 같다.

d=p1a1⋯prar  (0≤ai≤ki) d=p_1^{a_1} \cdots p_r^{a_r}~~(0 \le a_i \le k_i)

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

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

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

(1+p1+p12+⋯+p1k1)⋅(1+p2+p22+⋯+p2k2)⋯(1+pr+pr2+⋯+prkr) \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}

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

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

σ(n)=(p1k1+1−1p1−1)⋅(p2k2+1−1p2−1)⋯(prkr+1−1pr−1)=∏i=1r(piki+1−1pi−1) \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

곱의 기호 ∏\prodPermalink

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

양의 약수의 곱Permalink

∏d∣nd=nτ(n)/2 \displaystyle \prod_{d \mid n} d=n^{\large \tau(n)/2}

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

nτ(n)=∏d∣nd∏d′∣nd′⇓nτ(n)/2=∏d∣nd          ∵∏d∣nd=∏d′∣nd′ \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}

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

그럴일은 없다.

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

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

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

승법 함수, 곱셈적 함수Permalink

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

Definition 6.2Permalink

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

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

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

ff 가 승법적 함수라면,

n=p1k1p2k2⋯prkrf(n)=f(p1k1)f(p2k2)⋯f(prkr) \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}

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

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

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

Theorem 6.3Permalink

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

증명

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

∵τ(1)=1, σ(1)=1\because \tau(1)=1,~\sigma(1)=1

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

m=p1k1⋯prkr,  n=q1j1⋯qsjsm=p_1^{k_1} \cdots p_r^{k_r},~~ n=q_1^{j_1} \cdots q_s^{j_s} 라 한다.

gcd(m,n)gcd(m,n) 이므로 모든 pip_i와 qjq_j 에 대해서 pi≠qjp_i \ne q_j

따라서 곱 mnmn의 소인수분해는

mn=p1k1⋯prkrq1j1⋯qsjs mn=p_1^{k_1} \cdots p_r^{k_r}q_1^{j_1} \cdots q_s^{j_s}

Theorem 6.2를 적용하여

τ(mn)=[(k1+1)⋯(kr+1)]⋅[(j1+1)⋯(js+1)]=τ(m)τ(n) \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는 승법함수이다.

같은 방법으로,

σ(mn)=[(p1k1+1−1p1−1)⋯(prkr+1−1pr−1)]⋅[(q1j1+1−1q1−1)⋯(qsjs+1−1qs−1)]=σ(m)σ(n) \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

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

LemmaPermalink

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

d1∣m, d2∣nd_1 \mid m,~d_2 \mid n 이고, gcd(d1,d2)=1gcd(d_1,d_2)=1 인 모든 곱 d1d2d_1d_2 로 구성된다.

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

증명

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

m=p1k1⋯prkrn=q1j1⋯qsjs \begin{aligned} m=p_1^{k_1} \cdots p_r^{k_r}\\ n=q_1^{j_1} \cdots q_s^{j_s} \end{aligned}

를 각각의 소인수분해라 할 때, 소수 pi,qjp_i, q_j 가 모두 다르므로 mnmn의 소인수분해는

mn=p1k1⋯prkrq1j1⋯qsjsmn=p_1^{k_1} \cdots p_r^{k_r}q_1^{j_1} \cdots q_s^{j_s} 이다.

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

d=p1a1⋯prarq1b1⋯qsbs  (0≤ai≤ki, 0≤bi≤ji) 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)

이것은 dd를 d1d2d_1d_2 로 쓸 수 있게 해준다.

어느 pip_i와 qjq_j도 같지 않기 때문에 gcd(d1,d2)=1gcd(d_1,d_2)=1 이다. □\square

Theorem 6.4Permalink

ff가 승법 함수이고, FF가 다음과 같이 정의되면

F(n)=∑d∣nf(n) F(n)=\displaystyle \sum_{d \mid n}f(n)

FF 도 승법함수이다.

증명

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

F(mn)=∑d1∣m∑d2∣nf(d1d2) F(mn)=\displaystyle \sum_{d_1 \mid m} \sum_{d_2 \mid n}f(d_1d_2)

보조정리에 의해 mnmn의 모든 약수 dd는 gcd(d1,d2)=1gcd(d_1,d_2)=1 인 mm의 약수 d1d_1과 nn의 약수 d2d_2 의 곱 d1d2d_1d_2 로 나타낼 수 있다.

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

F(mn)=∑d1∣m∑d2∣nf(d1d2)=∑d1∣m∑d2∣nf(d1)f(d2)=(∑d1∣mf(d1))(∑d2∣nf(d2))=F(m)F(n)  □ \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}

CorollaryPermalink

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

증명

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

τ(n)=∑d∣n1σ(n)=∑d∣nd \tau(n)=\displaystyle \sum_{d \mid n}1\\ \sigma(n)=\displaystyle \sum_{d \mid n}d

□\square

Comments

You may also enjoy