합동식 편집하기

{{학술}}

Modulus, Congruence
== 개요 ==
합동 산술(Modular Arithmetic)이라고 부르기도 한다. 간단히 설명하면, 어떤 두 정수를 다른 한 정수로 나눈 나머지로 비교하는 식이라 할 수 있다. [[기하학]]의 합동과는 이름만 같고, 내용은 천지차이다. 한국의 교육과정에서는 다루지 않지만, [[수학 경시대회]]를 준비한다면 반드시 알아놔야할 개념 중 하나다. 사실, 수학 경시대회를 준비하지 않아도 배워두면 쓸 데가 많다. 대표적으로 고등학교의 [[이항정리]] 응용 문제.

== 정의 ==
[[정수]] <math>a</math>를 다른 정수 <math>m</math>으로 나눈 나머지를 <math>b</math>라 하자. 그럼 두 정수 <math>a,b</math>는 법 <math>m</math>에 대하여 합동이라고 하며, 기호로는 <math>a\equiv b\mod m</math>으로 나타낸다. 위 정의는 <math>\exists k\in\mathbb{Z}\text{ s.t. }a-b=mk</math>와 동치임을 쉽게 알 수 있다. 혹은 <math>m\mid\left(a-b\right)</math>와 동치라 해도 맞다<ref><math>\mid</math>는 나누어 떨어진다는 기호</ref>

== 성질 ==
=== 동치 관계 ===
#<math>a\equiv a\mod m</math> (반사율)
#<math>a\equiv b\mod m</math>이면, <math>b\equiv a\mod m</math> (대칭률)
#<math>a\equiv b\mod m,\,b\equiv c\mod m</math>이면, <math>a\equiv c\mod m</math> (추이율)
위 세 성질로 부터, 합동은 [[동치관계]]임을 알 수 있다.
=== 산술 ===
#<math>a\equiv b\mod m,\,c\equiv d\mod m</math>이면, <math>a\pm c\equiv b\pm d\mod m</math> (복호동순)
#<math>a\equiv b\mod m,\,c\equiv d\mod m</math>이면, <math>ac\equiv bd\mod m</math>
#<math>a\equiv b\mod m</math>이면, <math>a^k\equiv b^k\mod m</math>
#<math>ab\equiv ac\mod m</math>이고, <math>d=\gcd\left(a,m\right)</math>이면 <math>b\equiv c\mod\frac{m}{d}</math>
#<math>a\equiv b\mod m</math>이고, <math>n</math>이 <math>m</math>의 [[약수]]이면, <math>a\equiv b\mod n</math>
#<math>a\equiv b\mod m</math>이고, <math>d</math>가 <math>a,b,m</math>의 [[공약수]]이면, <math>\frac{a}{d}\equiv\frac{b}{d}\mod\frac{m}{d}</math>
=== 기타 ===
#<math>p</math>가 [[소수]]이면, <math>\left(p-1\right)!\equiv-1\mod p</math>. 역도 성립한다. ([[윌슨의 정리]])
#<math>p</math>가 소수이고, <math>p\nmid a</math>이면 <math>a^{p-1}\equiv1\mod p</math> ([[페르마의 소정리]])
#<math>n</math>이 양의 정수이고, <math>\gcd\left(a,n\right)=1</math>이면, <math>a^{\phi\left(n\right)}\equiv1\mod n</math> ([[오일러의 정리]])

== 증명 ==
=== 동치 관계 ===
#<math>a-a=0</math>이고, <math>m\cdot0=0</math>이므로 <math>m\mid0</math>. <math>\therefore a\equiv a\mod 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\mod m</math>
#<math>a\equiv b\mod m</math>이므로 <math>m\mid\left(a-b\right)</math>. 또한, <math>b\equiv c\mod 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\mod m</math>

=== 산술 ===
#<math>a\equiv b\mod m</math>이므로 <math>m\mid\left(a-b\right)</math>. <math>c\equiv d\mod 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\mod m</math>
#<math>a\equiv b\mod m</math>이므로 <math>m\mid\left(a-b\right)</math>. <math>c\equiv d\mod 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\mod m</math>
#<math>a\equiv b\mod 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\mod m</math>
#<math>ab\equiv ac\mod 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\mod\frac{m}{d}</math>
#<math>a\equiv b\mod 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\mod n</math>
#<math>a\equiv b\mod 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}\mod\frac{m}{d}</math>.

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

== 일차합동식 ==
미지수 <math>x</math>에 대하여 <math>ax\equiv b\mod 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\mod m</math>은
:#<math>d\nmid b</math>일 때 해를 갖지 않는다.
:#<math>d\mid b</math>이면, 법 <math>m</math>에 대해 정확히 <math>d</math>개의 서로 다른 해를 갖는다.

==== 증명 ====
#<math>ax+my=d</math>를 만족하는 적당한 정수 <math>x,y</math>가 존재한다 가정하자. 여기서, <math>\gcd\left(a,m\right)=d\mid ax+my=b</math>이므로 <math>d\mid b</math>이다. 이는 <math>d\nmid b</math>에 모순된다. 따라서 <math>ax+my=d</math>를 만족하는 정수 <math>x,y</math>는 존재하지 않고, 곧 <math>ax\equiv b\mod 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\mod 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\mod m</math>이라 하면, <math>\frac{im}{d}\equiv\frac{jm}{d}\mod 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\mod 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\mod m</math>의 해 <math>x</math>를 법 <math>m</math>에 대한 잉여 역수라 부른다. 또한, 이 잉여 역수는 법 <math>m</math>에 대해 유일하다. 문제는 이 잉여 역수를 어떻게 이용하냐는 건데, 그냥 '''노가다'''를 하면 된다. 아래 예시를 통해 확인해 보자.
:<math>7x\equiv5\mod10</math>을 풀고 싶다 하자. 먼저, <math>5\mid10</math>이므로 해가 존재하고, <math>d=\gcd\left(7,10\right)=1</math>이므로 해가 유일하다. 합동식의 양쪽에 -7을 곱하자. 그러면, <math>-49x\equiv-35\mod10</math>이고, 이것은 <math>x\equiv5\mod10</math>와 동치이다. 이는 법 10에 대한 7의 잉여 역수가 -7임을 이용한 것이다.
디오판토스 방정식을 사용한 풀이는 아래와 같다.
:<math>7x\equiv5\mod10</math>이므로, 적당한 정수 <math>y</math>에 대해 <math>7x+10y=5</math>이다. 여기서 <math>x=5,y=-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\mod10</math>이 답이다.
그런데 잉여 역수나 디오판토스 방정식을 이용한 풀이에도 한계가 있다. <math>a</math>와 <math>m</math>이 커지면 무슨 수로 잉여 역수, 혹은 특이 해를 구할 것인가? 노가다에도 한계가 있다. 이럴 때는 [[오일러의 정리]]나 [[페르마의 소정리]]를 활용한다. 아래 예시를 통해 확인하자.
:<math>15x\equiv7\mod32</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\mod32</math>이다. 따라서, 양변에 <math>15^{15}</math>를 곱하면, <math>x\equiv7\cdot15^{15}\equiv9\mod32</math>이다.

== 연립합동식 ==

== 관련 항목 ==
*[[나누어떨어짐]]
*[[나눗셈 정리]]
*[[디오판토스 방정식]]
*[[이차 잉여]]
*[[완전잉여계]]
*[[기약잉여계]]

{{각주}}
[[분류:정수론]]