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

태그목록

공지사항

최근에 달린 댓글

글 보관함

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      

'공부_2학년 2학기/이산수학'에 해당되는 글 2

  1. 2013.11.21 11/20 이산수학 - Number Theory (2)
  2. 2013.11.18 11/18 이산수학 - Number Theory (1)

<Group에 대하여>

 

* Order of Group (|G|) : Group의 원소 개수.

 

ex) | <Zp*, *> |  =  p-1

(소수에 대해서는 모두 역원이 존재하므로. 단 0은 제외이므로 -1)

 

* Properties of Group

- 항등원은 유일하다.

- 역원은 각 원소에 대해서 유일하다.

 

- cancellation property : ab = ac => b = c / ba = ca => b = c

proof -- a의 역원을 양변의 앞에 곱해주면 a가 날아감.

 

* Subgroup

- G에서 원소 몇개 빼내서 만든 집합 H가 Group이면 H는 G의 서브그룹.

 

ex) G = <Z6, +>   H = {0,2,4}   --  H는 G의 Subgroup

    (Z6에서 2의 역원은 4, 4의 역원은 2...)

 

* Subgroup Condition

- 닫혀있고 Inverse가 존재하면 서브그룹이다.

- 사실은 닫혀있기만 해도 서브그룹이다. (증명?)

 

* Direct Product of Group

 

 

* Powers of Elements

 

 

* Homomorphism / Isomorphism

- f : Z => Z4와 같이 한 그룹에서 다른 그룹으로 향하는 함수가 있을 때.

Z에서 항등원인게 Z4에서도 항등원이고, Z에서 역원인게 Z4에서도 역원이고... 등등

연산관계가 똑같이 적용되는 경우에, Homomorphism.

 

- 여기에 역함수도 존재 (역으로 맵핑이 성립) 하는 경우 => Isomorphism.

- 두 집합이 같은 경우 => Endomorphism.

 

 

* Cuclic Group

 

 

* Order of Elements

* 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 다음