합동식(modular)을 왜 쓰는 걸까???

합동식이란 원래 수학, 그 중에서도 정수론 분야에서 쓰였다.

그러나 합동식을 이용하서 알고리즘 작성이 매우 용이할 때가 있다. 먼저 합동식에 대한 기본적인 성질에 대해 알아 보자.

( 합동식의 증명은 수학과의 영역이므로, 증명은 여기서 생략을 한다.)

 

(1) 덧셈, 뺄셈, 곱셈에 관련된 성질

덧셈, 뺄셈에 관련된 성질

-> 쉽게 말해 a와 b로 m으로 나눈 나머지가 같고 c와 d를 m으로 나눈 나머지가 같으면 a ± c 와 b ± d 를 m으로 나눈 나머지도 같다는 의미이다. 예를 들면 49 ≡ 1 (mod 8)이고 37 ≡ 5 (mod 8)일 때 위의 성질에 의하여 86 ≡ 6 (mod 8)임을 알 수 있다.

곱셈에 관련된 성질

-> 위의 성질과 별로 다른 점이 없다. 곱셈에 대해서도 똑같은 논리가 적용된다. 예를 들면 33 ≡ 5 (mod 7)이고 122 ≡ 17 (mod 7)일 때 위의 성질에 의하여 4026 ≡ 85 (mod 7)임을 알 수 있다.

 

(2) 거듭 제곱에 관련된 성질

                                                           거듭 제곱에 관련된 성질

 

 

합동식의 활용 예

 합동식의 성질을 활용하면 다음과 같이 일반적으로는 계산하기 힘든 문제도 간단하게 해결할 수 있다. 

ex) 3^333의 1의 자리수를 구하시오

우선 거듭 제곱에 관련된 모듈러 산술의 성질을 이용하여 접근하기 위해 작은 숫자부터 규칙성을 찾아보자

3 ^ 4 ≡ 1 (mod 10)(3^x % 10 == 1이 되는 최소x를 찾는 것이 포인트) 

--> (거듭 제곱의 성질을 적용하면) 3 ^ 332 ≡ 1 ^ 83 (mod 10) == 3 ^ 332 ≡ 1 (mod 10)

 곱셈에 관련된 모듈러 산술의 성질을 이용하면 3 ^ 333 = 3 (mod 10)

정답 : 3

아래 사이트에서 나머지 문제도 확인해라!!!

https://namu.wiki/w/%ED%95%A9%EB%8F%99%EC%8B%9D#s-4

합동식 - 나무위키

 

그 외의 합동식의 성질

 a와 b는 m에 의하여 나눠 졌을때의 나머지가 동일

이때, 나누어지는 수들의 관계를 분석해보면 나누는 수 5에 의하여 나누어지는 수들 중 나머지가 같은 수(2, 7, 12...)는 나누는 수 만큼의 차이가 존재한다는 것을 알 수 있다. 즉, 5에 대한 나머지가 같은 수들의 집합에서 임의의 두 수를 꺼내서 빼도 항상 그 뺀 차이는 5로 나누어 떨어진다는 것을 알 수 있다. 따라서 이러한 규칙성을 m | (a - b)라고 표현한 것 뿐이고, 그것을 수식으로 표현한 것이다 a ≡ b (mod m)일 뿐이다.