For a better world

잉여류

잉여류는 정수 $a$와 법 $m$에 대해 합동인 모든 정수의 집합이다.

예를 들어 7을 5로 나누면 2가 남으며 이러한 수는 7, 12, 17, 22, $\dots$가 될 수 있다.

이를 법 5에 ~대한 7의 잉여류/합동류라 표현할 수 있다.

합동의 정의

• 정수론에서는 합동을 $a, b$를 $m$으로 나눈 나머지가 같을 때, $a$와 $b$가 법$(modulo)\ m$에 관하여 합동 (Congruence)이라고 하고, $a \equiv b(mod\ m)$으로 나타낸다.

• 두 정수 $a,b$에 대해서 $a-b$가 $m$의 배수일 때,  $a$와 $b$는 $m$을 법으로 합동(Congruent modulo m)이라한다.

합동의 기본 성질

$a\equiv b(mod\ m)$이고, $c\equiv d(mod\ m)$이면, 다음과 같다.

1. $a + c \equiv b + d(mod\ m)$
2. $ac \equiv bd(mod\ m)$
3. $a^n \equiv b^n(mod\ m)$

기약 잉여계와 완전 잉여계의 정의

• 기약 잉여계
  • $\{a_1, a_2, \dots , a_m \}$가 법 $m$에 대한 완전 잉여계일 때, 여기서 $m$과 서로소인 원소만 모은 집합을 법 $m$에 대한 기약잉여계라 한다.

• 완전 잉여계
  • $\{a_1, a_2, \dots , a_m \}$에서 $a \equiv a_i \pmod{m}$인 $a_i$가 유일하게 있을 때, $\{a_1, a_2, \dots , a_m \}$ 를 완전잉여계라고 한다.

기약 잉여계와 완전 잉여계의 예시

$4$를 예시로 들면, $\{0, 1, 2, 3\}$은 완전잉여계, 그리고 $4$와 서로소가 아닌 $0, 2$를 제외한 $\{1, 3\}$는 기약잉여계가 된다. 기약잉여계가 중요한 이유는, 곱셈의 역원이 있다는 점 때문이다. 예컨대, 6에 대한 완전잉여계 $\{0, 1, 2, 3, 4, 5\}$와 그것의 기약잉여계 $\{1, 5\}$를 생각하자. $\{1, 5\}$의 원소는 모두 곱셈 역원을 갖는다. 그러나, 다른 완전잉여계 원소는 그렇지 않다. 이는, $m$과 $a$가 서로소일 때, 정수 $x,y$가 존재하여 $ax + my = 1$ 즉, $ax \equiv \ 1(m)$이기 때문이다.

역원의 정의

집합 $S$와 이항연산자 *에 대해, 만약 항등원 e가 존재한다고 할 때, S의 원소 a에 대해

$a * b = b * a = e$를 만족하는 $S$의 원소 b가 유일하게 존재할 때, b를 a의 역원이라고 한다.

오일러 정의

기약 잉여계 개념은 정수론에서 오일러의 정의를 증명하는 데 사용된다. 정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.

• $a$와 $n$이 서로소인 양의 정수일 때, $a^{\varphi(n)} \equiv 1(mod\ n)$이다.
  • 여기서 $\varphi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수이다. 오일러 피 함수라고도 불린다.

• 양의 정수 $m$에 대하여, $m$ 이하의 자연수 중에서 $m$과 서로소인 정수의 개수를 $\varphi (m)$으로 나타내고 함수 $\varphi : Z→N$ 를 오일러의 $\varphi$ 함수라고 한다.
  
  • $\varphi$ = varphi

또한 오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리이다.
참고로 오일러 공식, 오일러 방정식과는 다른 것이다.

페르마의 소정리

$p$가 소수일 때, $gcd(a, p)=1$인 정수 $a$에 대하여 $a^(p-1) \equiv 1(mod p)$이다.

증명:  오일러 정리에서 $n=p$대입하고, $\varphi (p)=p-1$ 이용하면 증명

Reference

[1] http://blog.naver.com/PostView.nhn?blogId=dlrbtjd86&logNo=113315940

[2] https://namu.wiki/w/기약잉여계

[3] https://schbeom.tistory.com/367

[4] https://minq.tistory.com/90

[5] https://thewiki.kr/w/오일러%20정리