(a+b)%c = (a%c+b%c)%c 증명

기본 사칙연산 이외에 나머지를 구하는 mod 연산자 % 가 여러 program language 에 많이 사용된다.

알고리즘을 보다가 (a+b)%c = (a%c+b%c)%c 가 맞는걸로 바로 넘어가서 저게 과연 맞는것일까 하는 의문이 들었다.

일단 mod 연산자에 대한 분배법칙은 성립하지 않는다.

즉, (a+b)%c != (a%c + b%c) 이다.

 

하지만 (a+b)%c = (a%c+b%c)%c 은 성립한다. 이를 입증할 수 있는 간단한 증명을 메모해둔다.

 

 증명대상 : (a+b)%c = (a%c+b%c)%c
 A = kc + n
 B = k'c + n' 로 치환한다.
 위 치환식을 좌우에 대입
 (kc+n + k'c + n')%c = ((kc+n)%c + (k'c+n')%c)%c
  (k+k') = m 로 정의하고 (XZ + Y)%Z = Y%Z 이므로 (mc + n + n')%c = (n+n')%c 이 성립한다.