최대 정수 함수Permalink

최대정수함수는 가우스함수, 바닥함수라고도 부르며 정의는 다음과 같다.

Definition 6.4Permalink

임의의 실수 xx에 대해 [x][x]를 xx보다 작거나 같은 가장 큰 정수라고 한다.

즉, [x][x]는 x−1<[x]≤xx-1 < [x] \le x 를 만족하는 유일한 정수이다.

[x]=x[x]=x인 필요충분조건은 x∈Zx \in \Z 이다.

팩토리얼과 최대 정수 함수Permalink

Theorem 6.9Permalink

nn을 양의 정수, pp는 소수이면 n!n!을 나누는 가장 큰 pp의 거듭제곱의 지수는

∑k=1∞[npk] \begin{aligned} \displaystyle \sum_{k=1}^{\infty} \left[ \dfrac n{p^k} \right] \end{aligned}

증명

처음 nn개의 양의 정수 중에서 pp에 의해 나누어지는 정수는, p,2p,…,[np]p (1)p, 2p, \dots, \left[ \dfrac np \right]p ~ \left( 1 \right) 이다.

따라서 n!n! 을 정의하는 곱에서 나타나는 pp는 정확히 [np]\left[ \dfrac np \right]번 이다.

n!n!의 소인수분해에서 나타나는 pp의 지수는 (1)\left( 1 \right)에 있는 정수의 개수,

1∼n1 \sim n 중에서 p2p^2 로 나누어지는 정수의 개수, 그리고 p3p^3 으로 나누어지는 정수의 개수 ⋯\cdots 를 모두 더해서 얻어진다.

즉,

p2,2p2,…,[np2]p2p3,2p3,…,[np3]p3⋮p∞,2p∞,…,[np∞]p∞ \begin{aligned} p^2, 2p^2, \dots, \left[ \dfrac n{p^2} \right]p^2\\ p^3,2p^3,\dots,\left[ \dfrac n{p^3} \right]p^3\\ \vdots\\ p^{\infty}, 2p^{\infty}, \dots, \left[ \dfrac n{p^{\infty}} \right]p^{\infty} \end{aligned}

등이 있을 것이다.

물론 p∞p^{\infty}까지 갈 필요 없이, pk≤np^k \le n 이 되는 시점까지 유한히 시행해주면 된다.

따라서 n!n!을 나누는 pp의 전체 개수는, 다음과 같다.

∑k=1∞[npk] \displaystyle \sum_{k=1}^{\infty}\left[ \dfrac n{p^k} \right]

□\square

따라서 르장드르의 공식이라고도 불리는, n!n! 을 소수들로 표현하는 방법은 다음과 같다.

n!=∏p≤np∑k=1∞[npk]    p는 소수 n!=\displaystyle \prod_{p \le n}p^{\normalsize \displaystyle \sum_{k=1}^{\infty} \left[ \dfrac n{p^k} \right] }~~~~p\text{는 소수}

이는 PS에서도 n!n! 에 관련된 문제들에 자주 등장한다. 예시로, BOJ 1676 - 팩토리얼 0의 개수 같은 것들이 있다.

이항계수와 정수Permalink

Theorem 6.10Permalink

nn과 rr이 1≤r<n1 \le r < n인 양의 정수이면,

이항계수 (nr)=n!r!(n−r)!\dbinom {n}{r}=\dfrac {n!}{r!(n-r)!} 또한 정수이다.

아니 당연히 이항계수는 정수지 할 수도 있겠지만, 왜 정수가 나오는지에 대한 증명이다.

증명

주장은 a,ba,b 가 임의의 실수일 때, [a+b]≥[a]+[b][a+b] \ge [a] + [b] 라는 관찰에 달려있다.

r!(n−r)!r!(n-r)!의 각 소인수 pp에 대해,

[npk]≥[rpk]+[n−rpk],  k=1,2,… \left[ \dfrac n{p^k} \right] \ge \left[ \dfrac r{p^k} \right]+\left[ \dfrac {n-r}{p^k} \right],~~k=1,2,\dots

이 부등식들을 모두 더하면 다음을 얻는다.

∑k≥1[npk]≥∑k≥1[rpk]+∑k≥1[n−rpk] \begin{aligned} \displaystyle \sum_{k \ge 1} \left[ \dfrac n{p^k} \right] \ge \sum_{k \ge 1}\left[ \dfrac r{p^k} \right]+\sum_{k \ge 1} \left[ \dfrac {n-r}{p^k} \right] \end{aligned}

좌변은 n!n! 을 나누는 소수 pp의 가장 큰 거듭제곱의 지수이고, 우변은 r!(n−r)!r!(n-r)! 에 포함된 이 소수의 가장 큰 거듭제곱이다.

그러므로 모든 소수 pp는 적어도 r!(n−r)!r!(n-r)! 에 있는만큼 n!n! 에도 있다.

따라서 n!r!(n−r)!\dfrac {n!}{r!(n-r)!} 은 분모가 분자를 나누어 정수이다. □\square

CorollaryPermalink

rr개의 연속된 양의 정수의 곱은 n(n−1)⋯(n−r+1)=n!(n−r)!=n!r!(n−r)!⋅r!n(n-1)\cdots(n-r+1)=\dfrac {n!}{(n-r)!}=\dfrac {n!}{r!(n-r)!} \cdot r! 이고, 정수이다.

증명

Theorem 6.10에 의해 n!r!(n−r)!\dfrac {n!}{r!(n-r)!} 은 정수이고 r!r!도 정수이므로 정수이다. □\square

수론 함수와 최대 정수 함수Permalink

이제 나오는 내용들은 PS에서 흔히 쓰이는 테크닉인 약수의 개수를 세는것 대신, 배수의 개수를 세는것과 관련이 있는 내용이다.

Theorem 6.11Permalink

ff와 FF를 다음을 만족하는 수론 함수라고 하자.

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

그러면 모든 양의 정수 NN에 대해

∑n=1NF(n)=f(k)[Nk] \displaystyle \sum_{n=1}^N F(n)=f(k) \left[ \dfrac Nk \right]

증명

다음 식에 주목한다.

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

우변에서 동일한 f(d)f(d) 값이 나타내는 항의 개수를 보자.

항 f(k)f(k)가 ∑d∣nf(d)\displaystyle \sum_{d \mid n}f(d) 에 나타날 조건은 k∣nk \mid n이다.

모든 정수는 자기 자신을 약수로 가지기 때문에, 적어도 한 번은 1≤k≤N1 \le k \le N 인 kk에 대해 f(k)f(k)가 나타난다.

f(k)f(k)가 항으로 나타내는 합 ∑d∣nf(d)\displaystyle \sum_{d \mid n}f(d) 의 개수를 구하기 위해 1∼N1 \sim N 중, kk의 배수를 센다.

이는 당연히 [Nk]\left[ \dfrac Nk \right]개이다.

1≤k≤N1 \le k \le N 인 kk 에 대해 이것이 모두 성립하므로

∑n=1NF(n)=∑k=1Nf(k)[Nk]  □ \displaystyle \sum_{n=1}^N F(n)=\sum_{k=1}^N f(k) \left[ \dfrac Nk \right]~~\square

이로 인해 τ\tau와 σ\sigma에 대한 따름정리가 나온다.

τ(n)=∑d∣n1⟺∑n=1Nτ(n)=∑k=1N[Nk]σ(n)=∑d∣nd⟺∑n=1Nσ(n)=∑k=1Nk[Nk] \begin{aligned} \tau(n)=\displaystyle \sum_{d \mid n}1 \Longleftrightarrow \sum_{n=1}^N \tau(n)=\sum_{k=1}^N \left[ \dfrac Nk \right]\\ \sigma(n)=\sum_{d \mid n}d \Longleftrightarrow \sum_{n=1}^N \sigma(n)=\sum_{k=1}^N k \left[ \dfrac Nk \right] \end{aligned}

물론 이는 Harmonic Lemma 로 빠르게 세줄 수 있다.

Comments

You may also enjoy