합동식과 군론
Pythagoras0 (토론 | 기여)님의 2013년 4월 14일 (일) 03:39 판
개요
- 완전잉여계와 기약잉여계
- 1부터 n까지의 양의 정수들은 덧셈 (mod n) 에 대한 군의 구조를 이룸
- 이 군을 \(\mathbb{Z}/n\mathbb{Z}\) 로 표현함
- 완전잉여계
- 1부터 n까지의 양의 정수 중에 n과 서로소인 수로 구성된 집합은 곱셈 (mod n) 에 대한 군의 구조를 이룸
- 이 군을 \((\mathbb{Z}/n\mathbb{Z})^\times\) 로 표현함
- 이 집합의 원소의 개수는 \(\varphi(n)\)이며, 여기서 $\varphi$는 오일러의 totient 함수
- 기약잉여계
- 합동식이 무엇인지에 대해서는 합동식 (모듈로 modulo 연산) 항목을 참조
- 군론에 대해서는 고교생도 이해할 수 있는 군론 입문 참조
n=4의 경우
- \(\{1,3\}\) 의 곱셈 (mod 4) 테이블
| \(\times\) | 1 | 3 |
|---|---|---|
| 1 | 1 | 3 |
| 3 | 3 | 1 |
n=6의 경우
- \(\{1,5\}\) 의 곱셈 (mod 6) 테이블
| \(\times\) | 1 | 5 |
|---|---|---|
| 1 | 1 | 5 |
| 5 | 5 | 1 |
n=7 의 경우
- \(\{1,2,3,4,5,6\}\) 의 곱셈 테이블
| \(\times\) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
n=10 의 경우
- \(\{1,3,7,9\}\) 의 곱셈 테이블
| \(\times\) | 1 | 3 | 7 | 9 |
|---|---|---|---|---|
| 1 | 1 | 3 | 7 | 9 |
| 3 | 3 | 9 | 1 | 7 |
| 7 | 7 | 1 | 9 | 3 |
| 9 | 9 | 7 | 3 | 1 |
관련된 항목들
사전 형태의 자료
- http://ko.wikipedia.org/wiki/
- http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n