Modular 연산에 대해 알아보자!

나머지 연산(Modular)

---

 이번에는 모듈러 연산에 대해 알아보려고 합니다. 모듈러 연산은 어떤 정수 a가 주어졌을 때 이를 0이 아닌 정수 b로 나눈 나머지를 구하는 연산입니다. 기호로는 mod를 사용합니다. 예를 들어 10을 3으로 나눈 나머지가 알고 싶다면 10 mod 3 = 1과 같은 방식으로 표현합니다. 이 나머지 연산은 코딩 문제를 풀면서 결과값이 커지는 걸 방지하기 위해 많이 사용하는데 나머지 연산에는 재미있는 규칙이 숨어 있습니다.

 

나머지 연산의 분배 법칙

---

 나머지 연산에는 3가지 연산에 대해 분배 법칙이 존재합니다.

1. (A + B) mod p = ((A mod p) + (B mod p)) mod p
2. (A - B) mod p = ( (A mod p) - (B mod p)) mod p
3. (A * B) mod p = ((A mod p) * (B mod p)) mod p

 우리는 한번 의심해 볼 필요가 있습니다. 정말 위 법칙이 적용될까? 우리는 증명을 통해 그 궁금증을 해결해보도록 하겠습니다. 먼저 증명하기에 앞서 나머지 정리에 대해 소개해 드리도록 하겠습니다.

 

나머지 정리(remainder theorem)

---

 나머지 정리는 우리가 고등학교 때 다항식에 대한 나머지 정리라는 이름으로 배운 적이 있을 것입니다. 여기서는 정수에 대해서만 얘기하도록 하겠습니다. 나머지 정리란 어떤 정수 a, q, r과 0이 아닌 정수 b가 있고 a ≥ b일 때, a = b * q + r을 만족하는 유일한 정수 q, r이 존재한다는 정리입니다. 예를 들어 a = 7, b = 3이면 10 = 3 * 2 + 1이라는 형태로 나타낼 수 있습니다.

 

나머지 연산의 분배 법칙 증명

---

그러면 나머지 연산의 분배 법칙에 대해 증명해보도록 하겠습니다.

1번 증명

먼저, (A + B) mod p = ((A mod p) + (B mod p)) mod p에 대해서 증명해보도록 하겠습니다.

우리는 나머지 정리를 이용해 A = a * p + r1이라는 형태로 나타낼 수 있습니다. B 또한 B = b * p + r2라고 나타낼 수 있습니다. 그러면 (A + B) mod p = ( (a * p + r1) mod p + (b * p + r2)  mod p) mod p 형태로 나타낼 수 있습니다. 괄호 안에 있는 식을 p로 묶어서 정리하면 ((( a + b ) * p + r1 + r2) mod p) mod p로 나타날 수 있습니다. 우리는 mod 연산을 하면 (a + b) * p가 소거된다는 것을 알고 있고 결국 r1 + r2만 남아 결과적으로 (r1 + r2) mod p와 동일해집니다. r1와 r2는 각각 A mod p와 B mod p의 결과입니다. 그러므로 위 식이 성립된다는 것을 알 수 있습니다.

 

2번 증명

2번에 경우도 부호만 바뀌고 증명 과정은 위와 동일합니다.

 

3번 증명

(A * B) mod p = ((A mod p) *(B mod p)) mod p도 간단하게 풀어보겠습니다. 먼저 A = a * p + r1, B = b * p + r2으로 치환해서 전개해보면 ((a * p + r1) * (b * p + r2)) mod p = (a * b * p^2 + a * r2 * p + b * r1 * p + r1 * r2) mod p가 됩니다. 이 식은 덧셈의 분배 법칙에 따라 분배할 수 있고 p로 묶이는 항들은 mod 연산을 통해 0이됩니다. 남은 항은 r1 * r2 이고 이는 A, B 각각에 mod 연산을 한 결과를 곱한 것과 같습니다. 그렇기에 (A * B) mod p = ((A mod p) * (B mod p)) mod p가 성립합니다.

 

 

 

 

나눗셈에 대한 분배 법칙

---

위에서 보여드린 분배 법칙에는 나눗셈에 대한 내용이 존재하지 않습니다. 이 부분은 조금 더 보강해서 올리겠습니다!