합동식과 군론

개요

• 완전잉여계와 기약잉여계
• 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

블로그

• 142857과 군론의 만남(6) : 군론의 흔적

메타데이터

위키데이터

• ID : Q1169249