모듈러 연산

덧셈에 대한 역원

a + b ≡ 0 mod n

모듈러 연산에서 각각의 정수는 덧셈에 대한 역원을 갖는다.

어떤 정수와 그 정수의 덧셈에 대한 역원의 합은 모듈러 n에 대하여 0과 합동이다.

에서 모든 덧셈에 대한 역원 쌍을 찾아라

 >> (0,0), (1,9), (2,8), (3,7), (4,6), (5,5)

만약 (a+b) ≡ (a+c)(mod n) 이라면 b ≡ c(mod n)

즉, 덧셈의 역원이 존재한다.

(5+23) ≡ (5+7)(mod 8);

23 ≡ 7(mod 8)

곱셈에 대한 역원

a x b ≡ 1 mod n

모듈러 연산에서 정수는 곱셈에 대한 역원이 있을 수도 있고 없을 수도 있다.

만약 곱셈에 대한 역원이 있다면, 그 정수와 해당하는 곱셈에 대한 역원의 곱은 모듈러 n에서 1과 합동이다.

단, gcd(n,a)=1이어야 한다.

에서 8의 곱셈에 대한 역원을 계산하라

>> gcd(10,8) = 2, 따라서 1이 아니기 때문에 역원이 존재하지 않는다.

즉, 8을 곱해여 그 결과가 1과 합동이 되는 수를 0부터 9사이에서 찾을 수 없다.

에서 곱셈에 대한 모든 역원을 찾아라

(1,1), (3,7), (9,9) 와 같이 세 쌍의 역원이 존재한다.

0, 2, 4, 5, 6, 8은 곱셈에 대한 역원을 갖지 않는다.

(a x b) ≡ (a x c)(mod n)이라면

b ≡ c(mod n)이다.

단, a는 n과 서로소이다.

다음은 곱셈의 역원을 만족하지 않는 예이다.

6과 8은 서로소가 아니다.

6 x 3 =18 ≡ 2(mod 8)

6 x 7 = 42 ≡ 2(mod 8)

그러나 3 ≡ 7 (mod 8)은 성립하지 않는다.