모듈러산술 편집하기

== 개요 ==
'''모듈러산술(Modular arithmetic)'''이란, 아래에서 서술할 합동 관계에 의해 [[정수]]를 [[연산]]하는 방법이다. 간단히 설명하면, 어떤 두 정수를 다른 한 정수로 나눈 나머지로 비교하는 식이라 할 수 있다. Modular를 합동으로 번역하여 '''합동 산술'''이라고 부르기도 하는데<ref>한국어 위키 백과에는 [[위키백과:합동 산술]]라고 되어 있다.</ref> [[기하학]]의 합동과는 이름만 같고, 내용은 천지차이다. 한국의 교육과정에서는 다루지 않지만, [[수학 경시대회]]를 준비한다면 반드시 알아놔야할 개념 중 하나다. 사실, 수학 경시대회를 준비하지 않아도 배워두면 쓸 데가 많다. 대표적으로 고등학교의 [[이항정리]] 응용 문제.

== 정의 ==
양의 정수 ''m''에 대해
: <math>m\mid a-b</math><ref>''a''−''b''가 ''m''으로 나누어 떨어진다는 뜻이다.</ref>
이면 ''a'', ''b''는 법(modulus) ''m''에 대해 '''합동(congruent)'''이라 하고,
: <math>a\equiv b\pmod{m}</math>
로 표기한다. 이때 법 ''m''이 고정되어 있지 않으면 동치관계나, 연산을 말하는 것이 의미가 없으므로 아래에서 법 ''m''은 고정된 것으로 생각한다.

== 성질 ==
=== 동치관계 ===
이때 <math>\equiv</math>는 [[동치관계]]이다. 즉, 임의의 정수 <math>a,b,c</math>에 대해
*(반사성) <math>a\equiv a\pmod{m}</math>
*(대칭성) <math>a\equiv b\pmod{m}</math>이면 <math>b\equiv a\pmod{m}</math>
*(추이성) <math>a\equiv b\pmod{m}</math>이고 <math>b\equiv c\pmod{m}</math>이면 <math>a\equiv c\pmod{m}</math>
이 성립한다.

또한, <math>\equiv</math>가 [[동치관계]]이기 때문에 다음의 서술도 할 수 있다.

==== 잉여류 ====
<math>\equiv</math>가 동치관계이므로, [[동치류]]를 정의할 수 있다. [[집합]]
:<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}\}\\
&=\{a+kn\vert k\in\mathbb{Z}\}\end{align}</math>
을 법 ''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>[1]_3=\{1+3k\vert k\in\mathbb{Z}\}=\{\cdots,-8,-5,-2,1,4,7,10,\cdots\}</math>
법 ''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\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+[c]_n)=([a]_n+[b]_n)+[c]_n</math>
#<math>[a]_n+[0]_n=[a]_n=[0]_n+[a]_n</math>
#<math>[a]_n+[-a]_n=[0]_n=[-a]_n+[a]_n</math>
#<math>[a]_n+[b]_n=[b]_n+[a]_n</math>
#<math>[a]_n\cdot[b]_n=[ab]_n\in\mathbb{Z}_n</math>
#<math>[a]_n\cdot([b]_n\cdot[c]_n)=([a]_n\cdot[b]_n)\cdot[c]_n</math>
#<math>[a]_n\cdot[1]_n=[a]_n=[1]_n\cdot[a]_n</math>
#<math>[a]_n\cdot[b]_n=[b]_n\cdot[a]_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>는 [[환 (수학)|가환환]]임을 알 수 있다.

==== 완전잉여계 ====
법 ''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)'''라고 한다.

=== 산술 ===
정수 <math>a,b,c,d</math>에 대해 다음이 성립한다.
#<math>a\equiv b\pmod m,\quad c\equiv d\pmod m</math>이면, <math>a\pm c\equiv b\pm d\pmod m</math> (복호동순)
#<math>ac\equiv bd\pmod m</math>
#<math>a\equiv b\pmod m</math>이면, <math>a^k\equiv b^k\pmod m</math> (<math>k\in\mathbb{N}</math>)
#<math>ab\equiv ac\pmod m</math>이고, <math>d=\gcd\left(a,m\right)</math>이면 <math>b\equiv c\pmod{\frac{m}{d}}</math>
#<math>a\equiv b\pmod m</math>이고, <math>n</math>이 <math>m</math>의 [[약수]]이면, <math>a\equiv b\pmod n</math>
#<math>a\equiv b\pmod m</math>이고, <math>d</math>가 <math>a,b,m</math>의 [[공약수]]이면, <math>\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{m}{d}}</math>

=== 기타 ===
#<math>p</math>가 [[소수]]이면, <math>\left(p-1\right)!\equiv-1\pmod p</math>. 역도 성립한다. ([[윌슨의 정리]])
#<math>p</math>가 소수이고, <math>p\not\mid a</math>이면 <math>a^{p-1}\equiv1\pmod p</math> ([[페르마의 소정리]])
#<math>n</math>이 양의 정수이고, <math>\gcd\left(a,n\right)=1</math>이면, <math>a^{\phi\left(n\right)}\equiv1\pmod n</math> ([[오일러의 정리]])

== 성질의 증명 ==
=== 동치 관계 ===
#<math>a-a=0</math>이고, <math>m\cdot0=0</math>이므로 <math>m\mid 0</math>. <math>\therefore a\equiv a\pmod m</math>
#<math>a\equiv b\mod m</math>이므로 <math>m\mid\left(a-b\right)</math>. 곧, <math>m\mid\left(b-a\right)</math>이고, 따라서 <math>b\equiv a\pmod m</math>
#<math>a\equiv b\pmod m</math>이므로 <math>m\mid\left(a-b\right)</math>. 또한, <math>b\equiv c\pmod m</math>이므로 <math>m\mid\left(b-c\right)</math>. 따라서 <math>m\mid\left\{\left(a-b\right)+\left(b-c\right)\right\}=\left(a-c\right)</math>. <math>\therefore a\equiv c\pmod m</math>

=== 산술 ===
#<math>a\equiv b\pmod m</math>이므로 <math>m\mid\left(a-b\right)</math>. <math>c\equiv d\pmod m</math>이므로 <math>m\mid\left(c-d\right)</math>. 따라서 <math>m\mid\left\{\left(a-b\right)\pm\left(c-d\right)\right\}=\left\{\left(a\pm c\right)-\left(b\pm d\right)\right\}</math>. <math>\therefore a\pm c\equiv b\pm d\pmod m</math>
#<math>a\equiv b\pmod m</math>이므로 <math>m\mid\left(a-b\right)</math>. <math>c\equiv d\pmod m</math>이므로 <math>m\mid\left(c-d\right)</math>. 따라서 <math>m\mid\left\{\left(a-b\right)c+\left(c-d\right)d\right\}=\left(ac-bd\right)</math>. <math>\therefore ac\equiv bd\pmod m</math>
#<math>a\equiv b\pmod m</math>이므로 <math>m\mid\left(a-b\right)</math>. <math>a^k-b^k</math>를 [[인수분해]]하면, <math>\left(a-b\right)\left(a^{k-1}+a^{k-2}b+\cdots+ab^{k-2}+b^{k-1}\right)</math>이고, 따라서 <math>m\mid\left(a^k-b^k\right)</math>. <math>\therefore a^k\equiv b^k\pmod m</math>
#<math>ab\equiv ac\pmod m</math>이므로 <math>m\mid a\left(b-c\right)</math>. 또한, <math>d=\gcd\left(a,m\right)</math>이므로, [[서로소]]인 적당한 정수 <math>x,y</math>에 대해, <math>a=dx,m=dy</math>이다. 따라서 <math>dy\mid dx\left(b-c\right)</math>. <math>\therefore y\mid x\left(b-c\right)</math>. 그런데 <math>x,y</math>가 서로소이므로, <math>y\mid\left(b-c\right)</math>.또한, <math>y=\frac{m}{d}</math>이므로, <math>\frac{m}{d}\mid\left(b-c\right)</math>. <math>\therefore b\equiv c\pmod{\frac{m}{d}}</math>
#<math>a\equiv b\pmod m</math>이므로 <math>m\mid\left(a-b\right)</math>. 또한, <math>n\mid m</math>이므로 <math>n\mid\left(a-b\right)</math>. <math>\therefore a\equiv b\pmod n</math>
#<math>a\equiv b\pmod m</math>이므로 <math>m\mid\left(a-b\right)</math>. 또한, <math>d</math>가 <math>a,b,m</math>의 [[공약수]]이므로, 서로소인 적당한 정수 <math>x,y,z</math>에 대해 <math>a=dx,b=dy,m=dz</math>가 성립한다. 따라서 <math>dz\mid d\left(x-y\right)</math>이고, <math>z\mid\left(x-y\right)</math>이다. 그런데 <math>x=\frac{a}{d},y=\frac{b}{d},m=\frac{m}{d}</math>이므로, <math>\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)</math>. <math>\therefore\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{m}{d}}</math>.

=== 기타 ===
[[윌슨의 정리]], [[페르마의 소정리]], [[오일러의 정리]] 항목을 각각 참조하자. 여기서는 생략.

== 사용 예 ==
*[[큿]]수<ref>0xrgb (2015.4.19). [http://rgb.wo.tc/45 퍼즐<nowiki>]</nowiki> 큿수]. 크리에이티브 커먼즈 저작자표시-비영리 4.0 국제로 배포됨. [[2015년]] [[5월 17일]]에 확인.</ref>
2와 7로만 이루어진 자연수를 큿수라고 하면 N자리이고 <math>2^N</math>의 배수인 큿수가 존재함을 모듈러산술로 보일 수 있다.
*<math>N=1</math>이면 2는 한 자리 자연수인 동시에 2의 배수다.
*<math>N=m</math>에 대해 명제가 성립한다고 가정하자. 그러면 ''m''자리이고 <math>2^m</math>의 배수인 큿수가 존재한다. 이 수를 ''k''라고 하자. 그러면
*:<math>2\cdot10^m+k\equiv k\pmod{2^{m+1}}</math>
*:<math>7\cdot10^m+k\equiv 2^m+k\pmod{2^{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>x</math>에 대하여 <math>ax\equiv b\pmod m</math>을 만족시키는 <math>x</math>의 법 <math>m</math>에 관한 합동식을 찾는 것을 일차합동식을 푼다고 말한다. <math>x</math>를 찾는다고 말해도 상관없지만, 그렇게 되면 해가 존재한다는 가정 하에 <math>x</math>값이 무수히 많이 존재하게 된다.

합동식을 풀기 위해서는 [[나누어떨어짐]], [[디오판토스 방정식]], [[나눗셈 정리]]를 기본으로 알아놔야 한다. 물론 합동식의 기본 성질만을 사용해 적당한 노가다로 해결할 수 있지만 그러면 배우는 의미가...

=== 해의 존재성 ===
<math>d=\gcd\left(a,m\right)</math>라 하자. 그럼 <math>ax\equiv b\pmod m</math>은
:#<math>d\not\mid b</math>일 때 해를 갖지 않는다.
:#<math>d\mid b</math>이면, 법 <math>m</math>에 대해 정확히 <math>d</math>개의 서로 다른 해를 갖는다.

==== 증명 ====
#<math>ax+my=b</math>를 만족하는 적당한 정수 <math>x,y</math>가 존재한다 가정하자. 여기서, <math>\gcd\left(a,m\right)=d\mid ax+my=b</math>이므로 <math>d\mid b</math>이다. 이는 <math>d\not\mid b</math>에 모순된다. 따라서 <math>ax+my=b</math>를 만족하는 정수 <math>x,y</math>는 존재하지 않고, 곧 <math>ax\equiv b\pmod m</math>의 해는 존재하지 않는다.
#[[디오판토스 방정식]] <math>ax+my=d</math>의 한 해를 <math>x_0,y_0</math>이라 하면, 일반해는 임의의 <math>k\in\mathbb{Z}</math>에 대해 <math>x_k=x_0+\frac{mk}{d},\,y_k=y_0-\frac{ak}{d}</math>이다. 여기서 <math>x_k</math>가 주어진 일차합동식을 만족시키는 모든 값이다.즉, 해가 '''존재'''한다. 이제 <math>k</math>를 <math>d</math>로 나누면, [[나눗셈 정리]]에 의해 <math>k=qd+r,\,\left(0\leq r< d\right)</math>을 만족하는 정수 <math>q,r</math>이 유일하게 존재한다. 이를 <math>x_k</math>에 대입하면, <math>x_k=x_0+\frac{m\left(qd+r\right)}{d}\equiv x_0+\frac{mr}{d}\equiv x_r\pmod m</math>이다. 그런데 <math>0\leq r< d</math>이므로, 임의의 <math>x_k</math>는 <math>x_0,x_1,\cdots,x_{d-1}</math>중 하나와 법 <math>m</math>에 대해 합동이다. 이제 <math>x_0,x_1,\cdots,x_{d-1}</math>가 법 <math>m</math>에 대해 서로 합동이 아님을 증명하면 된다. <math>0\leq i,j\leq d-1</math>인 정수 <math>i,j</math>에 대해, <math>x_i\equiv x_j\pmod m</math>이라 하면, <math>\frac{im}{d}\equiv\frac{jm}{d}\pmod m</math>이다. 그런데 <math>\gcd\left(\frac{m}{d},m\right)=\frac{m}{d}</math>이므로,<ref><math>d</math>가 <math>a</math>와 <math>m</math>의 [[최대공약수]]이므로, <math>d\mid m</math>이다. 따라서 <math>\frac{m}{d}</math>은 정수이고, 이 역시 <math>m</math>의 약수이다. 그런데 <math>\gcd\left(\frac{m}{d},m\right)\leq\frac{m}{d}</math>이고, <math>\frac{m}{d}\mid m</math>이므로, <math>\gcd\left(\frac{m}{d},m\right)=\frac{m}{d}</math>가 되어야 한다.</ref> 합동식의 성질에 의해 <math>i\equiv j\pmod d</math>이다. 이는 곧, <math>x_0,x_1,\cdots,x_{d-1}</math>이 법 <math>m</math>에 대해 합동이 아님을 의미한다.

=== 해법 ===
일차합동식을 푸는 방법은 [[디오판토스 방정식]], [[유클리드 호제법]] 등이 있지만, 제일 간단한 방법은 잉여 역수를 이용하는 것이다. 잉여 역수란, <math>a</math>와 <math>m</math>이 서로소일 때, <math>ax\equiv 1\pmod m</math>의 해 <math>x</math>를 법 <math>m</math>에 대한 잉여 역수라 부른다. 또한, 이 잉여 역수는 법 <math>m</math>에 대해 유일하다. 문제는 이 잉여 역수를 어떻게 이용하냐는 건데, 그냥 '''노가다'''를 하면 된다. 아래 예시를 통해 확인해 보자.
:<math>7x\equiv5\pmod{10}</math>을 풀고 싶다 하자. 먼저, <math>5\mid10</math>이므로 해가 존재하고, <math>d=\gcd\left(7,10\right)=1</math>이므로 해가 유일하다. 합동식의 양쪽에 -7을 곱하자. 그러면, <math>-49x\equiv-35\pmod{10}</math>이고, 이것은 <math>x\equiv5\pmod{10}</math>와 동치이다. 이는 법 10에 대한 7의 잉여 역수가 -7임을 이용한 것이다.
디오판토스 방정식을 사용한 풀이는 아래와 같다.
:<math>7x\equiv5\pmod{10}</math>이므로, 적당한 정수 <math>y</math>에 대해 <math>7x+10y=5</math>이다. 여기서 <math>x_0=5,y_0=-3</math>은 한 해이다. 또한, <math>\gcd\left(7,10\right)=1</math>이므로, 일반해는 <math>x=5+10t,y=-3-7t</math>이고, 원하는 것은 <math>x</math>에 관한 것이므로, <math>x\equiv5+10t\equiv5\pmod{10}</math>이 답이다.
그런데 잉여 역수나 디오판토스 방정식을 이용한 풀이에도 한계가 있다. <math>a</math>와 <math>m</math>이 커지면 무슨 수로 잉여 역수, 혹은 특이 해를 구할 것인가? 노가다에도 한계가 있다. 이럴 때는 [[오일러의 정리]]나 [[페르마의 소정리]]를 활용한다. 아래 예시를 통해 확인하자.
:<math>15x\equiv7\pmod{32}</math>를 풀고 싶다 하자. 15와 32가 서로소이고, <math>\phi\left(32\right)=16</math>이므로,<ref><math>\phi\left(x\right)</math>는 오일러 <math>\phi</math>함수로, <math>x</math>이하의 자연수 중, <math>x</math>와 서로소인 수의 개수를 말한다.</ref> <math>15^{16}\equiv1\pmod{32}</math>이다. 따라서, 양변에 <math>15^{15}</math>를 곱하면, <math>x\equiv7\cdot15^{15}\equiv9\pmod{32}</math>이다.

=== 이원 일차합동식 ===
풀어야 하는 변수가 두 개인 일차 합동식. <math>ax+by\equiv c\pmod m</math>같은 것을 말한다. 해의 존재성은 위 일차 합동식과 비슷하다. <math>d=\gcd\left(a,b,m\right)</math>이라 했을 때,
:#<math>d\not\mid c</math>이면 해가 존재하지 않는다.
:#<math>d\mid c</math>이면 이 이원 일차합동식은 법 <math>m</math>에 대하여 <math>md</math>개의 서로 다른 해를 갖는다.
풀이는 디오판토스 방정식을 활용한다. 아래 예시를 통해 확인하자.
:<math>2x+6y\equiv4\pmod{10}</math>을 풀고 싶다 하자. <math>\gcd\left(2,6,10\right)=2\mid4</math>이므로, 해가 존재하며, 법 10에 대해 20개의 서로 다른 해가 존재한다. 이제 주어진 합동식을 디오판토스 방정식으로 변형하자. 즉, 적당한 정수 <math>z</math>에 대해, <math>2x+6y+10z=4</math>이다.<br/><math>w=x+3y</math>라 두면, <math>w+5z=2</math>이 되고, 위 디오판토스 방정식은 <math>w_=-3,z_0=1</math>을 한 해로 갖는다. 따라서 일반해는, <math>w=-3+5s,z=1-s</math>이다.<br/>여기서 우리가 풀고자 하는 것은 <math>w</math>이다. 즉, <math>x+3y=-3+5s</math>. 이 디오판토스 방정식의 한 특이해는 <math>x_0=5s,y_0=-1</math>이고, 일반해는 <math>x=5s+3t,y=-1-t</math>이다. 여기서 <math>s</math>는 0, 1일 때, <math>t</math>는 0, 1, ..., 9일 때 법 10에 대해 <math>x,y</math>가 서로 다른 값을 가진다.

== 연립합동식 ==
합동식 여러 개가 연립되어 있는 형태. <math>\begin{cases}2x\equiv1\pmod5\\4x\equiv3\pmod7\\5x\equiv8\pmod{11}\end{cases}</math>같이 보기만 해도 짜증나는 식을 말한다. 푸는 방법은 먼저 각 일차합동식을 풀어준 뒤, [[중국인의 나머지 정리]]를 사용하여 풀면 된다. 더 자세한 내용은 항목을 참조하자. {{ㅊ|그런데 만약 일차합동식이 아니라면... 포기하면 편해}}

== 일반화 ==
[[추상대수학]]의 영역으로 가면 합동 관계를 다음과 같이 서술할 수 있다:

=== 군 ===
*''K''는 [[군 (수학)|군]] ''G''의 [[부분군]]이고 <math>a,b\in G</math>라 하자. 이때
:<math>ab^{-1}\in K</math>
이면 <math>a,b</math>는 법 ''K''에 대해 합동이라 하고 <math>a\equiv b\pmod K</math>로 나타낸다. 이 경우에도 <math>\equiv</math>는 동치관계라는 것을 보일 수 있다.

''K''가 ''G''의 [[정규부분군]]이라고 가정하자. 임의의 <math>a,b,c,d\in G</math>에 대해 <math>a\equiv b\pmod{K}</math>이고 <math>c\equiv d\pmod{K}</math>라면 다음 연산이 성립함을 보일 수 있다.
:<math>ac\equiv bd\pmod{K}</math>

=== 환 ===
*''I''는 [[환 (수학)|환]] ''R''의 [[부분환]]이고 <math>a,b\in R</math>라 하자. 이때
:<math>a-b\in I</math>
이면 <math>a,b</math>는 법 ''I''에 대해 합동이라 하고 <math>a\equiv b\pmod I</math>로 나타낸다. 이 경우에도 <math>\equiv</math>는 동치관계임을 보일 수 있다.

만약 ''I''가 [[아이디얼]]이라고 가정하자. 임의의 <math>a,b,c,d\in R</math>에 대해 <math>a\equiv b\pmod{I}</math>이고 <math>c\equiv d\pmod{I}</math>이면 다음 연산이 성립함을 보일 수 있다.
:<math>a+c\equiv b+d\pmod{I}</math>
:<math>ac\equiv bd\pmod{I}</math>
'''<math>ac\equiv bd\pmod{I}</math>의 증명.''' <math>a\equiv b\pmod{I}</math>이고 <math>c\equiv d\pmod{I}</math>이이므로
:<math>ac-bd=ac-bc+bc-bd=(a-b)c+b(c-d)=ic+bj</math>
인 <math>i,j\in I</math>가 존재한다. 이때 아이디얼의 정의에 의해 <math>ic\in I</math>이고 <math>bj\in I</math>이다. 따라서 <math>ic+bj\in I</math>이므로 원하는 결론을 얻는다.

== 같이 보기 ==
* [[기약잉여계]]
* [[나누어떨어짐]]
* [[나눗셈 정리]]
* [[디오판토스 방정식]]
* [[이차잉여]]
* [[아이디얼]]
* [[완전잉여계]]

{{각주}}
{{수}}
[[분류:정수론]]
[[분류:추상대수학]]