02.정수, 정수의 나누어짐

정수란?

정수는 자연수(1,2,3...)와 이들의 음수(-1,-2,-3...), 그리고 0(zero)으로 이루어진 수 체계이다.

정수는 덧셈, 뺄셈, 곱셈에 대해 닫혀있고, 나눗셈에 대해서는 닫혀있지 않다.

정수가 어떤 것인지는 그리 중요하지도 않고 헷갈리지도 않을 것이다. 하나 둘 셋...이렇게 셀 수 있는 수이고, 0.5 등 소수는 정수가 아니다는 정도면 알고있으면 될 것이다.

'닫혀있다'는 것은, 연산의 결과값이 역시 정수라는 것이다.

덧셈에 대해서 닫혀있다는 것은, 임의의 두 정수 a, b에 대해, 그 두 수를 더한 (a+b)값 역시 정수라는 것이다.  당연한 말이다. 아주 큰 두 수를 더하더라도, 정수는 무한대이기에(큰 쪽으로든 작은 쪽으로든) 그 더 커진 수는 역시 정수인 것이다. 

곱셈과 뺄셈에 대해서도 마찬가지로 그 결과값은 정수이기에 닫혀있다고 말할 수 있다.

나눗셈에 대해서는 닫혀있지 않은데, 예를 들어 1/2=0.5로, 연산 결과값이 0.5로 정수가 아니므로 나눗셈에 대해서 닫혀있다고 할 수 없는 것이다.

a | b 는 "b는 a로 나누어진다"를 의미한다.

정수 a(a≠0)와 b가 어떤 정수 c에 대해 b=ac 일 때, 'a가 b를 나눈다' 혹은 'a는 b의 약수이다'라고 하고, a|b 로 표현한다. (a divide b)

알고리즘에 대한 수학적인 설명에서 종종 a|b라는 표현을 보게 될 것이다. 이것은 'b는 a에 의해 나눠질 수 있다'는 뜻이다. 예를 들어 12=3·4 이므로, 3 | 9 라고 쓸 수 있고, '3은 9의 약수이다'라고 할 수 있다. 

a | b 처럼 약수a를 먼저 표기하는 것은, 영어 표현으로 'a divide b'이기에 그런거 같다. 해서, a | b라는 표현은 'a divide b'로 외워 두는게 편할 듯 하다.

 나눗셈 알고리즘(The Division Algorithm)

(나눗셈 정리)

a,b를 임의의 양의정수라고 할 때, 아래 식을 만족하는 유일한 q와 r이 반드시 존재한다. 

                          b = aq + r, r<a

초등학교때 배우는 나눗셈에 대한 당연한 얘기를 복잡하게 얘기하는 것이다. 

예를 들어, 16을 3으로 나누면, 몫이 5이고 나머지가 1이되는데, 이것을 위의 식으로 표현하면 16 = 3·5 + 1 이 된다.

당연한 얘기를 '나눗셈정리'라는 거창한 이름으로 소개하는 것은 다음의 몇 가지 이유때문이다.

• 어떤 정수에 대해서도 aq + r 로 표현할 수 있고, 이를 만족하는 q와 r이 유일하게 한 쌍만 존재한다는 것은, 정수론의 다른 성질들을 유도하고 이해하는데 많은 도움을 주는 성질이다.
• 암호화알고리즘에 모듈러연산이 많이 사용되는데, 모듈러 연산이라는 것은 '나머지'만을 관심으로 가지는 연산이고, '나머지'라는 것의 수학적인 표현은 위 식에서 처럼 b = aq + r, r<a 로 표현되기 때문이다. 

나머지

놀랍게도, 나머지에 대한 정의는 여럿 존재한다.

1)Euclidean division에 의한 2)일반 계산기에 구현된 3)Mod 4)Nearest

Euclidean

Euclidean division은 바로 위 '나눗셈 알고리즘'에서 살펴본 나눗셈 정리이다. 

a>0, b>0 인 정수일 때, 다음식을 만족하는 몫q와 나머지 r인 정수 존재

a/b = aq + r, 0 <= r < a

이 정리는 기하학에서는 사용할 수 있지만 일반적인 정수 전부에 대해서 적용할 순 없다. a와 b가 전부 양수인 경우에 대해서만 정의되어 있기 때문이다.

해서, 일반적인 계산기, 프로그래밍 언어(c,java 등)에서는 모든 정수에서 성립하도록, 정수의 나눗셈에 대한 몫과 나머지가 정의되어 있다.

일반 계산기에 정의된 정수의 나눗셈

두 정수 a,b가 있을 때, a/b = aq +r을 만족하는 두 정수 q와 r이 존재하고,

q = trunc(a/n), r=a-nq

Eulidean나눗셈이 두 양수에 대한 나눗셈 연산이 가능함에 반해, 음수인 값에 대해서도 정의된것이다.

예를 들어 보면,

a	b	a/b	q	r
13	4	3.25	3	1
13	-4	-3.25	-3	1
-13	4	-3.25	-3	-1
-13	-4	3.25	3	-1

 

위 표를 세밀히 보면 다음과 q와 r의 부호에 대해 다음과 같은 규칙성을 발견할 수 있다.

q의 부호 = (a x b)의 부호

r의 부호 = a의 부호

Modulation연산

java의 BigInteger에 구현된 mod연산의 결과는 항상 양수이다. 즉, 나머지가 항상 양수가 되도록 정의된 것이다.

두 정수 a,b가 있을 때 a/b의 몫 q와 r은 다음과 같다.

if b>0, q=floor(a/b)

  b<0, q=ceiling(a/b)

r=a - |b| x floor(a/|b|)

floor는 작은 정수값으로 내림하는 것이고, ceiling은 큰 쪽 정수값으로 올림하는 것이다.

floor(2.1) = 2, floor(2.5) = 2, floor(2.9)=2

floor(-2.1)=-3, floor(-2.5)=-3, floor(-2.9)=-3

ceiling(2.1) = 3, ceiling(2.5) = 3, ceiling(2.9)=3

ceiling(-2.1)=-4, ceiling(-2.5)=-4, ceiling(-2.9)=-4

Calculator에 의한 나머지 r0를 이미 알고 있을 때에는 mod값을 다음과 같이 구할 수 있다.

if(r0 < 0) r = r0 + |b|

Nearest에 의한 연산

Nearest는 나눗셈의 결과인 실수에 가장 가까이 있는 정수값을 취하는 것이다.

즉, nearest(3.2)=3  nearest(3.8)=4, nearest(-3.2)=-3, nearest(-3.8)=-4

두 정수의 중간값의 경우에는 반올림에서와 같이 큰 쪽 정수가 된다.

nearest(3.5)=4, nearest(-3.5)=-3

nearest의 정의를 수식으로 나타내면 다음과 같다. 

두 정수 a,b가 있을 때, a를 b로 나눈값에 대한 nearest정수의 범위는 (a/b - 0.5, a/b + 0.5]

정수에 대한 나눗셈 연산함수만 존재할 때 nearest를 구하는 방법은 다음과 같다.

nearest(a,b) = floor(a/b + 0.5) = floor( (2a+b)/2b)

다음은, 각 경우별 몫과 나머지 계산값이다.

 

			calculator's		Mod 연산		Nearest
a	b	a/b	q0	r0	q	mod	q	r
13	4	3.25	3	1	3	1	3	1
13	-4	-3.25	-3	1	-3	1	-3	1
-13	4	-3.25	-3	-1	-4	3	-3	-1
-13	-4	3.25	3	-1	4	3	3	-1
15	4	3.75	3	3	3	3	4	-1
15	-4	-3.75	-3	3	-3	3	-4	-1
-15	4	-3.75	-3	-3	-4	1	-4	1
-15	-4	3.75	3	-3	4	1	4	1
14	4	3.5	3	2	3	2	4	-2
14	-4	-3.5	-3	2	-3	2	-3	2
-14	4	-3.5	-3	-2	-4	2	-3	-2
-14	-4	3.5	3	-2	4	2	4	2

 

-끝-