Modular Arithmetic

○Congruence Modulo n (Zn)

 ▷1보다 큰 정수 n과 정수 a, b에 대해

 ▷a ≡ b mod n 또는 n | (a-b) 또는 a = b + kn (k: 정수) 를 만족.

 ▶연산

  ▷Zn = { [0], [1],..., [n-1] }

  ▷[a] + [b] = [a+b]

  ▷[a][b] = [ab]

 

 ▶이론

  ▶Z(정수)에 대해 equivalence relation

   ▷Reflexive: (a,a) ∈ R

   ▷Symmetric: (a,b) ＆ (b,a) ∈ R

   ▷Transitive: (a,b) ＆ (b,c) ＆ (c,a) ∈ R

 

  ▶n≥2의 Zn에서 <Zn,+,×>는 Commutative ring with unity이다.

 

  ▶n이 소수일때 Zn에서 <Zn,+,×>는 Field이다.

 

  ▶Zn에서 gcd(a,n) = 1이면 [a]는 Unit이다.

   ▷Unit: Multiplivative Inverse를 가지는 element

 

 ▶Euler's Phi Function ( Φ(n) )

  ▷2이상 n사이에서 n과 서로소인 정수의 수.

  ▷수를 구성하는 모든 소수에 대해 (소수^n - 소수^(n-1))의 곱

  ▷n = 소수(p) -> Φ(p) = p-1

 

 ▶Zn*

  ▷n과 서로소인 m(2≤m≤n)들로 이루어진 Zn

  ▷|Zn*| = Φ(n)

 

  ▷Multiplication에 대해 Abelian Group이다.