[이론] 모듈로 연산(Modulo Operation)

모듈로 연산?

모듈로 연산은 어떠한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로 나머지 연산(mod)라고 한다(프로그래밍 언어에서 %연산자를 의미한ㄷ.). 정수론에서 모듈로 연산이라는것이 있는데, 이는 정수의 합과 곱을 어떤 주어진 수의 나머지에 대해 정의하는 방법이다.

 

모듈로 연산은 아래 세가지를 충족시킨다고 한다. 나머지는 이 공식에 부합하지 않는다고 한다.

 

• (A + B) % C = ((A % C) + (B % C)) % C
• (A - B) % C = ((A % C) - (B % C)) % C
• (A * B) % C = ((A % C) * (B % C)) % C

유도해보기

A,B를 각각 위와 같이 정의하고 유도해보면 아래와 같다.

이 원리를 이용해 풀었던 문제이다.

https://www.acmicpc.net/problem/15624

15624번: 피보나치 수 7