모듈러 산술 연산의 이해.

1. 모듈러 산술 연산 : 나머지 연산을 하는 것. 컴퓨터 언어에서 사용하는 %연산으로 표현하면 아래와 같다.

r = a % m (r: 나머지, a: 피제수, m: 제수)
r = a mod m

# a를 m으로 나눈 나머지 r

 

 

2. 합동(Congruent) : mod 연산은 합동 관계를 바탕으로 두 수의 관계를 정의

정수 a, b, m에 대해 m | (a-b)라고 하면, a와 b는 모듈러(modulus) m에 대해 합동이라 하고,
a ≡ b (mod m)과 같은 수식으로 표현

-> m | (a - b)에서 | 의 의미는 (a - b)는 m으로 나누어 떨어진다는 의미. 나누어 떨어지지 않는 경우는 ł

-> a - b가 m이라는 정수로 나누어 떨어진다면, a ≡ b (mod m)과 같이 표현

-> 이는 다르게 말하면, a와 b는 m으로 나눌 때, 나머지가 동일함을 의미

여기서 m은 5, a와 b는 2, 7, 12...이 된다.

 

3. 모듈러 분배 법칙

1. (a + b) % m = ((a % m) + (b % m)) % m
2. (a * b) % m = ((a % m) * (b % m)) % m
3. (a - b) % m = ((a % m) - (b % m)) % m # 음수 고려

 

3-1 증명

1. 임의의 정수 a, b, m에 대해서, (a + b) % m = (a % m + b % m) % m

 

• a % m = a  - m * k1, b % m = b - m * k2로 표현가능
• 위 식을 더하면, a + b - m * (k1 + k2)인데, m으로 나머지 연산을 하면 -m*(k1 + k2)는 나머지에서 날라감.
• (a + b) % m = a % m + b % m은 성립한다.

 

위의 증명에 따라

좌변: a % m + b % m

우변: ((a + b) % m) % m -> (a + b) % m -> a % m + b % m

으로 표현 가능

따라서, (a + b) % m = (a % m + b % m) % m은 성립한다.

 

2. 임의의 정수 a, b, m에 대해, (ab) % m = ((a % m) * (b % m)) % m

 

• a % m = a  - m * k1, b % m = b - m * k2로 표현가능
• 위 식을 곱하면, ab  - bmk1 - amk2 + m^2k1k2 인데, m으로 나머지 연산을 하면 - bmk1 - amk2 + m^2k1k2 는 나머지에서 날라감.
• (ab) % m = (a % m) * (b % m)은 성립한다.
• 이하 동문.

3. 1과 유사하므로 생략