모듈러 연산의 성질 (Modular Arithmetic Property)

 * 모듈러 연산의 성질 (Modular Arithmetic Property)

연산을 한 뒤 모듈러를 취하는 것과
각 항에 모듈러를 취한 후 동일한 연산을 하고 모듈러를 취한 것의 결과가 동일하다는 성질

값이 커지는 것을 방지하고
정수 오버플로우를 예방할 수 있다
연산 속도 역시 증가시켜줄 수 있다


모듈러를 취할 때 소수를 사용한다
주로 사용하는 소수는 10007, 1000000007, 998244353 등등

하지만 모듈러 기준값이 꼭 소수일 필요는 없다


종류는
 1. 모듈러 덧셈의 성질
 2. 모듈러 뺄셈의 성질
 3. 모듈러 곱셈의 성질
 4. 모듈러 나눗셈의 성질

..~~~~..

 * 모듈러 덧셈의 성질

(a+b)%m == ((a%m) + (b%m))%m

..~~~~..

 * 모듈러 뺼셈의 성질

(a-b)%m == ((a%m) - (b%m) + m)%m

+m은 중간 결과가 음수가 나오는 것을 방지하기 위해서 사용하는 것

실제 구현에서는
(a-b)%m == ((a%m - b%m + m) %m) 형태를 많이 쓴다

..~~~~..

 * 모듈러 곱셈의 성질

(a*b)%m == ((a%m) * (b%m))%m

..~~~~..

 * 모듈러 나눗셈의 성질

(a÷b)%m == (a*(b^-1))%m

모듈러 곱셈 역원을 사용한다 (modular multiplicative inverse)
여기서는 b^-1은 b의 모듈러 곱셈 역원임

참고로 b * b^-1 == 1 % m을 만족한다

..~~~~..