모듈러 연산
덧셈에 대한 역원
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이어야 한다.
>> 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)은 성립하지 않는다.