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(modm)$으로 나타낸다.

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

합동의 기본 성질

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

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

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

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

• 완전 잉여계
  • $\{a_1,a_2,\dots ,a_m\}$에서 $a\equiv a_i(\mathrm{mod}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\ast b=b\ast a=e$를 만족하는 $S$의 원소 b가 유일하게 존재할 때, b를 a의 역원이라고 한다.

오일러 정의

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

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

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

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

페르마의 소정리

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

증명:  오일러 정리에서 $n=p$대입하고, $\phi (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정리