정수론, 그 열네 번째 이야기 | n 진법 표현

 

합동이론은 어떤 정수를 나누어떨어지게 하는 수를 찾는 데에서 응용될 수 있다.

우리는 보통 나누어떨어지는 것을 10진법 하에서 판별하게 된다.

그러나 10진법이 아닌 다른 진법에서 유용한 성질들이 발견되는 경우도 있다.

그렇기 때문에, 다음 정리를 먼저 살펴보자.

 

모든 양의 정수 $N$ 은 주어진 정수 $b>1$ 에 대해 다음과 같이 유일하게 나타난다. $$N=a_m{b}^m+a_{m-1}{b}^{m-1}+\cdots +a_2{b}^2+a_{1}b+a_0$$     단, $i=0,1,2,\cdots m$ 에 대해 $a_i$ 는 $0\le a_i<b$ 인 정수이다.

 

Proof :

나눗셈 정리에 의해 정수 $q_1,a_0$ 가 존재하여 $N=q_{1}b+a_0$ 로 쓸 수 있다. (단, $0\le a_0<b$ )

 

만약 $q_1\ge b$ 이면, 다시 나눗셈 정리에 의해 정수 $q_2,a_1$ 이 존재하여 $q_1=q_{2}b+a_1$ 로 쓸 수 있다.

(단, $0\le a_1<b$ )

 

여기서도 $q_2\ge b$ 이면 같은 방법을 계속할 수 있다.

그러나 $q_i$ 의 수열은 $N>q_1>q_2\cdots \ge 0$ 이므로 무한히 길 수 없다.

이를 구체적으로 $(m-1)$ 단계에서 끝났다고 하자.

 

$0\le q_m<b$ 이므로, $a_m=q_m$ 이라고 놓으면

이 때, $N=a_m{b}^m+a_{m-1}{b}^{m-1}+\cdots +a_{1}b+a_0$ 로 표현되고

각각의 계수들은 모두 $0$ 이상, $b$ 미만이다.

 

이제 표현 방식의 유일성을 보이자. $N$ 이 두 가지 표현방식을 가진다면 아래처럼 표현된다. $$N=a_m{b}^m+a_{m-1}{b}^{m-1}+\cdots +a_{1}b+a_0=c_m{b}^m+\cdots +c_{1}b+c_0$$ 이 때, 양 변이 모두 $b^m$ 까지 있는 이유는 상황에 따라 계수를 $0$ 으로 정하여도 상관없기 때문이다.

 

이제 $d_i=a_i-c-i$ 라고 놓으면, $d_m{b}^m+\cdots +d_{1}b+d_0=0$ 를 얻는다.

그런데 두 가지 표현이 다르다고 가정하였으므로 어떤 정수 $i$ 에 대해 $d_i\ne 0$ 이어야 한다.

 

이제 $d_i\ne 0$ 인 최소의 $i$ 를 $k$ 라고 하면, $d_m{b}^m+\cdots +d_{k+1}{b}^{k+1}+d_k{b}^k=0$ 을 얻는다.

 

양 변을 $b^k$ 로 나누면, $d_k=-b(d_m{b}^{m-k-1}+\cdots +d_{k+1})$ 이 되는데, 이는 $b\mid d_k$ 임을 의미한다.

 

그런데 $0\le a_k,c_k<b$ 에서 $|a_k-c_k|=|d_k|<b$ 를 얻는다. 이는 $d_k=0$ 을 의미하는데

$d_k\ne 0$ 이므로 이는 모순이다.

 

따라서 귀류법에 의해, $N$ 의 표현방식은 유일하게 존재한다.

 

 

따라서, 우리는 $N$ 을 $b$ 의 거듭제곱들을 적절히 더해 표현할 수 있음을 알았다.

이 때, 이를 간단하게 표현하기 위하여 $N={(a_m{a}_{m-1}\cdots a_2{a}_1{a}_0)}_b$ 로 쓰기도 한다.

 

이것의 우변은 $b$ 의 거듭제곱들로 표현했을 때 각각의 계수를 의미하는 것으로

저렇게 표기한 것을 우리는 $N$ 의 $b$ 진법 표현이라고 한다.