정수론 | 가우스 함수([] 함수)

가우스 함수, [] 함수, 최대 정수 함수(Greatest integer function)의 정의

가우스 함수에 대한 명칭은 단순히 최대 정수 함수에 국한되지 않고 여러 곳에서 사용된다. 따라서, 혼동을 줄이기 위해 일반적으로 사용되는 명칭을 병기하였다.

실수 $x\in R$에 대하여 $x$를 넘지 않는 최대정수를 $[x]$라고 표기하고 함수 $[\ ]\ :\ R \rightarrow Z\ :\ x \rightarrow [x]$를 최대 정수 함수(Greatest integer function)이라 한다. []함수(Bracket function) 혹은 초등 교과과정에서는 가우스 함수라고도 부른다.

정리하자면 [ ]은 임의의 실수 $x\in R$에 대해 $x=[x]+\alpha,\ 0\le\alpha<1$로 표현할 수 있다.

예제 : 양의 정수 $n$이 $[\frac{n}{10}]+[\frac{n}{100}]+[\frac{n}{1000}]+[\frac{n}{10000}]=2016$을 만족하고 $n$의 각 자릿수의 합이 20일 때, $n$을 1000으로 나눈 나머지를 구하여라.

주어진 조건을 만족하려면 n이 5자리 정수여야 한다. 그러므로 표현하면 $n=\overline{a_4a_3a_2a_1a_0}$으로 나타낼 수 있고 각 자리수의 합이 20이므로 $a_0+a_1+a_2+a_3+a_4=20$이다. 전개식은 $a_4\cdot10^4+a_3\cdot10^3+a_2\cdot10^2+a_1\cdot10+a_0$이다. 주어진 식의 각 부분을 전개식을 기반으로 나타내면 아래와 같다.

$[\cfrac{n}{10}]=a_4\cdot10^3+a_3\cdot10^2+a_2\cdot10+a_1$

$[\cfrac{n}{100}]=a_4\cdot10^2+a_3\cdot10+a_2$

$[\cfrac{n}{1000}]=a_4\cdot10+a_3$

$[\cfrac{n}{10000}]=a_4$

따라서 주어진 방정식은 $a_4(1+10+10^2+10^3)+a_3(1+10+10^2)+a_2(1+10)+a_1$이고 괄호 안의 내용은 등비급수에 따라 바꾸면 $\cfrac{a_4(10^4-1)+a_3(10^3-1)+a_2(10^2-1)+a_1(10-1)}{10-1}$이 된다. 즉, $a_0$만 적절히 조정하면 양의 정수 $n$과 가 자릿수 합 20으로 나타낼 수 있다. 정리하면 $\cfrac{n-20}{10-1}=2016$이 되므로 $n=18164$가 되어 $n$을 1000으로 나눈 나머지는 164가 된다.

$n!$에 들어있는 소수 개수 구하는 방법

$a,\ b,\ q,\ r\in Z,\ b>0$에 대하여 $a=bq+r,\ 0\le r<b$라고 하자. 양변을 b로 나누면 $\cfrac{a}{b}=q+\cfrac{r}{b},\ 0\le \cfrac{r}{b}<1$이다. 즉 $[\cfrac{a}{b}]=q$가 됨을 알 수 있다. 따라서, $[\cfrac{a}{b}]$는 부등식 $b\cdot t\le a$를 만족하는 최대정수 $t$로도 표현할 수 있다.

정리: 자연수 $n\in N$과 소수 $p$에 대하여 $n!$ 안에 들어있는 소수 $p$의 개수는 $\sum_{k=1}^{\infty}[\frac{n}{p^k}]=[\frac{n}{p}]+[\frac{n}{p^2}]\cdots$이다.

[증명] 1부터 $n$까지의 자연수 중 $p$로 나누어지는 수는 $p,\ 2p,\ 3p,\ \cdots,\ tp$이고 정수 $t$는 $p\cdot t\le n$을 만족하는 최대 정수이다. 즉, $[\cfrac{n}{p}]=t$이다. 따라서, 1부터 $n$까지의 자연수 중 $[\cfrac{n}{p}]$개의 $p$인수가 존재한다. 그 다음 1부터 $n$까지의 자연수 중 $p^2$로 나누어지는 수는 $[\cfrac{n}{p^2}]$개 존재한다. 이를 계속 반복하면 1부터 n까지의 수에 대해 존재하는 모든 $p$인수의 개수를 구할 수 있다.

왜냐하면 지수 관점에서 곱셈이 이루어질 경우 덧셈으로 표현되고 첫 번째 과정은 말 그대로 적어도 $p^1$을 인수로 갖는 수의 개수이다. 두 번째 과정은 1부터 $n$까지 수에 대해 $p^2$로 나누어지는 수의 개수이므로 이전에 구했던 $p^1$을 가지고 있던 수 외에 $p^2$ 이상을 인수로 갖는 수만 포함하기 떄문에 이 과정을 반복하여 $[\cfrac{n}{p^2}]=0$이 되는 지점까지 반복하면 1부터 $n$까지의 수에 존재하는 모든 $p$인수를 구할 수 있다. 따라서 주어진 식은 마지막 항이 0이 되는 순간이 존재하므로 무한급수가 아니며 인수의 개수는 $\sum_{k=1}^{\infty}[\cfrac{n}{p^k}]$이다.

예제: $3042!$를 8진법으로 표현하였을 때, 마지막으로 연속되는 0의 개수는 몇 개인가?

8진법이므로 $2^3$으로 어디까지 묶이는 지 확인해야 한다. 주어진 값이 갖는 2의 개수를 구하면 $[\cfrac{3042}{2}]+[\cfrac{3042}{4}]+[\cfrac{3042}{8}]+\cdots+[\cfrac{3042}{2048}]$를 계산하면 되고 그 결과는 $1521+760+380+190+95+47+23+11+5+2+1$이 되어 3035가 된다. $[\cfrac{3035}{3}]=1011$이 되어 $3042!=k\cdot8^{1011},\ (k\nmid8)$으로 표현하면 8진법에서의 주어진 값이 갖는 연속되는 0의 개수는 1011이다.

• 위 과정에서 눈치챌 수 있겠지만 $[\cfrac{n}{p}]=t$라고 할 때 $[\cfrac{n}{p^2}]=[\cfrac{t}{p}]$가 성립하므로 계산의 복잡함을 줄일 수 있다.

예제: $n\in N$일 때, $2^n\ |\ (n+1)(n+2)\cdots(2n-1)2n$임을 증명하여라.

$(n+1)(n+2)\cdots(2n-1)2n=\cfrac{2n!}{n!}$으로 표현할 수 있다. 그리고 $n!$에 포함된 2의 개수는 $[\cfrac{n}{2}]+[\cfrac{n}{2^2}]+[\cfrac{n}{2^3}]+\cdots$이고 $2n!$에 포함된 2의 개수는 $[\cfrac{2n}{2}]+[\cfrac{2n}{2^2}]+[\cfrac{2n}{2^3}]+\cdots$이다. 각각을 정수 $r,\ s$라고 가정하면 $s=n+r$로 표현할 수 있고 $n=s-r$이 성립하는데 주어진 식에 따라 $2^{s-r}$은 $\cfrac{2n!}{n!}$의 인수임을 알 수 있다.

$\therefore\ 2^n\ |\ (n+1)(n+2)\cdots(2n-1)2n$이다.

정리: 임의의 실수 $x,\ y\in R$에 대하여, $[x+y]\ge[x]+[y]$이다.

[증명] $x\ge[x],\ y\ge[y]$이므로 $x+y\ge[x]+[y]$가 성립한다. 그리고 $[x+y]\ge[[x]+[y]]$또한 성립하지만 $[[x]+[y]]\in Z$이므로 $[x+y]\ge[x]+[y]$이다.

예제: n개의 연속된 자연수의 곱은 $n!$로 나누어 떨어짐을 증명하여라.

$n$개의 연속된 자연수 중 가장 큰 수를 $k$라 하자. 그러면 $n$개의 연속된 자연수의 곱은 $k(k-1)(k-2)\cdots(k-n+1)$이다.

달리 표현하면 $\cfrac{k(k-1)\cdots(k-n+1)(k-n)\cdots2\cdot1}{(k-n)(k-n-1)\cdots2\cdot1}=\cfrac{k!}{(k-n)!}$이다.

따라서 주어진 조건에 따르면 $\cfrac{k!}{n!(k-n)!}$이 정수임을 증명하면 된다.

주어진 식이 정수임을 증명하기 위해 $n!(k-n)!$이 갖는 임의의 소수 $p$에 대해 $k!$가 소수 $p$를 적어도 같거나 많이 가지면 된다.

• $k!$이 갖는 소수 $p$의 개수

  $[\cfrac{k}{p}]+[\cfrac{k}{p^2}]+[\cfrac{k}{p^3}]+\cdots$

• $n!$이 갖는 소수 $p$의 개수

  $[\cfrac{n}{p}]+[\cfrac{n}{p^2}]+[\cfrac{n}{p^3}]+\cdots$

• $(k-n)!$이 갖는 소수 $p$의 개수

  $[\cfrac{k-n}{p}]+[\cfrac{k-n}{p^2}]+[\cfrac{k-n}{p^3}]+\cdots$

$n!$과 $(k-n)!$이 갖는 소수 $p$의 개수를 합하면 $([\cfrac{n}{p}]+[\cfrac{k-n}{p}])+([\cfrac{n}{p^2}]+[\cfrac{k-n}{p^2}])+\cdots$이 되는데 보조정리를 이용하면 $[\cfrac{k}{p}]\ge[\cfrac{n}{p}]+[\cfrac{k-n}{p}]$이므로 적어도 $n!$과 $(k-n)!$이 갖는 임의의 소수 $p$에 대해 $k!$가 적어도 같거나 더 많이 가짐을 확인할 수 있기 때문에 $\cfrac{k!}{n!(k-n)!}$은 정수이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저