자연계열 5번

제시문 2

(가) 큰 자연수를 나타낼 때, 어떤 수의 거듭제곱을 사용하면 편리한 경우가 있다. 예를 들어, 30400000은 오른쪽 끝으로부터 연속하여 5개의 0이 나타나므로 10의 거듭제곱을 이용하여 나타내면 $\displaystyle 30400000=304\times10^5$이다. 다른 경우로 $\displaystyle 29282$는 11의 거듭제곱을 이용하여 $\displaystyle 29282=2\times11^4$과 같이 나타낼 수 있다.

자연수 100의 팩토리얼, 즉 $\displaystyle 100!=100\times99\times98\times\cdots\times2\times1$을 계산하여 십진법 수로 표현했을 때, 오른쪽 끝으로부터 연속하여 나타나는 0의 개수를 구하여 보자. 1에서 100까지의 수 각각을 소인수분해할 때, 소인수 5는 5의 배수마다 한 번씩 나오고, 또 5²의 배수마다 한 번씩 더 나오므로, $\displaystyle 100!$의 소인수분해에 나타나는 2의 지수를 $\displaystyle p$, 5의 지수를 $\displaystyle q$라고 하면, $\displaystyle q=\left[\frac{100}5\right]+\left[\frac{100}{25}\right]=20+4=24$이고, $\displaystyle p>q$이다. (이 식에서 기호 $\displaystyle [x]$는 $\displaystyle x$ 이하의 정수 중 가장 큰 것을 뜻한다.) 따라서 $\displaystyle 100!$의 약수 중에서 10의 거듭제곱 꼴로서 지수가 가장 큰 것은 $\displaystyle 10^q=10^{24}$이고, $\displaystyle 100!$의 십진법 수 표현에서 오른쪽 끝으로부터 연속하여 나타나는 0은 24개이다.

(나) 수를 표현하는 다른 방법으로 12진법을 생각해보자. 예를 들어, 12진법으로 표현한 네 자리 수 $\displaystyle abcd_{(12)}$는 십진법 수로 $\displaystyle abcd_{(12)}=a\times12^3+b\times12^2+c\times12+d$와 같이 계산된다. 어떤 자연수를 12진법 수로 표현했을 때 오른쪽 끝으로부터 연속하여 나타나는 0의 개수를 구하려면, 그 자연수의 약수 중에서 $\displaystyle 12^r$ 꼴로서 지수 $\displaystyle r$이 가장 큰 것을 찾아야 한다.

이제, $\displaystyle 100!=100\times99\times98\times\cdots\times2\times1$을 12진법 수로 표현했을 때 오른쪽 끝으로부터 연속하여 나타나는 0의 개수를 구해보자. $\displaystyle 12=2^2\times3$이므로, $\displaystyle 100!$의 소인수분해에 나타나는 2의 지수 $\displaystyle p$, 3의 지수 $\displaystyle q$를 구해보면 다음과 같다.$\displaystyle p=\left[\frac{100}2\right]+\left[\frac{100}4\right]+\left[\frac{100}8\right]+\left[\frac{100}{16}\right]+\left[\frac{100}{32}\right]+\left[\frac{100}{64}\right]=50+25+12+6+3+1=97$$\displaystyle q=\left[\frac{100}3\right]+\left[\frac{100}9\right]+\left[\frac{100}{27}\right]+\left[\frac{100}{81}\right]=33+11+3+1=48$따라서 $\displaystyle 100!$의 약수 중에서 12의 거듭제곱 꼴로서 지수가 가장 큰 것은 $\displaystyle 12^{48}$이고, $\displaystyle 100!$의 12진법 표현에서 오른쪽 끝으로부터 연속하여 나타나는 0은 48개이다.

(다) 0 이상의 정수를 표현하는 방법으로 $\displaystyle 1!$의 자리, $\displaystyle 2!$의 자리, $\displaystyle 3!$의 자리, $\displaystyle 4!$의 자리, $\displaystyle \cdots$ 등을 사용하는 팩토리얼 진법이 있다. 팩토리얼 진법의 $\displaystyle n$자리 수 $\displaystyle (a_na_{n-1}\cdots a_2a_1)_{(!)}$는 십진법 수로 $\displaystyle (a_na_{n-1}\cdots a_2a_1)_{(!)}=\sum_{k=1}^n a_k\times k!$과 같이 계산된다. 여기에서 가장 높은 자리인 $\displaystyle n!$의 자리의 수 $\displaystyle a_n$은 $\displaystyle 1,2,\cdots,n$ 중 하나이고, $\displaystyle k<n$이면 $\displaystyle k!$의 자리의 수 $\displaystyle a_k$는 $\displaystyle 0,1,2,\cdots,k$ 중 하나이다.예를 들어, $\displaystyle 1320_{(!)}=1\times4!+3\times3!+2\times2!+0\times1!=24+18+4=46$을 나타낸다. 그리고 팩토리얼 진법으로 표현한 네 자리 수 가운데 가장 큰 자연수는$\displaystyle 4321_{(!)}=4\times4!+3\times3!+2\times2!+1\times1!=96+18+4+1=119$이다. 팩토리얼 진법에서 $\displaystyle 10!$의 자리 이상은 그 자리의 수가 10 이상이 될 수 있으므로, $\displaystyle 10,11,12,\cdots$를 다른 기호, 예를 들어 알파벳 A, B, C, $\displaystyle \cdots$ 등으로 나타내어 $\displaystyle \mathrm{BA070000010}_{(!)}=11\times11!+10\times10!+7\times8!+1\times2!$과 같이 표현한다. 하지만 자리가 높아질수록 그 자리에 쓸 수 있는 수들을 나타낼 기호가 점점 더 많이 필요하게 된다는 단점이 있다.하나의 자연수에 대한 팩토리얼 진법 표현은 유일하다. 이 사실은 팩토리얼 진법으로 표현된 $\displaystyle n$자리 수 $\displaystyle P$는 $\displaystyle n$이 아닌 다른 개수의 자리들로는 표현할 수 없음을 보이고, 이후 $\displaystyle P$가 $\displaystyle n$자리의 다른 팩토리얼 진법 표현을 가진다고 가정하면 모순이 생김을 보임으로써 증명할 수 있다.

[문제 5]어떤 자연수 $\displaystyle P$에 대하여 다음과 같이 서로 다른 두 가지 팩토리얼 진법 표현이 존재한다고 가정하자.$\displaystyle P=(a_na_{n-1}\cdots a_2a_1)_{(!)}=\sum_{k=1}^n a_k\times k!\qquad\cdots\cdots\cdots\ (1)$$\displaystyle P=(b_nb_{n-1}\cdots b_2b_1)_{(!)}=\sum_{k=1}^n b_k\times k!\qquad\cdots\cdots\cdots\ (2)$그러면 (1)과 (2)의 두 표현에서 같은 자리의 수를 비교할 때 서로 다른 값이 나오는 자리가 있어야 한다. 이 중 가장 높은 자리를 $\displaystyle m!$의 자리라고 하자. 즉, $\displaystyle a_m\ne b_m$이고, $\displaystyle k>m$인 $\displaystyle k$가 있다면 $\displaystyle a_k=b_k$이다.이 사실과 [문제 4]에서 증명한 식을 이용하여, (1)의 가장 오른쪽 변과 (2)의 가장 오른쪽 변의 차가 0이 되지 않는 모순이 있음을 보이시오.