모듈러연산

모듈러 연산의 특징

1.[(a mod n)+(b mod n)] mod n = (a+b) mod n

2.[(a mod n)-(b mod n)] mod n = (a-b) mod n

3.[(a mod n)*(b mod n)] mod n = (a*b) mod n

위처럼 덧셈 뺄셈 곱셈에 대해서는 대체로 마구 적용해도 된다.

주의할점

나눗셈에 대해서는 적용안되는것 주의

일반적인 덧셈 말고 concatenation의 경우는 조심해야한다.

예를 들어 38과 427이 있을때 이 둘을 이어붙이 38427이라는 숫자에 대해서 mod 연산을 한다고 해보자.

$38 \times 10^3 + 427$ 이므로 $(38 \mod K) * (10^3 \mod K) + (427 \mod K)$ 이런건 가능하다.. 

만약 K가 8라고 한다면 $(38 \mod 8)*(10^3 \mod 8)+(427 \mod 8) = 6*0+3 = 3$이고 

$3 \mod K=3$인데 원래수인 $38427 \mod K=3$이므로 같은 걸 알수 있다.

그런데 $38 \mod 8=6$이고 $427 \mod 8=6$라고 해서 6과 6를 이어붙여서(concatenation) 66로 만들게 되면 $66 \mod K=2$이므로 같지 않은걸 알 수 있다.

이 문제에서 해당 부분을 연습할 수 있다.