모듈러 연산

[1. 개요]

모듈러 연산의 여러가지 특징을 정리한다.

---

[2. 표기]

일반적인 표기

• A mod B == A % B

합동 관계

• A mod N == B mod N 일 때 아래와 같이 표기
• A ≡ B (mod N)

---

[3. 분배 법칙]

덧셈

• (A + B) mod C = ((A mod C) + (B mod C)) mod C

곱셈

• (A * B) mod C = ((A mod C) * (B mod C)) mod C
• 두 수의 곱이 overflow 날 수 있을 지도,

뺄셈

• (A - B) mod C = ((A mod C) - (B mod C) + C) mod C
• 뺄셈 결과 가 음수 인 경우 방지

일반적으로 나눗셈에 대해서는 분배법칙을 적용 할 수 없다.

다만, 특수한 경우에 대해서는 페르마의 소정리를 이용하여 구할 수 있다.

 

페르마의 소정리 란?

• https://testkernelv2.tistory.com/703