신촌우왕 소개

수학자, 천재작곡가, 요가수행자

계산기를 만들기 위해

필요한 가장 기본적인 지식은

나눗셈의 몫과 나머지에 대한 지식이다.

파이썬 계산기(15):

두 정수 나눗셈 일반화

두 정수 간 나눗셈의 몫과 나머지 구하기는

<실수의 나눗셈 정리>에 대한 일종의 축약으로

<정수의 나눗셈 정리>라 불리운다.

이론적으로는 b/a의 값에 의존하여

몫과 나머지를 구하여야 하나

분수 계산에 오류가 동반되는 경우가 많으므로

뺄셈법(혹은 덧셈법)을 이용하여

몫과 나머지를 구하게 된다.

다만 뺄셈법은 빼는 회수가 기하급수적으로 증가하므로

특별한 방법을 동원하여 빼는 회수가 산술적으로 증가하게끔 전환한다.

q(b, a) = Q, r(b, a) = R

이제

두 양의 정수 a, b에 대하여

b를 a로 나누었을 때

정수 몫 q(b, a) = Q,

나머지 r(b, a) = R이라 하자.

이때 (-b, a), (b -a), (-b, -a)와 같은 경우에

어떻게 Q, R을 이용하여 나타낼 수 있는 지 살펴본다.

<실수의 나눗셈 정리>에서 밝혔듯이

다음 경우의 수를 이용하여

모두 해결할 수 있다.

b = aq + r

0 ≤ r < ｜a｜

일종의 q에 대한

절대부등식으로 생각해도 된다.

r = 0인 경우

b = aq + r에서

q = b/a임은 분명하다.

R = 0인 경우:

q(-b, a) = (-b)/a = - b/a = -Q

r(-b, a) = 0

q(b -a) = b / (-a) = - b/a = -Q

r(b, -a) = 0

q(-b, -a) = (-b)/(-a) = b/a = Q

r(-b, -a) = 0

R ≠ 0인 경우:

q(-b, a) = -q(b, a) - 1 = -Q-1

r(-b, a) = -r(b, a)+a = -R+a

q(b -a) = -q(b, a) = -Q

r(b, -a) = r(b, a) = R

q(-b, -a) = Q+1

r(-b, -a) = -R+a

(증명)

q(-b, a)의 경우 몫에 대해서만 증명을 보인다.

a>0이고 r≠0이므로

b/a - 1 < Q ≤ b/a에서 등호가 제거되어야 한다.

b/a - 1 < Q < b/a …①

이제 b 대신 -b를 대입했을 때

몫을 q라 하면

(-b)/a - 1 < q < (-b)/a …②

①식에 -1을 곱하면

-b/a < -Q < -b/a + 1

1을 빼면

-b/a - 1 < -Q - 1 < -b/a …③

②, ③은 같은 범위이고

그 범위 내에서 정수는 유일하므로

q = -Q - 1

Code