들어가기 전에
a｜b 는 a가 b를 나눌 수 있다라는 의미이다. (ex 5｜15, 3｜9 등)
A를 B로 나누는 것을 표현하면 A = qB + r (r < B)라고 표현 할 수 있다. (q는 몫, r은 나머지)
모듈러란 ?
수학의 분야 중의 정수론에서 배우게 되는 모듈러는
어떤 정수 A를 다른 정수 N으로 나누면 나오는 나머지
라는 뜻으로 식으로는 A modulo N 이라고 적는다. (modulo를 줄여서 mod라고도 적는다.)
( 몇몇 프로그래밍언어 (c, c++, python 등)에서는 %를 사용하여 A % N 이라고 사용한다. )
이해하기 쉽게 생각하려면 시계를 생각하면 된다.
시계는 24시까지만 표현하고 24시를 넘어가게되면 다시 0시부터 시작한다.
계산할 시간이 77시라고하면
77 mod 24 이고, 77 = 24 * 3 + 5 이므로 몫은 3 나머지는 5
즉 77시는 '5시'라고 계산이 된다.
모듈러 연산이란 ?
모듈러 연산은 합동식이라고도 하며
A≡B (mod m)라고 쓰고
m｜(A-B)라는 뜻이다.
즉 A를 m으로 나누었을 경우 나머지가 B라는 소리이다.
다른 표현으로는
(A-B) = km, A = B + km (k는 정수) 등이 있다.
모듈러 연산 성질
A ≡ B (mod m) , C ≡ D (mod m)이면
1. A±C≡ B±D (mod m)이다.
2. AC ≡ BD (mod m)이다.
3. AC ≡ BC (mod m) 이다. (C는 정수)
4. Aⁿ ≡ Bⁿ (mod m) 이다. (n은 자연수)
모듈러 연산 성질의 증명
1. A+C ≡ B+D (mod m)
A = B+k1m, C = D+k2m
A+C = B+D m(k1 + k2)
-의 경우에도 같은 방법이다.
2. AC ≡ BD (mod m)
A = B+k1m, C = D+k2m
AC = BD + Bk2m +Dk1m + k1k2m²
AC = BD + m(bk2 + dk1 + k1k2m)
3. AC ≡ BC (mod m)
A - B = km
C(A - B) = C(km)
CA - CB = Ckm
4. Aⁿ ≡ Bⁿ (mod m)
2번 성질을 n번 하면 성립
(인수분해를 이용한 증명 등 다른 증명 방법도 있다.)