mod에 대해 (이산수학 정수론 (1))

이산수학 교과서에 다루는 정도의 정수론을 정리해보고자 한다.

Algorithm 기초 중의 기초 문제를 풀다가 정리하고 넘어갈 필요성을 느꼈다.

예를 들면 수가 너무 커지면 % 100007을 해서 저장을 하곤 하는데, 그때 사용하는 mod 연산 그리고 

최대공약수, 최소공배수 (GCD, LCM) 문제를 풀 때 나오는 Euclidean algorithm (유클리드 호제법)을 정리를 해보려고 한다.

 

교재는 학교 이산수학 강의에서 사용한 Discrete Mathematics and Its Application(8th)를 기준으로 작성하였다.

(I am using definition, theorem and figures from the textbook I mentioned above if there are any problems please le me know)

 

Chapter 4 Number Theory and Cryptography

 

4.1 Divisibility and Modular Arithmetic

 

Figure 1

 

b를 a로 나누어 나누어 떨어질 때 (다른말로 해서 b/a가 정수일 때), | 기호를 써서 나타낸 다는 것을 볼 수 있다. 

 

정수론의 이쪽 part에서는 나누기에 대한 개념을 많이 다루는데, 증명할때, 임의의 정수 b를 b = aq + r의 형식으로 나타내는 것을 많이 볼 수 있을 것이다. 그에 대한 설명이 section 4.1.3에 나타나 있고 정리하면 Figure 2와 같다.

Figure 2

 

Figure 3

Section 4.1.4 에서는 우리가 사용하는 mod라는 것에 대해서 정확한 정의가 나와 있다(Definition 3)

"Congruent"라는 표현이 다음을 나타냄을 Figure 3을 통해서 볼 수 있다.

 

 

 

위에서 a | b 가 b가 a의 배수임을 나타내는 것이라면 Figure 3에서 a ≡ b (mod m)는 m | b-a를 나타낸다. 

한국말로 풀어서 설명하면, a 하고 b는 m으로 나눴을 때의 나머지가 같은 equivalence class라는 것이다.

그러면! 여기서 의문.. mod의 경우 modular operation이라고 해서 여러 컴퓨터 언어에서 '%'에 해당하는 것이라고 배웠는데, 여기서 작대기 3개, mod가 나오는 이것은 뭔가? 할 수 있을 텐데, 그 관계를 아래의 그림(Figure 4)이 설명한다.

 

Figure 4

 

빨간색으로 표시한 표기는 relation을 나타내고, a mod m은 function을 나타낸다. relation과 function의 차이는 이산수학을 통해 배웠을 것이라고 생각하고 넘어간다. 그 둘의 관계는 Figure 4의 Thm 3과 같은데, 증명은 어렵지 않다. 위에서 말한 b = aq + r과 같은 표현을 이용하면 쉽게 할 수 있을 것이다. 

 

Thm 4를 직접 증명해보면서 수학 증명에 대해서 알아보고자 한다.

Figure 5

일단 큰따옴표 표시를 한 if and only if (우리말로 필요충분조건)를 증명하는 경우, 명제가 양쪽 방향으로 성립한다는 것을 보여야한다. 그러므로 증명은 2단계로 이루어진다. 나머지는 계속해서 말한 a = bq + r 표기를 사용하고 있으므로 길지 않은 Figure 5를 살펴보면 쉽게 이해할 수 있을 것이다. 

 

 

가장 중요한 부분 

이 글을 작성하게 된 이유는 알고리즘 풀이를 할 때 값이 overflow가 되는 것을 막기 위해서, % 10007 같은 행위를 하는 것을 보고, 아무 곳에나 %10007을 하는 것이 아니라 확실하게 필요한 곳에만 붙여주기 위함이라 밝힌 바 있다.

 

Figure 6

Figure 6의 Corollary가 mod 연산의 특성을 보여준다. 특히 알고리즘을 막 시작한 내가 많이 마주하게 된 형식은 덧셈으로 이루어진 꼴인것 같은데, 증명을 직접 해보면서 확실하게 개념을 잡아 보는 것이 좋을 것 같다. 마지막 연결고리는 Thm 5인데, 아래에 첨부한다. 

Figure 7

+4.4에도 congruence에 관한 내용이 있는데, 알고리즘 문제를 더 풀어나가다가 또 마주치면 정리해보도록 하겠다.