본문 바로가기
Topos Uranos
한국어

위치적 기수법

요약

이 수업은 각 숫자의 값이 그 숫자가 차지하는 자리에 따라 정해지는 위치 기수법을 다룬다. 모든 자연수가 임의의 밑 b≥2b \geq 2에서 오직 한 가지 방식으로 쓰인다는 것을 밑으로 거듭 나누는 절차로 증명하고, 1010진법과 22진법, 88진법, 1616진법 사이에서, 그리고 뒤의 세 진법 사이에서는 이진 숫자를 묶어서 수를 변환하는 방법을 가르친다. 덧셈과 곱셈이 어느 진법에서나 1010진법과 같은 규칙으로 계산됨을 보이고, 배수 판정법이 왜 성립하는지 설명하여 다른 진법으로 확장하며, 기수법의 역사와 컴퓨터에서 22진법의 쓰임에 관한 짧은 글로 마무리한다.

학습 목표

  1. 위치 기수법을 이해하고, 임의의 진법으로 쓰인 수의 값을 계산한다.
  2. bb진법 표현의 존재성과 유일성을 증명하고, 이를 연속된 나눗셈으로 구한다.
  3. 22진법, 88진법, 1010진법, 1616진법 사이에서 수를 변환하고, 22진법으로 덧셈과 곱셈을 한다.
  4. b−1b - 1의 배수 판정법과 b+1b + 1의 배수 판정법(bb진법에서)을 정당화하고, 이를 1010진법과 다른 진법에 적용한다.

위치 기수법

20252025 수를 쓸 때 네 숫자를 더하는 것이 아니라, 각 숫자에 그 자리에 따라 정해지는 1010의 거듭제곱을 곱한다. 첫 번째 22 숫자는 천이 두 개, 두 번째 것은 십이 두 개를 나타낸다. 숫자 00 값은 백이 없음을 나타내며, 그 자리를 차지함으로써 다른 숫자들을 저마다 제자리에 있게 한다.

2025=2⋅103+0⋅102+2⋅10+52025 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10 + 5

이 원리를 위치 기수법이라 하며, 이는 수 1010에 의존하지 않는다. 자연수 b≥2b \geq 2 값을 밑이라 하면, bb진법의 숫자는 수 0,1,…,b−10, 1, \ldots, b - 1 값들이며, 숫자의 열 ak,ak−1,…,a1,a0a_k, a_{k-1}, \ldots, a_1, a_0(단, ak≠0a_k \neq 0)는 다음 수를 나타낸다.

n=akbk+ak−1bk−1+⋯+a1b+a0n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0

숫자는 왼쪽에서 오른쪽으로 나란히 쓰고, 밑은 아래첨자로 나타낸다. 예를 들어 341253412_5 수는 55진법에서 숫자 33, 44, 11, 22로 쓰이는 수이며, 「34123412(55진법)」이라고 읽는다. aia_i 숫자는 자리 ii 값을 차지한다고 하며, 자리는 오른쪽부터 00 값에서 시작하여 센다. 아래첨자가 없으면 수는 1010진법으로 쓰인 것이다. 22진법에는 숫자가 두 개, 곧 00 값과 11 값만 있으며, 이를 비트라 한다. 1616진법에는 열여섯 개의 숫자가 필요하며, 보통의 열 개 숫자에 문자 A, B, C, D, E, F를 더하는데, 이들은 각각 1010, 1111, 1212, 1313, 1414, 1515 값을 나타낸다.

그런데 bb진법으로 쓰인 수의 값은 bb 값을 공통인수로 거듭 묶어 내어 계산할 수 있으며, 이렇게 하면 거듭제곱을 계산하지 않아도 된다. 이것이 호너의 방법이다.

보조정리호너의 방법

모든 kk 값과 모든 수 a0,a1,…,aka_0, a_1, \ldots, a_k에 대하여, 곱 aibia_i b^i 항들의 합은 aka_k 값에서 시작하여 kk 번 다음 연산을 되풀이하면 얻어진다. 곧 bb 값을 곱하고 다음 계수를 더하는 연산이다.

akbk+ak−1bk−1+⋯+a1b+a0=(⋯((akb+ak−1)b+ak−2)⋯ )b+a0a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 = (\cdots((a_k b + a_{k-1}) b + a_{k-2}) \cdots) b + a_0

증명은 분배법칙만 쓰는 kk에 대한 귀납법이다. 이 식은 x=bx = b일 때 다항식 akxk+⋯+a1x+a0a_k x^k + \cdots + a_1 x + a_0 식의 값이며, 다항식의 대수에 관한 수업에서 이를 다시 다룬다.

증명

  1. a0=a0a_0 = a_0

    기초 단계: k=0k = 0일 때 양변은 모두 a0a_0 식이 된다. 이 방법은 아무 연산도 하지 않기 때문이다.

  2. ckbk+⋯+c1b+c0=(⋯(ckb+ck−1)⋯ )b+c0\dato{h}{c_k b^k + \cdots + c_1 b + c_0 = (\cdots(c_k b + c_{k-1}) \cdots) b + c_0}

    귀납 가정: k+1k + 1개의 항으로 이루어지고 계수는 임의이며 거듭제곱 bkb^k 항까지 이어지는 모든 합에 대하여 이 방법이 성립한다.

  3. ak+1bk+1+⋯+a1b+a0=(ak+1bk+⋯+a2b+a1) b+a0a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{(a_{k+1} b^k + \cdots + a_2 b + a_1)} \, b + a_0

    bk+1b^{k+1} 항까지 이어지는 합을 생각한다. 분배법칙에 의하여 마지막 항을 제외한 모든 항에서 bb 값을 공통인수로 묶어 낸다.

  4. ak+1bk+1+⋯+a1b+a0=((⋯(ak+1b+ak)⋯ )b+a1) b+a0a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{((\cdots(a_{k+1} b + a_k) \cdots) b + a_1)} \, b + a_0

    괄호 안의 식은 계수를 ci=ai+1c_i = a_{i+1} 식으로 두면 귀납 가정의 꼴이다. 이 방법으로 그것을 다시 쓰고, bb 값을 곱한 뒤 a0a_0 값을 더하면 k+1k + 1에 대한 방법이 얻어진다. 귀납법의 원리에 의하여 모든 kk에 대하여 성립한다.

예시5진법으로 쓰인 수의 값

55진법으로 341253412_5라고 쓰이는 수를 두 가지 방법으로 계산하여라. 자리의 값을 더하는 방법과 호너의 방법이다.

증명

  1. 34125=3⋅53+4⋅52+1⋅5+23412_5 = \resaltar{3} \cdot 5^3 + \resaltar{4} \cdot 5^2 + \resaltar{1} \cdot 5 + \resaltar{2}

    각 숫자에 그 자리에 해당하는 55의 거듭제곱, 곧 535^3, 525^2, 55, 11 값을 곱한다.

  2. 3⋅125+4⋅25+1⋅5+2=375+100+5+2=4823 \cdot \resaltar{125} + 4 \cdot \resaltar{25} + 1 \cdot 5 + 2 = \resaltar{375} + \resaltar{100} + 5 + 2 = \dato{v}{482}

    거듭제곱과 곱을 계산하고 더한다.

  3. 34125=((3⋅5+4)⋅5+1)⋅5+23412_5 = \resaltar{((3 \cdot 5 + 4) \cdot 5 + 1)} \cdot 5 + 2

    호너의 방법으로, 처음 세 항에서 55 값을 공통인수로 묶어 내고, 이어서 괄호 안의 처음 두 항에서 묶어 낸다.

  4. 3⋅5+4=19,19⋅5+1=96,96⋅5+2=482\resaltar{3 \cdot 5 + 4} = 19, \quad \resaltar{19 \cdot 5 + 1} = 96, \quad \resaltar{96 \cdot 5 + 2} = \resaltar{482}

    안쪽에서 바깥쪽으로 계산한다. 각 결과에 밑을 곱하고 다음 숫자를 더한다. 거듭제곱을 하나도 쓰지 않고 같은 값이 얻어진다.