모듈러 연산(Modulo Operation)

어떤 하나의 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.

정수론에서 모듈러 연산이란 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이라고 한다.

 

모듈로 연산 사칙 연산

• 덧셈 : (a + b) % M = ((a % M) + (b % M)) % M
• 뺄셈 : (a - b) % M = ((a % M) - (a % M)) % M
• 곱셈 : (a * b) % M = ((a * M) * (b * M)) % M
• 나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다.
  (모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b와 M이 서로소(coprime)일 때만 존재)

 

Ref)

- https://johngrib.github.io/wiki/discrete-math-modular/#%EB%AA%A8%EB%93%88%EB%A1%9C-%EC%97%B0%EC%82%B0