뺄셈의 나머지 연산에서 더하기 나머지를 하는 이유

알고리즘에서 나머지 연산은 연산의 값이 너무 커져서 자료형으로 담기 어려울 때, 각 연산마다 나머지 연산을 하여 자료형 안에 담기 위하여 사용한다

 

덧셈, 곱셈, 뺄셈은 성립하지만 나눗셈의 경우 성립하지 않는다. (나눗셈의 경우는 modular inverse를 구해야 한다)

 

그리고 주의할 점은 뺄셈의 경우 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 한 번 더하는 과정이 필요하다

 

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

 

그 이유는 무엇일까? M을 더해도 전체 식에 영향은 없는 것인가?

 

나머지 연산에서 음수가 나오는 예시를 먼저 본다

$(6-5) mod 3 = 1 mod 3 = 1$ 이다

 

만약 $(6 mod 3-5 mod 3) mod 3 = (0 - 2) mod 3 = -2 mod 3 = ?$ 이면 문제가 된다

 

음수의 경우 결과 부호가 프로그래밍 언어마다 다르다

위의 경우 C11, C++14, Java에서는 -2를 반환할 것이고, 파이썬에서는 1을 반환한다

그런데 애초에 우리가 원하는 결과는 음수가 아니다

 

범위를 생각해 본다

$0 \leq a mod c < c$ 이고, $0 \leq b mod c < c$ 이다

그러면 $(a mod c - b mod c)$ 의 결과는 $-c < (a mod c - b mod c)< c$ 를 만족한다

 

여기서 -c가 문제니까 양측에 c를 더한다

이제 식은 다음과 같다 $0<amodc-bmodc +c<3c$

 

이제 전체 식은 0보다 큰 값을 갖기 때문에 이 상태에서 다시 c로 나눠주면 원하는 결과를 얻을 수 있다

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