모듈러 산술

정의

정수론에서 모듈러 산술 또는 합동 산술은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다.

성질

모듈러 연산에는 다음과 같은 성질들이 존재한다.

1. 덧셈 : (A + B) mod C = (A mod C + B mod C) mod C
2. 뺄셈 : (A - B) mod C = (A mod C - B mod C) mod C
3. 곱셈 : (A * B) mod C = (A mod C * B mod C) mod C
4. 거듭제곱 : (A^B) mod C = ((A mod C)^B) mod C

프로그래밍에서 종종 매우 큰 수를 처리하게 되는데, 모듈러 거듭제곱 연산의 최적화를 통해 큰 수를 효율적으로 계산할 수 있다.