편집 요약 없음 |
잔글 (기호의 의미를 모르는 사람이 볼 수 있어서 주석 추가) |
||
4번째 줄: | 4번째 줄: | ||
== 합동관계 == | == 합동관계 == | ||
정수 ''m''에 대해 | 정수 ''m''에 대해 | ||
: <math>m\mid a-b</math> | : <math>m\mid a-b</math><ref>a-b가 m으로 나누어 떨어진다는 것을 수식으로 표현한 것</ref> | ||
이면 ''a'', ''b''는 법(modulus) ''m''에 대해 '''합동(congruent)'''이라 하고, | 이면 ''a'', ''b''는 법(modulus) ''m''에 대해 '''합동(congruent)'''이라 하고, | ||
: <math>a\equiv b\pmod{m}</math> | : <math>a\equiv b\pmod{m}</math> | ||
16번째 줄: | 16번째 줄: | ||
* <math>a+c\equiv b+d\pmod m</math> | * <math>a+c\equiv b+d\pmod m</math> | ||
* <math>ac\equiv bd\pmod m</math> | * <math>ac\equiv bd\pmod m</math> | ||
== 예 == | == 예 == | ||
* [[큿]]수<ref>0xrgb (2015.4.19). [http://rgb.wo.tc/45 퍼즐<nowiki>]</nowiki> 큿수]. 크리에이티브 커먼즈 저작자표시-비영리 4.0 국제로 배포됨. 2015년 5월 17일에 확인.</ref> | * [[큿]]수<ref>0xrgb (2015.4.19). [http://rgb.wo.tc/45 퍼즐<nowiki>]</nowiki> 큿수]. 크리에이티브 커먼즈 저작자표시-비영리 4.0 국제로 배포됨. 2015년 5월 17일에 확인.</ref> |
2015년 5월 17일 (일) 03:46 판
개요
모듈러산술(Modular arithmetic)이란, 아래에서 서술할 합동관계에 의해 정수를 연산하는 방법이다.
합동관계
정수 m에 대해
- [math]\displaystyle{ m\mid a-b }[/math][1]
이면 a, b는 법(modulus) m에 대해 합동(congruent)이라 하고,
- [math]\displaystyle{ a\equiv b\pmod{m} }[/math]
로 표기한다. 이때 [math]\displaystyle{ \equiv }[/math]는 동치관계이다. 즉, 임의의 정수 [math]\displaystyle{ a,b,c,m }[/math] (단, [math]\displaystyle{ m\gt 0 }[/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+1}+k\equiv k\pmod{2^{m+1}} }[/math]
- [math]\displaystyle{ 7\cdot10^{m+1}+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]일 때 명제가 성립하므로, 수학적 귀납법에 의해 원하는 결론을 얻는다.
일반화
추상대수학의 영역으로 가면 합동관계를 다음과 같이 서술할 수 있다: K는 군 G의 부분군이고 [math]\displaystyle{ a,b\in G }[/math]라 하자. 이때
- [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]는 동치관계라는 것을 보일 수 있다.