Floor Function
정의
최대정수함수란, 실수를 집어넣으면 그 실수보다 크지 않은 최대 정수를 내뱉는 함수를 말한다. 이렇게 쓰니 뭔가 어려워 보이지만, 실상은 학교 수학시간에 자주 보았을 가우스 함수를 말한다. 하지만 이 함수를 가우스 함수라 부르는 곳은 한국 뿐이며, 세계적으로는 최대정수함수(Greatest Integer Function)나 바닥함수(Floor Function)이라고 부른다. 최대정수함수는 주로 수학계에서, 바닥함수는 주로 프로그래밍에서 쓴다.
기호로는 [math]\displaystyle{ \left[\cdot\right] }[/math]나 [math]\displaystyle{ \lfloor\cdot\rfloor }[/math]를 쓰는데, 정수론과 한국의 학교 수학에서는 전자를, 나머지는 후자를 쓴다. 정수론에선 아무래도 자주 쓰는 함수다 보니 익숙한 기호를 쓰고, 나머지 학문에서는 다른 함수와의 혼동을 막기 위해 전용 기호를 쓰는 것. 한국 학교 수학에서도 대괄호를 쓰는데, 사실 최대정수함수는 교육 과정 밖의 내용이다. 문제 끝에 항상 "단 [math]\displaystyle{ \left[x\right] }[/math]는 [math]\displaystyle{ x }[/math]보다 크지 않은 최대 정수를 나타낸다" 같은 말이 있는 이유는 교육 과정 밖의 내용이기 때문. 이는 달리 말하면 대괄호가 아닌 다른 기호를 집어넣고 함정을 팔 수 있음을 의미하기도 한다.
이 문서에서는 최대정수함수를 편의상 대괄호로 표기하기로 하자.
예시
- [1] = 1
- [7.2] = 7
- [-8.41] = -9
값을 계산하는 것 자체는 의외로 간단하다. 함수 안에 정수가 들어있으면 그냥 그 정수를 뱉으면 되고, 양수이면 소수점을 때버리면 된다. 음수일 경우에는 부호 때문에 쉽게 틀릴 수 있으므로 주의. 헷갈리면 수직선 위에 숫자를 찍고, 그 숫자 왼쪽에 있는 가장 큰 정수를 쓰자.
기본 성질
임의의 실수 [math]\displaystyle{ x,y }[/math]와 정수 [math]\displaystyle{ m,n }[/math]에 대해서 다음이 성립한다.
- [math]\displaystyle{ \left[x\right]\leq x\lt \left[x\right]+1 }[/math]
- [math]\displaystyle{ \left[x+m\right]=\left[x\right]+m }[/math]
- [math]\displaystyle{ \left[\left[x\right]\right]=\left[x\right] }[/math]
- [math]\displaystyle{ \left[x\right]+\left[y\right]\leq\left[x+y\right]\leq\left[x\right]+\left[y\right]+1 }[/math]
- [math]\displaystyle{ \left[x\right]+\left[-x\right]=\begin{cases}0,\quad&x\in\mathbb{Z}\\-1,\quad&x\not\in\mathbb{Z}\end{cases} }[/math]
- [math]\displaystyle{ \left[\frac{n}{m}\right] }[/math]은 1부터 [math]\displaystyle{ n }[/math]까지의 수 중 [math]\displaystyle{ m }[/math]의 배수의 개수
- [math]\displaystyle{ x\gt 0 }[/math]일 때, [math]\displaystyle{ x-\left[x\right] }[/math]는 [math]\displaystyle{ x }[/math]의 소수 부분
- 자연수 [math]\displaystyle{ n }[/math]의 일의 자릿수는 [math]\displaystyle{ n-10\left[\frac{n}{10}\right] }[/math]
- [math]\displaystyle{ x,y\geq0 }[/math]이면, [math]\displaystyle{ \left[xy\right]\geq\left[x\right]\left[y\right] }[/math]
- [math]\displaystyle{ x\geq0 }[/math]이면, [math]\displaystyle{ \left[\sqrt{\left[\sqrt{x}\right]}\right]=\left[\sqrt{\sqrt{x}}\right] }[/math]
증명
- 사실 이게 진짜 정의다.
- 우선 정의에 의해, [math]\displaystyle{ \left[x\right]\leq x\lt \left[x\right]+1 }[/math]이 성립한다. 그러면, [math]\displaystyle{ \left[x\right]+m\leq x+m\lt \left[x\right]+m+1 }[/math]이다. 이제, [math]\displaystyle{ \left[x\right]+m=n }[/math]이라 정의하자. 그러면 [math]\displaystyle{ n\leq x+m\lt n+1 }[/math]이 성립한다. 그런데 다시 정의에 의해, [math]\displaystyle{ n=\left[x+m\right] }[/math]이다. 따라서 [math]\displaystyle{ \left[x\right]+m=\left[x+m\right] }[/math].
- [math]\displaystyle{ x }[/math]가 정수이면, 정의에 의해 [math]\displaystyle{ \left[x\right]=x }[/math]가 성립한다. 그런데 [math]\displaystyle{ \left[x\right] }[/math]는 항상 정수이므로, [math]\displaystyle{ \left[\left[x\right]\right]=\left[x\right] }[/math]가 성립한다.
- [math]\displaystyle{ \left[x\right]=m,\left[y\right]=n }[/math]이라하고, [math]\displaystyle{ x-m=a,y-n=b }[/math]라 하자. 그러면 [math]\displaystyle{ \left[x+y\right]=\left[m+n+a+b\right]=m+n+\left[a+b\right] }[/math]이다. 한편, [math]\displaystyle{ 0\leq a,b\lt 1 }[/math]이므로, [math]\displaystyle{ 0\leq a+b\lt 2 }[/math]이고, 따라서 [math]\displaystyle{ 0\leq\left[a+b\right]\leq1 }[/math]이다. 따라서, [math]\displaystyle{ m+n\leq m+n+\left[a+b\right]\leq m+n+1 }[/math].
- 우선 [math]\displaystyle{ x }[/math]가 정수이면, 정의에 의해 [math]\displaystyle{ \left[x\right]=x }[/math]이다. 그러면 [math]\displaystyle{ \left[x\right]+\left[-x\right]=x-x=0 }[/math]. 이제 [math]\displaystyle{ x }[/math]가 정수가 아니라고 가정하자. [math]\displaystyle{ \left[x\right]=m,x-m=a }[/math]라 가정하면, [math]\displaystyle{ x=m+a }[/math]이고 [math]\displaystyle{ 0\lt a\lt 1 }[/math]이다. 그러면 [math]\displaystyle{ -x=-m-a=-m-1+1-a }[/math]이고, [math]\displaystyle{ 0\lt 1-a\lt 1 }[/math]이다. 따라서, 정의에 의해 [math]\displaystyle{ \left[-x\right]=-m-1 }[/math]. [math]\displaystyle{ \therefore\left[x\right]+\left[-x\right]=m-m-1=-1 }[/math]
- [math]\displaystyle{ \left[\frac{n}{m}\right] }[/math]은 [math]\displaystyle{ n }[/math]을 [math]\displaystyle{ m }[/math]으로 나눈 몫임을 보이면 끝이다. 먼저, 정의에 의해 [math]\displaystyle{ \left[\frac{n}{m}\right]\leq\frac{n}{m}\lt \left[\frac{n}{m}\right]+1 }[/math]이고, 정리하면 [math]\displaystyle{ m\left[\frac{n}{m}\right]\leq n\lt m\left[\frac{n}{m}\right]+m }[/math]이다. [math]\displaystyle{ q=\left[\frac{m}{n}\right] }[/math]이라 두면 [math]\displaystyle{ mq\leq n\lt mq+m }[/math]이고, 정리하면 [math]\displaystyle{ 0\leq n-mq\lt m }[/math]이다. [math]\displaystyle{ r=n-mq }[/math]라 두면, [math]\displaystyle{ 0\leq r\lt m }[/math]을 만족하고, 나눗셈 정리의 유일성 파트에 의해 [math]\displaystyle{ q }[/math]가 몫이라는 사실이 보여진다.
- 당연한 결과. 정수론에서는 [math]\displaystyle{ x-\left[x\right] }[/math]를 기호로 간단하게 [math]\displaystyle{ \left\{x\right\} }[/math]로 표기한다. 이 기호의 경우에는 [math]\displaystyle{ x }[/math]가 음수여도 상관없음에 주의하자.
- [math]\displaystyle{ \left[\frac{n}{10}\right] }[/math]은 [math]\displaystyle{ n }[/math]을 10으로 나눈 몫, 즉 일의 자리를 제외한 나머지 숫자이다. 이 수에 10을 곱하고 원래 수에서 빼면 당연히 일의 자릿수가 남는다.
- [math]\displaystyle{ \left[x\right]=m,\left[y\right]=n,\left\{x\right\}=a,\left\{y\right\}=b }[/math]라고 하자. 그러면 [math]\displaystyle{ \left[xy\right]=\left[mn+mb+na+ab\right]=mn+\left[mb+na+ab\right] }[/math]이다. 그런데, [math]\displaystyle{ 0\leq m,n }[/math]이고 [math]\displaystyle{ 0\leq a,b\lt 1 }[/math]이므로 [math]\displaystyle{ \left[mb+na+ab\right]\geq0 }[/math]이다. 따라서, [math]\displaystyle{ \left[xy\right]\geq mn=\left[x\right]\left[y\right] }[/math]
- [math]\displaystyle{ \left[\sqrt{x}\right]=m }[/math]이라 하자. 그러면, [math]\displaystyle{ 0\leq m\leq\sqrt{x}\lt m+1 }[/math]이고, 양변에 제곱근을 씌우면 [math]\displaystyle{ \sqrt{m}\leq\sqrt{\sqrt{x}}\lt \sqrt{m+1}\lt \sqrt{m}+1 }[/math]이고, 다시 양변에 최대정수함수를 씌우면 [math]\displaystyle{ \left[\sqrt{m}\right]\leq\left[\sqrt{\sqrt{x}}\right]\lt \left[\sqrt{m}+1\right]=\left[\sqrt{m}\right]+1 }[/math]이다. 따라서, 정의에 의해 [math]\displaystyle{ \left[\left[\sqrt{\sqrt{x}}\right]\right]=\left[\sqrt{\sqrt{x}}\right]=\left[\sqrt{m}\right]=\left[\sqrt{\left[\sqrt{x}\right]}\right] }[/math]이다.
다른 성질
소수 [math]\displaystyle{ p }[/math], 음이 아닌 정수 [math]\displaystyle{ e }[/math], 양의 정수 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ p^e\mid\mid n }[/math]은 [math]\displaystyle{ p^e\mid n }[/math]이지만 [math]\displaystyle{ p^{e+1}\nmid n }[/math]인 경우를 말한다. 이 때, [math]\displaystyle{ e }[/math]를 [math]\displaystyle{ n }[/math]의 [math]\displaystyle{ p }[/math]-지수라고 한다. 이제, [math]\displaystyle{ n! }[/math]의 [math]\displaystyle{ p }[/math]-지수는 [math]\displaystyle{ e=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\cdot=\sum_{k=1}^\infty\left[\frac{n}{p^k}\right] }[/math]이다.
이걸 어디다가 써먹냐는 생각이 들 수도 있는데, "100!을 소인수분해 했을 때 5의 지수가 몇이냐" 같은 문제를 풀 때 쓰인다. 100!의 5지수를 찾으면 끝이기 때문. 증명은 기본 성질 5번을 활용한다. 설마 진짜로 숫자를 다 써서 푼 사람은 없겠지
실수 [math]\displaystyle{ x }[/math]와 자연수 [math]\displaystyle{ n }[/math]에 대해서,
- [math]\displaystyle{ \sum_{k=0}^{n-1}\left[x+\frac{k}{n}\right]=\left[nx\right] }[/math]
가 성립하고, 이를 에르미트 항등식이라 부른다.
서로소인 홀수인 소수 [math]\displaystyle{ p,q }[/math]에 대해서,
- [math]\displaystyle{ \sum_{i=1}^{\left(p-1\right)/2}\left[\frac{iq}{p}\right]+\sum_{i=1}^{\left(q-1\right)/2}\left[\frac{ip}{q}\right]=\frac{\left(p-1\right)\left(q-1\right)}{4} }[/math]
이다. 네???
사실 이차상반성을 증명하기 위해 쓰이는 보조 정리다. 격자점 세는 문제에서도 응용할 수 있다. 증명은 이차상반성 참조.