수학 나머지 연산(Modular arithmetic)

수학 나머지 연산(Modular arithmetic)을 알아보겠습니다.

​
나머지 연산이란 어떤 숫자를 나누고 남은 나머지를 말합니다. 보통 나눗셈은 몫을 구하는 용도인데요. 나머지 연산은 나머지에 관심을 가져주는 연산입니다.
​
​
표현은 아래와 같이 합니다.
24를 11로 나눴을 때 나머지는?

답은 2입니다.

11 * 2 + 2

​

​

아래와 같이 같은 나머지를 가지는 두 나머지 연산이 있습니다.

이 둘은 합동(Congruence)라고 하며, 다음과 같이 표기합니다.

합동 관계는 다음과 같은 특징이 있습니다.

a = b + km

a - b = km

즉 두 숫자를 뺀 값이 m의 배수가 되면 됩니다.

위의 24 ≡ 35 (mod 11)의 경우 35 - 24 = 11이 되어 1 x 11이 되므로 합동 관계가 맞습니다.

​

​

음수에 대한 나머지 연산의 경우 다음과 같이 구합니다.

-24보다 큰 11의 배수를 더합니다. 여기선 33이 크네요. 그러면 3*11 - 24 = 9

즉 9 mod 11과 같습니다.

​

나머지 연산의 산술 특징을 알아봅시다.

두 수의 합 나머지 연산은 각 각의 나머지 연산 더하기 나머지 연산을 한 것과 같습니다.

(A + B) mod M = (A mod M + B mod M) mod M

​

예시

25 mod 11 = (11 mod 11 + 14 mod 11) mod 11

25 mod 11 = 3

(0 + 3) mod 11 = 3

​

증명은 다음과 같습니다.

(1)과 (2)가 같다는 걸 확인했습니다.

​

​

뺄셈도 적용됩니다.

(A - B) mod M = (A mod M - B mod M) mod M

​

증명은 다음과 같습니다.

(1)과 (2)가 같다는 걸 확인했습니다.

​

​

​

곱셈에도 적용됩니다.

(1)과 (2)가 동일한 것을 확인했습니다.

​

​

​

아쉽게도 나눗셈에는 적용되지 않습니다.

나눗셈은 나머지 연산의 역원을 구해서 곱셈으로 구해야 합니다.

나머지 연산의 역원은 다음 시간에 다뤄보겠습니다.

​

​

​

끝.

카테고리: Math