모듈러 연산

표기

a ≡ b (mod n): b % n = a % n 이라는 의미
1. n|(a-b)이면 a ≡ b (mod n)
2. a (mod n) ≡ b (mod n)이면 a ≡ b (mod n)
3. a ≡ b (mod n)이면 b ≡ a (mod n)
4. a ≡ b (mod n) 그리고 b ≡ c (mod n)이면 a ≡ c (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 × b) (mod n)
(a + b) ≡ (a + c) (mod n) 이면 b ≡ c (mod n) (a 생략 가능)
- (a × b) ≡ (a × c) (mod n) 이면 b ≡ c (mod n)인가?
  - 6 × 3 ≡ 18 ≡ 2 (mod 8), 6 × 7 ≡ 42 ≡ 2 (mod 8) → 그러나, 3 ≠ 7 (mod 8)
  - a와 n이 서로소일때 만 위 식 성립.
Zn={0,1,2,3, …,(n-1)}: 임의의 Z(정수)를 n으로 나누었을 때의 나머지 집합
- 덧셈의 역원: 두 정수 a, b가 a + b ≡ 0 (mod n)을 만족하면 Zn 상에서 서로가 덧셈에 대한 역원.
- 곱셈의 역원: 두 정수 a, b가 a x b ≡ 1 (mod n)을 만족하면Zn 상에서 서로가 곱셈에 대한 역원.