Finite Field - Modular Arithmetic

- Modular Arithmetic
n : 모든 양의 정수, a : 음이 아닌 정수 일 때, 
                                           a = qn + r     0 <= r < n;
이고 a mod n = r 로 정의합니다.

- b|a
a를 b로 나누었을 때 나머지가 0이라는 것을 의미합니다. 따라서 b는 a의 Divisor(약수)가 됩니다.

- Properties of Modular Arithmetic
. [(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 mod n = ra, b mod n = rb라 두면, 어떤 정수 j, k가 존재할 때,
a = ra+jn, b = rb+kn으로 나타낼 수 있다. 
(a-b) mod n = (ra+jn-rb-kn) mod n = {ra-rb+(j-k)n} mod n
                

= (ra-rb) mod n = [(a mod n) - (b mod n)] mod n
입니다. 나머지 성질도 위와 같은 방법으로 증명을 하면 됩니다.

- a = b mod n if n|(a-b) 
쉽게 말해서 a = b mod n 이면 b = a mod n도 만족한 다는 말입니다.
(증명은 간단하므로 생략..)

- 덧셈에 대해 commutative ring이고 곱셈에 대한 항등원이 존재할 때,
(a+b)≡(a+c) mod n 이면 b≡c mod n이 성립합니다. 그러나,
(ab)≡(ac) mod n 이면 b≡c mod n이 성립하기 위해서는 a가 n과 relatively prime 즉 a와 n사이에 공약수는 1만 존재해야 합니다.