Number Theory - 6.3 최대 정수 함수

최대 정수 함수

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

Definition 6.4

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

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

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

팩토리얼과 최대 정수 함수

Theorem 6.9

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

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

증명

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

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

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

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

즉,

$$ \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^{\infty}$까지 갈 필요 없이, $p^k \le n$ 이 되는 시점까지 유한히 시행해주면 된다.

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

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

$\square$

---

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

$$ n!=\displaystyle \prod_{p \le n}p^{\normalsize \displaystyle \sum_{k=1}^{\infty} \left[ \dfrac n{p^k} \right] }~~~~p\text{는 소수} $$

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

이항계수와 정수

Theorem 6.10

$n$과 $r$이 $1 \le r < n$인 양의 정수이면,

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

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

증명

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

$r!(n-r)!$의 각 소인수 $p$에 대해,

$$ \left[ \dfrac n{p^k} \right] \ge \left[ \dfrac r{p^k} \right]+\left[ \dfrac {n-r}{p^k} \right],~~k=1,2,\dots $$

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

$$ \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!$ 을 나누는 소수 $p$의 가장 큰 거듭제곱의 지수이고, 우변은 $r!(n-r)!$ 에 포함된 이 소수의 가장 큰 거듭제곱이다.

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

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

Corollary

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

증명

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

수론 함수와 최대 정수 함수

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

Theorem 6.11

$f$와 $F$를 다음을 만족하는 수론 함수라고 하자.

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

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

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

증명

다음 식에 주목한다.

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

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

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

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

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

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

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

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

---

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

$$ \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 로 빠르게 세줄 수 있다.