모듈로 연산 (Modulo Operation)

모듈로 연산

 

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

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

프로그래밍 언어에선 %이 mod의 역할을 한다.

 

ex) 8 mod 3 = 2

 

A mod B = Q

라 해보자

이때 Q는 B보다 작아야 된다... (당연함)

 

ex) -1 mod 5 = 4

A가 음수일 경우에는 A에 B를 더해주고 계산하면 된다

즉 (-1+5) mod 5 = 4 로 계산해주고 답을 얻어낼 수 있다.

 

 

우리가 주목해야 될 것은 모듈로 연산의 속성이다

(알고리즘 문제에 많이 나옴)

 

 

모듈로 연산의 속성 (***)

(a + b) mod n = ((a mod n) + (b mod n)) mod n

(a - b) mod n = ((a mod n) - (b mod n)) mod n

(a * b) mod n = ((a mod n) * (b mod n)) mod n

 

예를 들어 a를 8 b를 13 n을 5이라고 대입해보자

(1) 21 mod 5 = ( 8 mod 5 + 13 mod 5 ) mod 5

    -> 1 = 6 mod 5

(2) -5 mod 5 = ( 8 mod 5 - 13 mod 5 ) mod 5

    -> 0 = -5 mod 5

(3) 104 mod 5 = ( 8 mod 5 * 13 mod 5 ) mod 5

    -> 4 = 104 mod 5

 

굿

 

 

마지막으로 모듈로 합동에 대하여 알아보자.

A mod B = Q라고 할 때

Q와 B가 고정돼 있을 때 A의 값들은 합동이 된다... 라고 이해하면 쉬웠다

 

예를 들어 

7 mod 4 = 3

11 mod 4 = 3

15 mod 4 = 3 

 

이런 상황을 수식으로 표현하면,

a ≡ b (mod m)

 

예시로 생각하면 7 ≡ 11 (mod 4) 와 같은 식을 만들수 있다. 

 

 

 

 

참고: 

모듈러 연산(Modular Arithmetic)