모듈로 덧셈과 뺄셈

A=14, B=17, C=5라고 합시다.

다음 식이 맞는지 확인해 봅시다: (A + B) mod C = (A mod C + B mod C) mod C
LHS = 식의 왼쪽 변
RHS = 식의 오른쪽 변

LHS = (A + B) mod C
LHS = (14 + 17) mod 5
LHS = 31 mod 5
LHS = 1

RHS = (A mod C + B mod C) mod C
RHS = (14 mod 5 + 17 mod 5) mod 5
RHS = (4 + 2) mod 5
RHS = 1

아래 그림을 봅시다. 아래 왼쪽 원에서 볼 수 있듯이 12+9 mod 7을 계산하기 위해 모듈러 원을 시계방향으로 12+9번을 순서대로 돌면 결과값을 쉽게 계산할 수 있습니다.

모듈러 원에서 7번 돌 때마다 같은 위치로 돌아온다는 사실에서 단서를 찾을 수 있습니다. 이와 같이 모듈러 원을 둘러싸는 완전한 루프는 마지막 위치에 영향을 주지 않습니다. (위의 두 모듈러 원에서 보듯이) 각각의 숫자의 mod 7을 계산하여 원 주위로 완전히 한바퀴를 도는 루프는 무시합니다. 그런 후 남은 숫자는 모듈러 원 주위를 0부터 돌고, 이것이 마지막 위치에 영향을 주는 숫자입니다.

오른쪽 아래 모듈러 원에서 볼 수 있듯이 이제 각 숫자의 최종 위치를 결정할 수 있도록 원 주위로 남은 횟수만큼 돌기만 하면 됩니다. 이 방법은 모든 두 정수와 모듈러 원에 적용할 수 있습니다.

(A + B) mod C = (A mod C + B mod C) mod C를 증명해 봅시다.
여기서는 LHS=RHS라는 것을 보여주어야 합니다.

몫-나머지 정리(quotient remainder theorem)로부터 A와 B를 다음과 같이 쓸 수 있습니다:

A = C * Q1 + R1, 여기서 0 ≤ R1 < C이고 Q1는 정수이다. A mod C = R1
B = C * Q2 + R2, 여기서 0 ≤ R2 < C 이고 Q2는 정수이다. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2

LHS = (A + B) mod C
LHS = (C * (Q1 + Q2) + R1+ R2) mod C
mod C의 성질에 의해 C의 곱은 없앨 수 있다.
LHS = (R1 + R2) mod C

RHS = (A mod C + B mod C) mod C
RHS = (R1 + R2) mod C

모듈러 빼기도 위와 매우 유사하게 증명할 수 있습니다.