교과서나 인터넷의 블로그 등을 보면, (혹인 계산기를 보면) "mod"라고 적힌 것을 찾아볼 수 있습니다.
정의
모듈러 산술(modulo arithmetic, 또는 합동 산술)은 정수의 합과 곱을 나머지(Remainder)에 대해 정의하는 방법입니다.
이와 달리 계산기에서 찾을 수 있는 모듈러 연산(modulo operation)은 어떤 두 정수가 주어졌을 때, 한 정수로 다른 정수를 나눈 나머지를 반환하는 연산입니다. (컴퓨팅을 기준으로)
일반적으로, \(a\)를 \(b\)로 나눈 나머지를 \(a\ mod\ b\)라 표기합니다.
모듈러의 사칙연산
초등학교 교육과정에서 곱셈, 나눗셈, 덧셈, 뺄셈을 배웠으며, 고등학교 교육과정에서 행렬을 공부할 때 까지도, 새로운 개념과 연산을 배울 때면, 항상 이러한 연산에서 덧셈, 곱셈, 나눗셈, 뺄셈을 진행할 때(사칙연산이 불가능한 경우도 있다.), 교환 법칙이나 결합 법칙 등이 성립하는지에 대해 중요하게 다룹니다.
초~고교 시절 나머지에 대해 배우면서, 여러 성질을 배웠을 것이라고 생각합니다. 예를 들어,
" \(n\ +\ m\) 을 \(p\)로 나눈 나머지는 \(n\)을 \(p\)로 나눈 나머지와 \(m\)을 \(p\)로 나눈 나머지를 더한 값을 \(p\)로 나눈 나머지와 같다."
와 같은 사실은 익히 알고 있을 것입니다.
위와 같은 사실을 바탕으로 알 수 있는 사실은 분배 법칙이 성립한다는 것입니다.
(사실 이 사실을 위 문장은 풀어 쓴 것)
물론 사실, 곱셉에 대해서만 성립한다는 사실을 알 수 있습니다.
증명은 하지 않겠지만, 모듈러 연산에서 아래가 성립합니다.
\((\ n\ +\ m\ )\ \mod\ p\ =\ (\ n\ \mod\ p\ +\ m\ \mod\ p\ )\ \mod p\)
\((\ n\ - m\ +\ kp\ )\ \mod\ p\ =\ (\ n\ \mod\ p\ -\ m\ \mod\ p\ +\ kp\ )\ \mod\ p\) (단, \(kp\)≥\(|\ n\ -\ m\ |\) )
\(\ ab\ \mod\ p\ =\ (\ a\ \mod\ p\ \times\ b\ \mod\ p\ )\ \mod\ p\)
\(\ a\ (\ b\ +\ c\ )\ \mod\ p\ =\ (\ ab\ \mod\ p\ +\ ac\ \mod\ p\ )\ \mod\ p\)
당연하게도, 위 식들이 모듈러 연산의 성질의 전부가 아닙니다.
이번에 다룰 내용에서 중요한 사실은 \( \frac{n}{m}\mod\ p\ \neq\ \frac{n\mod p}{n\mod p}\)라는 것입니다.
모듈러 곱셈 역원
모듈러의 역원(Modulo inverse)은 다음과 같이 정의됩니다.
정수 \(a\ mod\ p\)의 역원을 \(a^{-1}\) 로 표기하면,
\( (\ a\ \times\ a^{-1}\ )\ \equiv\ 1\ (\ \mod\ p )\)
위 식을 만족합니다. 또한, \(p\)와 서로소인 수 만이 역원을 가집니다. 역은 성립하지 않음에 주의하십시오.
페르마 소정리(Fermat's little theorem)
\(p\)가 소수라면, 페르마 소정리에 따라 \( a\ \equiv\ a^{p}\ (\ \mod\ p\ ) \) 입니다.
\(p\ \nmid\ a\)일 때, \(\ a^{p-1}\ \equiv\ 1\ (\ \mod\ p\ )\) 이며, 여기서 \(a^{p-2}\ \equiv\ a\ (\ mod\ p\ )\)로 쓸 수 있으므로,
\(a^{p-2}\)는 \(a\ \mod\ p\)의 역원이 됩니다.
페르마의 소정리를 간단히 증명해 보면,
위에서 한 연산을 지속적으로 수행하면 됩니다. \(p\)가 \(2\) 라면, \( a\ \mod\ p \in \left \{ 0, 1 \right \}\)이므로 페르마의 소정리가 성립합니다. 그렇지 않다면 \(p\)는 홀수 이므로 결국 \(a^{p}\)와 \(a\)를 \(1\) 로 같게 만들 수 있습니다.
잘못된 정보가 있다면 지적 바랍니다.