모듈러 연산.

모듈러 연산(mod %)

정의
A를 B로 나누었을 때의 결과(몫이 Q이고 나머지가 R)이라고 하자.

A / B = Q,
A %(mod) B = R

A = BQ + R

 

10 mod(%) 4는

원을 4등분 시키고 12시 지점을 0으로 잡고 10만큼 이동하면 도착하는 곳의 숫자 "2"

즉 2바퀴 돌고 2번 더감

10 = 2*4 + 2

 

합동
A mod C = B mod C 이면 합동(A ≡ B(mod C))이다.


(A-B)(mod C) = 0

5 mod 7 = 5
12 mod 7 = 5
19 mod 7 = 5

특징
대칭성 : A ≡ B(mod C)이면 B ≡ A(mod C)
추이성 : A ≡ B(mod C)이고 B ≡ D(mod C)이면 A ≡ D(mod C)

알고리즘에 필요한 지식

(A+B) mod C =(A mod C + B mod C) mod C
(A-B) mod C =(A mod C - B mod C) mod C
(A*B) mod C =(A mod C * B mod C) mod C

* 나눗셈은 성립하지 않음.