모듈러산술

개요

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

정의

양의 정수 m에 대해

[math]\displaystyle{ m\mid a-b }[/math]

이면 a, b는 법(modulus) m에 대해 합동(congruent)이라 하고,

[math]\displaystyle{ a\equiv b\pmod{m} }[/math]

로 표기한다. 이때 법 m이 고정되어 있지 않으면 동치관계나, 연산을 말하는 것이 의미가 없으므로 아래에서 법 m은 고정된 것으로 생각한다.

성질

동치관계

이때 [math]\displaystyle{ \equiv }[/math]는 동치관계이다. 즉, 임의의 정수 [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{ \equiv }[/math]가 동치관계이기 때문에 다음의 서술도 할 수 있다.

잉여류

[math]\displaystyle{ \equiv }[/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]에 대해 다음 성질이 성립한다.

1. [math]\displaystyle{ [a]_n+[b]_n=[a+b]_n\in\mathbb{Z}_n }[/math]
2. [math]\displaystyle{ [a]_n+([b]_n+[c]_n)=([a]_n+[b]_n)+[c]_n }[/math]
3. [math]\displaystyle{ [a]_n+[0]_n=[a]_n=[0]_n+[a]_n }[/math]
4. [math]\displaystyle{ [a]_n+[-a]_n=[0]_n=[-a]_n+[a]_n }[/math]
5. [math]\displaystyle{ [a]_n+[b]_n=[b]_n+[a]_n }[/math]
6. [math]\displaystyle{ [a]_n\cdot[b]_n=[ab]_n\in\mathbb{Z}_n }[/math]
7. [math]\displaystyle{ [a]_n\cdot([b]_n\cdot[c]_n)=([a]_n\cdot[b]_n)\cdot[c]_n }[/math]
8. [math]\displaystyle{ [a]_n\cdot[1]_n=[a]_n=[1]_n\cdot[a]_n }[/math]
9. [math]\displaystyle{ [a]_n\cdot[b]_n=[b]_n\cdot[a]_n }[/math]
10. [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{ a,b,c,d }[/math]에 대해 다음이 성립한다.

1. [math]\displaystyle{ a\equiv b\pmod m,\quad c\equiv d\pmod m }[/math]이면, [math]\displaystyle{ a\pm c\equiv b\pm d\pmod m }[/math] (복호동순)
2. [math]\displaystyle{ ac\equiv bd\pmod m }[/math]
3. [math]\displaystyle{ a\equiv b\pmod m }[/math]이면, [math]\displaystyle{ a^k\equiv b^k\pmod m }[/math] ([math]\displaystyle{ k\in\mathbb{N} }[/math])
4. [math]\displaystyle{ ab\equiv ac\pmod m }[/math]이고, [math]\displaystyle{ d=\gcd\left(a,m\right) }[/math]이면 [math]\displaystyle{ b\equiv c\pmod{\frac{m}{d}} }[/math]
5. [math]\displaystyle{ a\equiv b\pmod m }[/math]이고, [math]\displaystyle{ n }[/math]이 [math]\displaystyle{ m }[/math]의 약수이면, [math]\displaystyle{ a\equiv b\pmod n }[/math]
6. [math]\displaystyle{ a\equiv b\pmod m }[/math]이고, [math]\displaystyle{ d }[/math]가 [math]\displaystyle{ a,b,m }[/math]의 공약수이면, [math]\displaystyle{ \frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{m}{d}} }[/math]

기타

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

성질의 증명

동치 관계

1. [math]\displaystyle{ a-a=0 }[/math]이고, [math]\displaystyle{ m\cdot0=0 }[/math]이므로 [math]\displaystyle{ m\mid 0 }[/math]. [math]\displaystyle{ \therefore a\equiv a\pmod m }[/math]
2. [math]\displaystyle{ a\equiv b\mod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. 곧, [math]\displaystyle{ m\mid\left(b-a\right) }[/math]이고, 따라서 [math]\displaystyle{ b\equiv a\pmod m }[/math]
3. [math]\displaystyle{ a\equiv b\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. 또한, [math]\displaystyle{ b\equiv c\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(b-c\right) }[/math]. 따라서 [math]\displaystyle{ m\mid\left\{\left(a-b\right)+\left(b-c\right)\right\}=\left(a-c\right) }[/math]. [math]\displaystyle{ \therefore a\equiv c\pmod m }[/math]

산술

1. [math]\displaystyle{ a\equiv b\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. [math]\displaystyle{ c\equiv d\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(c-d\right) }[/math]. 따라서 [math]\displaystyle{ 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]\displaystyle{ \therefore a\pm c\equiv b\pm d\pmod m }[/math]
2. [math]\displaystyle{ a\equiv b\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. [math]\displaystyle{ c\equiv d\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(c-d\right) }[/math]. 따라서 [math]\displaystyle{ m\mid\left\{\left(a-b\right)c+\left(c-d\right)d\right\}=\left(ac-bd\right) }[/math]. [math]\displaystyle{ \therefore ac\equiv bd\pmod m }[/math]
3. [math]\displaystyle{ a\equiv b\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. [math]\displaystyle{ a^k-b^k }[/math]를 인수분해하면, [math]\displaystyle{ \left(a-b\right)\left(a^{k-1}+a^{k-2}b+\cdots+ab^{k-2}+b^{k-1}\right) }[/math]이고, 따라서 [math]\displaystyle{ m\mid\left(a^k-b^k\right) }[/math]. [math]\displaystyle{ \therefore a^k\equiv b^k\pmod m }[/math]
4. [math]\displaystyle{ ab\equiv ac\pmod m }[/math]이므로 [math]\displaystyle{ m\mid a\left(b-c\right) }[/math]. 또한, [math]\displaystyle{ d=\gcd\left(a,m\right) }[/math]이므로, 서로소인 적당한 정수 [math]\displaystyle{ x,y }[/math]에 대해, [math]\displaystyle{ a=dx,m=dy }[/math]이다. 따라서 [math]\displaystyle{ dy\mid dx\left(b-c\right) }[/math]. [math]\displaystyle{ \therefore y\mid x\left(b-c\right) }[/math]. 그런데 [math]\displaystyle{ x,y }[/math]가 서로소이므로, [math]\displaystyle{ y\mid\left(b-c\right) }[/math].또한, [math]\displaystyle{ y=\frac{m}{d} }[/math]이므로, [math]\displaystyle{ \frac{m}{d}\mid\left(b-c\right) }[/math]. [math]\displaystyle{ \therefore b\equiv c\pmod{\frac{m}{d}} }[/math]
5. [math]\displaystyle{ a\equiv b\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. 또한, [math]\displaystyle{ n\mid m }[/math]이므로 [math]\displaystyle{ n\mid\left(a-b\right) }[/math]. [math]\displaystyle{ \therefore a\equiv b\pmod n }[/math]
6. [math]\displaystyle{ a\equiv b\pmod m }[/math]이므로 [math]\displaystyle{ m\mid\left(a-b\right) }[/math]. 또한, [math]\displaystyle{ d }[/math]가 [math]\displaystyle{ a,b,m }[/math]의 공약수이므로, 서로소인 적당한 정수 [math]\displaystyle{ x,y,z }[/math]에 대해 [math]\displaystyle{ a=dx,b=dy,m=dz }[/math]가 성립한다. 따라서 [math]\displaystyle{ dz\mid d\left(x-y\right) }[/math]이고, [math]\displaystyle{ z\mid\left(x-y\right) }[/math]이다. 그런데 [math]\displaystyle{ x=\frac{a}{d},y=\frac{b}{d},m=\frac{m}{d} }[/math]이므로, [math]\displaystyle{ \frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right) }[/math]. [math]\displaystyle{ \therefore\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{m}{d}} }[/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{ x }[/math]에 대하여 [math]\displaystyle{ ax\equiv b\pmod m }[/math]을 만족시키는 [math]\displaystyle{ x }[/math]의 법 [math]\displaystyle{ m }[/math]에 관한 합동식을 찾는 것을 일차합동식을 푼다고 말한다. [math]\displaystyle{ x }[/math]를 찾는다고 말해도 상관없지만, 그렇게 되면 해가 존재한다는 가정 하에 [math]\displaystyle{ x }[/math]값이 무수히 많이 존재하게 된다.

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

해의 존재성

[math]\displaystyle{ d=\gcd\left(a,m\right) }[/math]라 하자. 그럼 [math]\displaystyle{ ax\equiv b\pmod m }[/math]은

1. [math]\displaystyle{ d\not\mid b }[/math]일 때 해를 갖지 않는다.
2. [math]\displaystyle{ d\mid b }[/math]이면, 법 [math]\displaystyle{ m }[/math]에 대해 정확히 [math]\displaystyle{ d }[/math]개의 서로 다른 해를 갖는다.

증명

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

해법

일차합동식을 푸는 방법은 디오판토스 방정식, 유클리드 호제법 등이 있지만, 제일 간단한 방법은 잉여 역수를 이용하는 것이다. 잉여 역수란, [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ m }[/math]이 서로소일 때, [math]\displaystyle{ ax\equiv 1\pmod m }[/math]의 해 [math]\displaystyle{ x }[/math]를 법 [math]\displaystyle{ m }[/math]에 대한 잉여 역수라 부른다. 또한, 이 잉여 역수는 법 [math]\displaystyle{ m }[/math]에 대해 유일하다. 문제는 이 잉여 역수를 어떻게 이용하냐는 건데, 그냥 노가다를 하면 된다. 아래 예시를 통해 확인해 보자.

[math]\displaystyle{ 7x\equiv5\pmod{10} }[/math]을 풀고 싶다 하자. 먼저, [math]\displaystyle{ 5\mid10 }[/math]이므로 해가 존재하고, [math]\displaystyle{ d=\gcd\left(7,10\right)=1 }[/math]이므로 해가 유일하다. 합동식의 양쪽에 -7을 곱하자. 그러면, [math]\displaystyle{ -49x\equiv-35\pmod{10} }[/math]이고, 이것은 [math]\displaystyle{ x\equiv5\pmod{10} }[/math]와 동치이다. 이는 법 10에 대한 7의 잉여 역수가 -7임을 이용한 것이다.

디오판토스 방정식을 사용한 풀이는 아래와 같다.

[math]\displaystyle{ 7x\equiv5\pmod{10} }[/math]이므로, 적당한 정수 [math]\displaystyle{ y }[/math]에 대해 [math]\displaystyle{ 7x+10y=5 }[/math]이다. 여기서 [math]\displaystyle{ x_0=5,y_0=-3 }[/math]은 한 해이다. 또한, [math]\displaystyle{ \gcd\left(7,10\right)=1 }[/math]이므로, 일반해는 [math]\displaystyle{ x=5+10t,y=-3-7t }[/math]이고, 원하는 것은 [math]\displaystyle{ x }[/math]에 관한 것이므로, [math]\displaystyle{ x\equiv5+10t\equiv5\pmod{10} }[/math]이 답이다.

그런데 잉여 역수나 디오판토스 방정식을 이용한 풀이에도 한계가 있다. [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ m }[/math]이 커지면 무슨 수로 잉여 역수, 혹은 특이 해를 구할 것인가? 노가다에도 한계가 있다. 이럴 때는 오일러의 정리나 페르마의 소정리를 활용한다. 아래 예시를 통해 확인하자.

[math]\displaystyle{ 15x\equiv7\pmod{32} }[/math]를 풀고 싶다 하자. 15와 32가 서로소이고, [math]\displaystyle{ \phi\left(32\right)=16 }[/math]이므로, [math]\displaystyle{ 15^{16}\equiv1\pmod{32} }[/math]이다. 따라서, 양변에 [math]\displaystyle{ 15^{15} }[/math]를 곱하면, [math]\displaystyle{ x\equiv7\cdot15^{15}\equiv9\pmod{32} }[/math]이다.

이원 일차합동식

풀어야 하는 변수가 두 개인 일차 합동식. [math]\displaystyle{ ax+by\equiv c\pmod m }[/math]같은 것을 말한다. 해의 존재성은 위 일차 합동식과 비슷하다. [math]\displaystyle{ d=\gcd\left(a,b,m\right) }[/math]이라 했을 때,

1. [math]\displaystyle{ d\not\mid c }[/math]이면 해가 존재하지 않는다.
2. [math]\displaystyle{ d\mid c }[/math]이면 이 이원 일차합동식은 법 [math]\displaystyle{ m }[/math]에 대하여 [math]\displaystyle{ md }[/math]개의 서로 다른 해를 갖는다.

풀이는 디오판토스 방정식을 활용한다. 아래 예시를 통해 확인하자.

[math]\displaystyle{ 2x+6y\equiv4\pmod{10} }[/math]을 풀고 싶다 하자. [math]\displaystyle{ \gcd\left(2,6,10\right)=2\mid4 }[/math]이므로, 해가 존재하며, 법 10에 대해 20개의 서로 다른 해가 존재한다. 이제 주어진 합동식을 디오판토스 방정식으로 변형하자. 즉, 적당한 정수 [math]\displaystyle{ z }[/math]에 대해, [math]\displaystyle{ 2x+6y+10z=4 }[/math]이다.
[math]\displaystyle{ w=x+3y }[/math]라 두면, [math]\displaystyle{ w+5z=2 }[/math]이 되고, 위 디오판토스 방정식은 [math]\displaystyle{ w_=-3,z_0=1 }[/math]을 한 해로 갖는다. 따라서 일반해는, [math]\displaystyle{ w=-3+5s,z=1-s }[/math]이다.
여기서 우리가 풀고자 하는 것은 [math]\displaystyle{ w }[/math]이다. 즉, [math]\displaystyle{ x+3y=-3+5s }[/math]. 이 디오판토스 방정식의 한 특이해는 [math]\displaystyle{ x_0=5s,y_0=-1 }[/math]이고, 일반해는 [math]\displaystyle{ x=5s+3t,y=-1-t }[/math]이다. 여기서 [math]\displaystyle{ s }[/math]는 0, 1일 때, [math]\displaystyle{ t }[/math]는 0, 1, ..., 9일 때 법 10에 대해 [math]\displaystyle{ x,y }[/math]가 서로 다른 값을 가진다.

연립합동식

합동식 여러 개가 연립되어 있는 형태. [math]\displaystyle{ \begin{cases}2x\equiv1\pmod5\\4x\equiv3\pmod7\\5x\equiv8\pmod{11}\end{cases} }[/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]는 동치관계라는 것을 보일 수 있다.

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]

환

• I는 환 R의 부분환이고 [math]\displaystyle{ a,b\in R }[/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]이므로 원하는 결론을 얻는다.

같이 보기

• 기약잉여계
• 나누어떨어짐
• 나눗셈 정리
• 디오판토스 방정식
• 이차잉여
• 아이디얼
• 완전잉여계