블로그 이미지
두번째 블로그, 조금은 개인적인 공간;ㅅ;
메시에

태그목록

공지사항

최근에 달린 댓글

글 보관함

calendar

      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  

* Thm 3. Zn이 Field  <==>  n이 prime number.

 

proof)

n이 소수고 0<a<n인 a가 있다 하자.

n이 소수이므로 GCD (a,n) = 1. 즉 a와 n은 서로소이다.        

그러면, Bezout's Identity에 의해 as + tn = 1이 되는 s, t가 존재한다.

그러면 as == 1 (mod n)

즉 a의 역원이 되는 s가 반드시 존재하고 a는 unit이 됨.

곱셈에 대한 역원이 존재하므로 field이다.

 

* n이 prime이 아니면, field가 될 수 없다.

- n이 소수가 아니므로 n = n1 * n2, 1<n1, n2<n 인 n1, n2가 존재.

  [n1] != 0, [n2] != 0 이지만 [n1*n2] = [0] 이 될 수 있다. (Zero Divisor가 존재한다)

  따라서 Field는 물론 Integral Domain도 될 수 없다.

 


* Thm 4. [a] : unit  <==>  GCD (a,n) = 1

- [a] 가 unit이다 -> ab = 1 + qn. 

  그런데 a, n 사이에는 공통인수 (common factor) 가 없다. -> a, n은 서로소다.

                         

<Bezout's Identity>

- a, n이 서로소다 -> 1 = au + nv, [u] 가 [a] 의 역원이 되어주므로 [a] 는 unit.

 

 

* Euler's Phi Function

: RSA (공개 키 암호) 기법 등에 응용됨.

 

- residues (나머지) : 0, 1, 2, ..., n-1

- 나머지 중에서 n이랑 서로소인 원소들의 집합 : reduced set of residues

- R.S of residues의 원소 개수 = Euler Phi Func.

 

ex : Phi(10) = 4 (1,3,7,9)

 

 

- GCD (m,n) = 1  =>  Phi(mn) = Phi(m) * Phi(n)

 

 

* Zn* VS. Phi(n)

- Def) Zn* = {[m] | GCD(m,n)=1, 1<=m<=n}

         곱셈에 대한 역원이 존재하는, 즉 n이랑 서로소인 m들의 집합.

 

- |Zn*| = Phi (n).

 

 

 

 

 

이전 1 2 3 4 5 6 7 다음