정수론, 그 열네 번째 이야기 | 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\leq a_i < b$ 인 정수이다.

 

Proof :

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

 

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

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

 

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

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

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

 

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

이 때, $N = a_m b^m + a_{m-1}b^{m-1} + \cdots + a_1b + 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_1b + d_0 = 0$ 를 얻는다.

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

 

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

 

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

 

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

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

 

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

 

 

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

이 때, 이를 간단하게 표현하기 위하여 $N = \left ( a_ma_{m-1}\cdots a_2a_1a_0 \right )_b$ 로 쓰기도 한다.

 

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

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