잔글 (→일반화) |
편집 요약 없음 |
||
30번째 줄: | 30번째 줄: | ||
: 인데, <math>k\equiv 2^m\pmod{2^{m+1}}</math> 또는 <math>k\equiv 0\pmod{2^{m+1}}</math>이므로 둘 중 하나는 영이다. 따라서 <math>N=m+1</math>일 때 명제가 성립하므로, 수학적 귀납법에 의해 원하는 결론을 얻는다. | : 인데, <math>k\equiv 2^m\pmod{2^{m+1}}</math> 또는 <math>k\equiv 0\pmod{2^{m+1}}</math>이므로 둘 중 하나는 영이다. 따라서 <math>N=m+1</math>일 때 명제가 성립하므로, 수학적 귀납법에 의해 원하는 결론을 얻는다. | ||
== | == 잉여류 == | ||
≡가 동치관계이므로, [[동치류]]를 정의할 수 있다. [[집합 (수학)|수학]] | ≡가 동치관계이므로, [[동치류]]를 정의할 수 있다. [[집합 (수학)|수학]] | ||
: <math>\begin{align}[] [a]_n&=\{b\in\mathbb{Z}\vert b\equiv a\pmod{n}\}\\ | : <math>\begin{align}[] [a]_n&=\{b\in\mathbb{Z}\vert b\equiv a\pmod{n}\}\\ | ||
&=\{b\in\mathbb{Z}\vert b=a+kn,k\in \mathbb{Z}\}\\ | &=\{b\in\mathbb{Z}\vert b=a+kn,k\in \mathbb{Z}\}\\ | ||
&=\{a+kn\vert k\in\mathbb{Z}\}\end{align}</math> | &=\{a+kn\vert k\in\mathbb{Z}\}\end{align}</math> | ||
를 법 ''n''에 대한 ''a''의 ''' | 를 법 ''n''에 대한 ''a''의 '''잉여류(Residue class)''' 또는 '''합동류(Congruence class)'''라고 한다. 예를 들어, | ||
: <math>[0]_3=\{3k\vert k\in\mathbb{Z}\}=\{\cdots,-9,-6,-3,0,3,6,9,\cdots\}</math> | : <math>[0]_3=\{3k\vert k\in\mathbb{Z}\}=\{\cdots,-9,-6,-3,0,3,6,9,\cdots\}</math> | ||
: <math>[1]_3=\{1+3k\vert k\in\mathbb{Z}\}=\{\cdots,-8,-5,-2,1,4,7,10,\cdots\}</math> | : <math>[1]_3=\{1+3k\vert k\in\mathbb{Z}\}=\{\cdots,-8,-5,-2,1,4,7,10,\cdots\}</math> | ||
법 ''n''에 대한 모든 | 법 ''n''에 대한 모든 잉여류의 집합을 <math>\mathbb{Z}_n</math> 또는 <math>\mathbb{Z}/n\mathbb{Z}</math>로 쓴다. | ||
잉여류의 연산 +와 ·를 다음과 같이 정의하자. | |||
: <math>[a]_n+[b]_n=[a+b]_n</math> | : <math>[a]_n+[b]_n=[a+b]_n</math> | ||
: <math>[a]_n\cdot[b]_n=[ab]_n</math> | : <math>[a]_n\cdot[b]_n=[ab]_n</math> | ||
그러면 두 연산은 잘 정의되어 있다. 임의의 | 그러면 두 연산은 잘 정의되어 있다. 임의의 잉여류 <math>[a]_n,[b]_n,[c]_n</math>에 대해 다음 성질이 성립한다. | ||
# <math>[a]_n+[b]_n=[a+b]_n\in\mathbb{Z}_n</math> | # <math>[a]_n+[b]_n=[a+b]_n\in\mathbb{Z}_n</math> | ||
# <math>[a]_n+([b]_n+[c]_n)=([a]_n+[b]_n)+[c]_n</math> | # <math>[a]_n+([b]_n+[c]_n)=([a]_n+[b]_n)+[c]_n</math> | ||
55번째 줄: | 55번째 줄: | ||
# <math>[a]_n\cdot([b]_n+[c]_n)=[a]_n\cdot[b]_n+[a]_n\cdot[c]_n,\; ([a]_n+[b]_n)\cdot[c]_n=[a]_n\cdot[c]_n+[b]_n\cdot[c]_n</math> | # <math>[a]_n\cdot([b]_n+[c]_n)=[a]_n\cdot[b]_n+[a]_n\cdot[c]_n,\; ([a]_n+[b]_n)\cdot[c]_n=[a]_n\cdot[c]_n+[b]_n\cdot[c]_n</math> | ||
위의 성질에 의해, <math>\mathbb{Z}_n</math>는 [[환 (수학)|가환환]]임을 알 수 있다. | 위의 성질에 의해, <math>\mathbb{Z}_n</math>는 [[환 (수학)|가환환]]임을 알 수 있다. | ||
== 완전잉여계 == | |||
법 ''n''에 대한 ''n''개의 잉여류 <math>[0]_n,[1]_n,\cdots,[n-1]_n</math>에서 각각 한 개의 정수를 선택해 만든 집합 | |||
: <math>S=\{s_0,s_1,\cdots,s_{n-1}\}</math> (단, <math>s_i\in [i]_n\text{ for each }i\in\{0,\cdots,n-1\}</math>) | |||
를 법 ''n''에 대한 '''완전잉여계(complete residue system)'''라고 한다. | |||
== 일반화 == | == 일반화 == |
2015년 6월 1일 (월) 17:32 판
개요
모듈러산술(Modular arithmetic)이란, 아래에서 서술할 합동관계에 의해 정수를 연산하는 방법이다.
합동관계
양의 정수 m에 대해
- [math]\displaystyle{ m\mid a-b }[/math][1]
이면 a, b는 법(modulus) m에 대해 합동(congruent)이라 하고,
- [math]\displaystyle{ a\equiv b\pmod{m} }[/math]
로 표기한다. 이때 법 m이 고정되어 있지 않으면 동치관계나, 연산을 말하는 것이 의미가 없으므로 아래에서 법 m은 고정된 것으로 생각한다.
이때 ≡는 동치관계이다. 즉, 임의의 정수 [math]\displaystyle{ a,b,c }[/math]에 대해
- (반사성) [math]\displaystyle{ a\equiv a\pmod{m} }[/math]
- (대칭성) [math]\displaystyle{ a\equiv b\pmod{m} }[/math]이면 [math]\displaystyle{ b\equiv a\pmod{m} }[/math]
- (추이성) [math]\displaystyle{ a\equiv b\pmod{m} }[/math]이고 [math]\displaystyle{ b\equiv c\pmod{m} }[/math]이면 [math]\displaystyle{ a\equiv c\pmod{m} }[/math]
이 성립한다(증명은 자명하다).
한편, 정수 [math]\displaystyle{ a,b,c,d }[/math]에 대해
- [math]\displaystyle{ a\equiv b\pmod m,\quad c\equiv d\pmod m }[/math]
이면 다음이 성립한다.
- [math]\displaystyle{ a+c\equiv b+d\pmod m }[/math]
- [math]\displaystyle{ ac\equiv bd\pmod m }[/math]
예
2와 7로만 이루어진 자연수를 큿수라고 하면 N자리이고 [math]\displaystyle{ 2^N }[/math]의 배수인 큿수가 존재함을 모듈러산술로 보일 수 있다.
- [math]\displaystyle{ N=1 }[/math]이면 2는 한 자리 자연수인 동시에 2의 배수다.
- [math]\displaystyle{ N=m }[/math]에 대해 명제가 성립한다고 가정하자. 그러면 m자리이고 [math]\displaystyle{ 2^m }[/math]의 배수인 큿수가 존재한다. 이 수를 k라고 하자. 그러면
- [math]\displaystyle{ 2\cdot10^m+k\equiv k\pmod{2^{m+1}} }[/math]
- [math]\displaystyle{ 7\cdot10^m+k\equiv 2^m+k\pmod{2^{m+1}} }[/math]
- 인데, [math]\displaystyle{ k\equiv 2^m\pmod{2^{m+1}} }[/math] 또는 [math]\displaystyle{ k\equiv 0\pmod{2^{m+1}} }[/math]이므로 둘 중 하나는 영이다. 따라서 [math]\displaystyle{ N=m+1 }[/math]일 때 명제가 성립하므로, 수학적 귀납법에 의해 원하는 결론을 얻는다.
잉여류
- [math]\displaystyle{ \begin{align}[] [a]_n&=\{b\in\mathbb{Z}\vert b\equiv a\pmod{n}\}\\ &=\{b\in\mathbb{Z}\vert b=a+kn,k\in \mathbb{Z}\}\\ &=\{a+kn\vert k\in\mathbb{Z}\}\end{align} }[/math]
를 법 n에 대한 a의 잉여류(Residue class) 또는 합동류(Congruence class)라고 한다. 예를 들어,
- [math]\displaystyle{ [0]_3=\{3k\vert k\in\mathbb{Z}\}=\{\cdots,-9,-6,-3,0,3,6,9,\cdots\} }[/math]
- [math]\displaystyle{ [1]_3=\{1+3k\vert k\in\mathbb{Z}\}=\{\cdots,-8,-5,-2,1,4,7,10,\cdots\} }[/math]
법 n에 대한 모든 잉여류의 집합을 [math]\displaystyle{ \mathbb{Z}_n }[/math] 또는 [math]\displaystyle{ \mathbb{Z}/n\mathbb{Z} }[/math]로 쓴다.
잉여류의 연산 +와 ·를 다음과 같이 정의하자.
- [math]\displaystyle{ [a]_n+[b]_n=[a+b]_n }[/math]
- [math]\displaystyle{ [a]_n\cdot[b]_n=[ab]_n }[/math]
그러면 두 연산은 잘 정의되어 있다. 임의의 잉여류 [math]\displaystyle{ [a]_n,[b]_n,[c]_n }[/math]에 대해 다음 성질이 성립한다.
- [math]\displaystyle{ [a]_n+[b]_n=[a+b]_n\in\mathbb{Z}_n }[/math]
- [math]\displaystyle{ [a]_n+([b]_n+[c]_n)=([a]_n+[b]_n)+[c]_n }[/math]
- [math]\displaystyle{ [a]_n+[0]_n=[a]_n=[0]_n+[a]_n }[/math]
- [math]\displaystyle{ [a]_n+[-a]_n=[0]_n=[-a]_n+[a]_n }[/math]
- [math]\displaystyle{ [a]_n+[b]_n=[b]_n+[a]_n }[/math]
- [math]\displaystyle{ [a]_n\cdot[b]_n=[ab]_n\in\mathbb{Z}_n }[/math]
- [math]\displaystyle{ [a]_n\cdot([b]_n\cdot[c]_n)=([a]_n\cdot[b]_n)\cdot[c]_n }[/math]
- [math]\displaystyle{ [a]_n\cdot[1]_n=[a]_n=[1]_n\cdot[a]_n }[/math]
- [math]\displaystyle{ [a]_n\cdot[b]_n=[b]_n\cdot[a]_n }[/math]
- [math]\displaystyle{ [a]_n\cdot([b]_n+[c]_n)=[a]_n\cdot[b]_n+[a]_n\cdot[c]_n,\; ([a]_n+[b]_n)\cdot[c]_n=[a]_n\cdot[c]_n+[b]_n\cdot[c]_n }[/math]
위의 성질에 의해, [math]\displaystyle{ \mathbb{Z}_n }[/math]는 가환환임을 알 수 있다.
완전잉여계
법 n에 대한 n개의 잉여류 [math]\displaystyle{ [0]_n,[1]_n,\cdots,[n-1]_n }[/math]에서 각각 한 개의 정수를 선택해 만든 집합
- [math]\displaystyle{ S=\{s_0,s_1,\cdots,s_{n-1}\} }[/math] (단, [math]\displaystyle{ s_i\in [i]_n\text{ for each }i\in\{0,\cdots,n-1\} }[/math])
를 법 n에 대한 완전잉여계(complete residue system)라고 한다.
일반화
추상대수학의 영역으로 가면 합동관계를 다음과 같이 서술할 수 있다:
군
- [math]\displaystyle{ ab^{-1}\in K }[/math]
이면 [math]\displaystyle{ a,b }[/math]는 법 K에 대해 합동이라 하고 [math]\displaystyle{ a\equiv b\pmod K }[/math]로 나타낸다. 이 경우에도 [math]\displaystyle{ \equiv }[/math]는 동치관계라는 것을 보일 수 있다.
K가 G의 정규부분군이라고 가정하자. 임의의 [math]\displaystyle{ a,b,c,d\in G }[/math]에 대해 [math]\displaystyle{ a\equiv b\pmod{K} }[/math]이고 [math]\displaystyle{ c\equiv d\pmod{K} }[/math]라면 다음 연산이 성립함을 보일 수 있다.
- [math]\displaystyle{ ac\equiv bd\pmod{K} }[/math]
환
- [math]\displaystyle{ a-b\in I }[/math]
이면 [math]\displaystyle{ a,b }[/math]는 법 I에 대해 합동이라 하고 [math]\displaystyle{ a\equiv b\pmod I }[/math]로 나타낸다. 이 경우에도 [math]\displaystyle{ \equiv }[/math]는 동치관계임을 보일 수 있다.
만약 I가 아이디얼이라고 가정하자. 임의의 [math]\displaystyle{ a,b,c,d\in R }[/math]에 대해 [math]\displaystyle{ a\equiv b\pmod{I} }[/math]이고 [math]\displaystyle{ c\equiv d\pmod{I} }[/math]이면 다음 연산이 성립함을 보일 수 있다.
- [math]\displaystyle{ a+c\equiv b+d\pmod{I} }[/math]
- [math]\displaystyle{ ac\equiv bd\pmod{I} }[/math]
[math]\displaystyle{ ac\equiv bd\pmod{I} }[/math]의 증명. [math]\displaystyle{ a\equiv b\pmod{I} }[/math]이고 [math]\displaystyle{ c\equiv d\pmod{I} }[/math]이이므로
- [math]\displaystyle{ ac-bd=ac-bc+bc-bd=(a-b)c+b(c-d)=ic+bj }[/math]
인 [math]\displaystyle{ i,j\in I }[/math]가 존재한다. 이때 아이디얼의 정의에 의해 [math]\displaystyle{ ic\in I }[/math]이고 [math]\displaystyle{ bj\in I }[/math]이다. 따라서 [math]\displaystyle{ ic+bj\in I }[/math]이므로 원하는 결론을 얻는다.