모듈러 연산(mod)

모듈러 연산 (mod)

• 나머지연산

• a mod b : a를 b로 나눈 나머지

• 어떤 양의 정수 n과 a가 주어지고, 만약 a를 n으로 나눈다면 다음과 같은 관계를 가지는 몫 q와 나머지 r을 얻는다

-> a =  qn + r ( 0 <= r < n < a)  →  a = r mod n

example)

  a=11, n=7

  11 = 1*7 + 4 = 4 mod 7             

  11 = 4 mod 7

 

합동 (Congruent)

• (a mod n) = (b mod n), 두 정수 a와 b는 modulo n에 대해 합동

• a ≡ b mod n 으로 표기

• 예를 들어, 14와 20은 mod 6 에 대하여 합동

 

모듈러 연산자 특성

1. [(a mod n)+(b mod n)] mod n = (a+b) mod n

2. [(a mod n)*(b mod n)] mod n = (a*b) mod n

example)

a = 11, b = 15, n = 8

1. (a + b) mod n = ((11 mod 8) + (15 mod 8)) mod 8 = 3 + 7 mod 8

                             = 10 mod 8 = 2

2. (a * b) mod n = ((11 mod 8) * (15 mod 8)) mod 8 = 3 * 7 mod 8

                             = 21 mod 8 = 5

• 교환법칙

- (w+x) mod n = (x+w) mod n

- (w*x) mod n = (x*w) mod n

• 결합법칙

- [(w+x)+y] mod n = [w+(x+y)] mod n

- [(w*x)*y] mod n = [w*(x*y)] mod n

• 분배법칙

- [w*(x+y)] mod n = [(w*x)+(w*y)] mod n

• 항등원

- (0+w) mod n = w mod n

- (1*w) mod n = w mod n

example)

mod 5 연산, 3의 곱셈의 역원은? 

 (3 x ?) mod 5 = 1

→ ?는 mod 5 연산에 대한 3의 곱셈의 역원 (?는 2, 7, ... 등 여러 개가 있을 수 있다.)

 

Test

• 117 mod 13 = ?를 모듈러 연산의 교환, 분배법칙을 이용해서 한번 풀어보자.

11^7 mod 13

11^2 * 11^2 * 11^2 * 11 mod 13 ( 11^2 mod 13 = 4 )

4 * 4 * 4 * 11 mod 13 = (16 * 44) mod 13 = (16 mod 13) * (44 mod 13) = 3 * 5 mod 13 = 15 mod 13 = 2