모듈로 연산이란

코딩 테스트 문제 힌트를 보다가 모듈로 연산과 mod라는 키워드가 나오는데 이 키워드가 생소해서 정리한다.

 

https://en.wikipedia.org/wiki/Modulo

Modulo - Wikipedia

모듈로 연산은 한 수를 다른 수로 나눈 후 남은 수(나머지) 또는 부호 있는 나머지를 리턴한다. 이 연산에서 한 수는 다른 수로 나뉘며 나뉘는 수를 모듈로(modulo)라고 한다
두 양의 수 a, n이 주어졌을 때 a modulo n(일반적으로 a mon n이라고 약칭)은 a를 n으로 나눈 유클리드 나눗셈(나머지 정리)의 나머지다. a는 피제수(분자)고 n은 제수(분모)다

예를 들어 5 mod 2는 1로 평가된다. 5를 2로 나눈 상수는 2고 나머지는 1이기 때문이다. 9 mod 3은 0으로 평가된다. 9를 3으로 나눈 상수는 3이고 나머지는 0이기 때문이다...(중략)...정수 모듈로 연산에서 n의 값 범위는 0부터 n-1까지다. a mod 1은 항상 0이다...(중략)

 

쉽게 말해 모듈로 연산은 %을 사용해 나머지를 구하는 연산을 의미한다. % 연산자를 부르는 다른 이름이 모듈로 연산자다.

기호로는 작대기가 세로로 3개 쌓인 ≡ 을 사용하며 아래와 같은 식이 있다고 가정한다.

 

a ≡ b (mod m)

 

이것은 a와 b를 m으로 나눴을 때 나머지가 같다는 뜻으로 이해할 수 있다. 엄밀히 따지면 a, b의 차이가 m의 배수라고도 해야 한다.

챗지피티한테 모듈로 연산이 어느 문제를 풀 때 유용한지 물어보니 아래 문제에서 자주 쓰인다고 하니 참고로만 본다.

 

• 공약수 문제
• 합동식 풀이
• 암호 알고리즘
• 모듈로 역원