합동식

1. 개요

---

漢: 合同式 / En: Congruence
정수 $$a,b,m$$에 대하여, [math(m\mid\left(a-b\right))]일 때[1], $$a$$는 법 $$m$$에 대하여 $$b$$와 합동이다[2]($$a$$ is congruent to $$b$$ modulo $$m$$)라고 한다. 이때, 기호로는 $$a\equiv b\left(\text{mod}\,m\right)$$라고 쓴다. $$m$$를 합동의 법(modular)이라고 한다. 간단히 말해서, "$$a$$를 $$m$$으로 나눈 나머지는 $$b$$"라는 문장을 수식으로 표현한 것. [3][4]
일반적으로 나머지는 나누는 수보다 작지만, 합동식에서는 $$b$$값에 제한이 없다는 차이점은 존재한다. 다시 말해 $$a\equiv b\left(\text{mod}\,m\right)$$에서 b에 들어갈 수 있는 수 자체는 많이 있고, 그중에 가장 작은 양의 정수가 초등학교 때 배운 '나머지'이다.
나머지라는 개념 자체가 초등학교 시절 분수 전에 배우던 것이어서 보통 마치 가르치기 어려운 개념을 회피하기 위해 만들어진 것 같아 보인다. 그러나 '''천만의 말씀'''. 나머지는 수학에서 가장 신비로운 개념 중 하나로, 덧셈이나 곱셈에만 적용되는 줄 알았던 연산개념이 신기하게도 나머지에서 완전 같은 방법으로 적용된다는 점을 깨닫게 되면 정수론에 대한 관심이 꽃피게 되는 일이 많다.
대학교의 정수론 수업이나 특정 수학 과목의 정수론 파트를 듣지 않는 한 배울 일이 없지만, KMO를 비롯한 수학 경시대회를 준비한다면 '''반드시''' 알아놔야 할 것 중 하나. 2차 잉여까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다. 사실 경시대회 준비가 아니더라도 고등학교 때 이항정리 문제 중 합동식을 쓰면 편한 문제가 나오므로 알아놔서 절대 나쁠 건 없다.

2. 성질

---

1. (반사성) $$a\equiv a\left(\text{mod}\,m\right)$$이다.

증명

$$a-a=0$$이고, $$m\cdot0=0$$이므로 $$m\mid0$$이다. 따라서, $$a\equiv a\left(\text{mod}\,m\right)$$이다.

$$a-a=0$$이고, $$m\cdot0=0$$이므로 $$m\mid0$$이다. 따라서, $$a\equiv a\left(\text{mod}\,m\right)$$이다.}}}

2. (대칭성) $$a\equiv b\left(\text{mod}\,m\right)$$이면 $$b\equiv a\left(\text{mod}\,m\right)$$이다. (교환법칙)

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$m\mid\left(a-b\right)$$이므로 $$m\mid\left(b-a\right)$$이다. 따라서, $$b\equiv a\left(\text{mod}\,m\right)$$이다.}}}

3. (추이성) $$a\equiv b\left(\text{mod}\,m\right), b\equiv c\left(\text{mod}\,m\right)$$이면 $$a\equiv c\left(\text{mod}\,m\right)$$이다.

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이고, $$b\equiv c\left(\text{mod}\,m\right)$$이면 $$m\mid\left(b-c\right)$$이다. 그러므로 $$m\mid{\left(a-b\right)+\left(b-c\right)}$$이다. 즉, $$m\mid\left(a-c\right)$$이다. 따라서, $$a\equiv c\left(\text{mod}\,m\right)$$이다.}}}

4. $$a\equiv b\left(\text{mod}\,m\right), c\equiv d\left(\text{mod}\,m\right)$$이면, $$a\pm c\equiv b\pm d\left(\text{mod}\,m\right)$$이다. (복부호동순)

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이고, $$c\equiv d\left(\text{mod}\,m\right)$$이면 $$m\mid\left(c-d\right)$$이다. 그러므로 $$m\mid{\left(a-b\right)\pm\left(c-d\right)}$$이다. 즉, $$m\mid{\left(a\pm c\right)-\left(b\pm d\right)}$$이다. 따라서, $$a\pm c\equiv b\pm d\left(\text{mod}\,m\right)$$이다.}}}

5. $$a\equiv b\left(\text{mod}\,m\right), c\equiv d\left(\text{mod}\,m\right)$$이면, $$ac\equiv bd\left(\text{mod}\,m\right)$$이다.

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이고, $$c\equiv d\left(\text{mod}\,m\right)$$이면 $$m\mid\left(c-d\right)$$이다. 그러므로 $$m\mid{\left(a-b\right)c+\left(c-d\right)b}$$이다. 즉, $$m\mid\left(ac-bd\right)$$이다. 따라서, $$ac\equiv bd\left(\text{mod}\,m\right)$$이다.}}}

6. $$a\equiv b\left(\text{mod}\,m\right)$$이면, $$a^k\equiv b^k\left(\text{mod}\,m\right)$$이다.

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$k\geq2$$일 때, $$a^k-b^k =\left(a-b\right)\left(a^{k-1} + a^{k-2}b+\cdots +ab^{k-2}+b^{k-1}\right)$$이므로, $$m\mid\left(a^k-b^k\right)$$이다. 따라서, $$a^k\equiv b^k\left(\text{mod}\,m\right)$$이다.[5][6] }}}

7. $$ab\equiv ac\left(\text{mod}\,m\right)$$이고, $$d=\gcd\left(a,m\right)$$이면, $$b\equiv c\left(\text{mod}\,\frac{m}{d}\right)$$이다.

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$ab\equiv ac\left(\text{mod}\,m\right)$$이면, $$m\mid a\left(b-c\right)$$이다. $$d=\gcd\left(a,m\right)$$이므로, $$a=dx_1,m=dx_2$$를 만족하는 정수 $$x_1,x_2$$가 존재한다. 또한, $$dx_2\mid dx_1\left(b-c\right)$$이다. 또, $$x_1$$과 $$x_2$$가 서로소이므로 $$x_2\mid\left(b-c\right)$$이다. 그런데, $$x_2=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(b-c\right)$$이다. 따라서, $$b\equiv c\left(\text{mod}\,\frac{m}{d}\right)$$이다.

}}}

8. $$a\equiv b\left(\text{mod}\,m\right)$$이고, $$n$$이 $$m$$의 약수이면, $$a\equiv b\left(\text{mod}\,n\right)$$이다.

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또 $$n\mid m$$이면, $$n\mid\left(a-b\right)$$이다. 따라서, $$a\equiv b\left(\text{mod}\,n\right)$$이다.}}}

9. $$a\equiv b\left(\text{mod}\,m\right)$$이고, $$d>0$$이 $$a,b,m$$의 공약수이면, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

증명

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.

$$a\equiv b\left(\text{mod}\,m\right)$$이면 $$m\mid\left(a-b\right)$$이다. 또, $$d$$가 $$a,b,m$$의 공약수이므로 $$a=dx_1,b=dx_2,m=dx_3$$를 만족하는 정수 $$x_1,x_2,x_3$$가 존재한다. 또한, $$dx_3\mid d\left(x_1-x_2\right)$$이다. 그러므로, $$x_3\mid\left(x_1-x_2\right)$$이다. 그런데, $$x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}$$이므로, $$\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$$이다. 따라서, $$\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)$$이다.}}}

3. 일차합동식

---

3.1. 일차합동식의 정의

---

일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 $$ax\equiv b\left(\text{mod}\,m\right)$$인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. $$d=\gcd\left(a,m\right)$$[7]라 했을 때, $$d\nmid b$$이면[8] 합동식은 정수해를 갖지 않고, $$d\mid b$$[9]이면 법 $$m$$에 대해 정확히 $$d$$개의 서로 다른 해를 갖게된다. 해의 존재성에 대한 증명은 다음과 같다.

1. $$d\nmid b$$인데 해가 존재한다고 가정하자. 그럼 적당한 정수 $$y$$에 대하여 $$ax+my=b$$가 성립한다. 그런데 $$d\mid ax+my=b$$이므로 $$d\mid b$$이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다. 1.$$ax+my=b$$의 한 해를 $$x_0,y_0$$라 하면, 일반해는 $$x_k=x_0+\frac{mk}{d},y_k=y_0-\frac{ak}{d}$$의 꼴이다 (단 $$k$$는 임의의 정수).[10] 여기서 $$x_k$$가 합동식 $$ax\equiv b\left(\text{mod}\,m\right)$$을 만족시키는 모든 해이다. 나눗셈 정리에 의해 $$k=qd+r,\,\left(0\leq r<d\right)$$이고, 이를 $$x_k$$에 대입하면, $$x_k\equiv x_0+\frac{m\left(qd+r\right)}{d}\equiv x_0+\frac{mr}{d}\equiv x_r\left(\text{mod}\,m\right)$$이다. 이것은 곧 모든 $$x_k$$가 $$x_0,x_1,\cdots,x_{d-1}$$ 중 하나와 법 $$m$$에 대해 합동임을 의미한다. 이제 $$x_i\equiv x_j\left(\text{mod}\,m\right)$$, ($$0\leq i,j\leq d-1$$)라 가정하면, $$\frac{im}{d}\equiv\frac{jm}{d}\left(\text{mod}\,m\right)$$이다. 그런데 $$\gcd\left(\frac{m}{d},m\right)=\frac{m}{d}$$이므로 위 성질 7번에 의해 $$i\equiv j\left(\text{mod}\,d\right)$$이다. 이는 곧 $$x_0,x_1,\cdots,x_{d-1}$$가 법 $$m$$에 대해 서로 합동이 아님을 의미한다.

3.2. 일차합동식의 해법

---

크게 디오판토스 방정식, 유클리드 호제법, 잉여역수를 이용하는 방법으로 나눌 수 있다. 여기서는 다음 예제의 해법을 소개한다.

일차합동식 $$3x\equiv7\left(\text{mod}\,4\right)$$의 해를 구하시오.

3.2.1. 디오판토스 방정식 이용

---

적당한 정수 $$y$$에 대하여 $$3x+4y=7$$이다. 여기서 $$x_0=1,y_0=1$$은 한 해(특이해)임을 쉽게 알 수 있다. $$\gcd\left(3,4\right)=1$$이므로 일반해는 $$x=1+4t,\quad y=1-3t$$이다. 우리가 구하는 것은 $$x$$와 관련된 것이므로 $$x\equiv1\left(\text{mod}\,4\right)$$가 해이다.

3.2.2. 유클리드 호제법 이용

---

$$\gcd\left(3,4\right)=1$$이므로, 적당한 정수 $$a,b$$에 대해 $$3a+4b=1$$이다.[11] 실제로, $$\left(-1\right)\cdot3+1\cdot4=1$$이다. 이 사실은 우리에게 $$1\cdot x$$를 얻기 위하여 $$x$$의 계수를 바꿀 수 있음을 암시한다. 즉, 아래와 같이 된다.
$$4x\equiv0\left(\text{mod}\,4\right)\quad\cdots\left(1\right)$$
$$3x\equiv7\left(\text{mod}\,4\right)\quad\cdots\left(2\right)$$
그리고, (1) 식에서 (2)식을 빼면, x ≡ -7 (mod 4) 가 된다. -7 + 2*4 = 1 이므로 -7 ≡ 1 (mod 4) 이기에, 위 식을 x ≡ 1 (mod 4) 로 써도 된다.
그래서 답은 $$x\equiv1\left(\text{mod}\,4\right)$$이다.

3.2.3. 잉여역수 이용

---

법 4에 대한 곱셈표는 아래와 같다.[12]

×	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

위 표에서 보듯이 $$3\cdot3\equiv1\left(\text{mod}\,4\right)$$이다.
원래 식 $$3x\equiv7\left(\text{mod}\,4\right) $$ 의 양변에 3을 곱하면 $$3 \cdot 3x\equiv 3 \cdot 7\left(\text{mod}\,4\right) $$ 이 되는데, $$3\cdot3\equiv1\left(\text{mod}\,4\right)$$이고, $$ 21\equiv1\left(\text{mod}\,4\right)$$ 이므로 이를 정리하면
$$x\equiv 1\left(\text{mod}\,4\right) $$ 이 나온다.

4. 예제

---

합동식을 다룰줄 안다면 여러 경이로운 문제들의 답을 생각보다 쉽게 찾을 수 있다. 연습해보자!

4.1. 예제 1

---

$$7^{242}$$의 10과 1의 자리수를 합동식을 이용하여 구하시오.

[힌트]

$$7^4$$

[풀이]

$$7^4 = 2401 \equiv 1 \, (\text{mod} \, 100) \rightarrow (7^4)^{60} \equiv 1^{60} \,(\text{mod} \, 100) \rightarrow 7^{240} \equiv 1 \, (\text{mod} \, 100)$$
$$7^{242} = 7^{240} \times 7^2$$이니, $$7^{242} \equiv 7^2 \, (\text{mod} \, 100)$$.
그러므로 답은 $$49$$이다.

4.2. 예제 2

---

$$7^{7^{777}}$$의 1의 자리수를 합동식을 이용하여 구하시오.

[풀이]

$$7 \equiv -1 \, (\text{mod} \, 4) \, \rightarrow \, 7^{777} \equiv (-1)^{777} \, (\text{mod} \, 4) \rightarrow 7^{777} \equiv -1 \,(\text{mod} \, 4)$$.
그렇다면, $$7^{7^{777}}=7^{4n+(4-1)}=7^{4n+3}$$을 만족하는 자연수 $$n$$이 존재한다.
$$7^4 \equiv 1 \, (\text{mod} \, 10)$$이므로 $$7^{4n} \equiv 1 \, (\text{mod} \, 10)$$다. 따라서 $$7^{4n+3} \equiv 7^3 \equiv 3 \, (\text{mod} \, 10)$$이다.
답은 $$3$$이다.

4.3. 예제 3

---

$$ \displaystyle 1^2 + 2^2 + ...$$ $$ 98^2 + 99^2$$ 의 1의 자리수를 합동식을 이용하여 구하시오.

[풀이]

$$ \displaystyle 1^2 + 2^2 + ...$$ $$ 98^2 + 99^2 \equiv n\, (\text{mod} \, 10)$$이라 하자.
$$ 1^2 \equiv 11^2 \equiv \, ... \, \equiv 91^2 \,(\text{mod}\,10)$$이며, $$ 2^2 \equiv 12^2 \equiv \, ... \, \equiv 92^2 \,(\text{mod}\,10)$$등등 이니까
$$1^2+2^2+...\,9^2\equiv 11^2+12^2+...\,19^2\equiv...\equiv 91^2+92^2+...\,99^2\equiv \frac{n}{10}\,(\text{mod}\,10)$$다.
따라서 $$n$$은 $$10$$의 배수가 되는것이니, 답은 [math(0)]이다.

4.4. 예제 4

---

합동식 $$a \equiv b \, (\text{mod} \, m)$$에 대하여 $$a$$와 $$m$$이 서로소일 때, $$b$$와 $$m$$이 서로소임을 보이시오.

[풀이]

먼저 $$b$$와 $$m$$이 서로소가 아니라고 가정해보자. 그렇다면 $$a \equiv cd \, (\text{mod} \, cn)$$이 성립한다 (단, $$c > 1$$). 그렇다면 $$cn\,|\,(a - cd) \, \rightarrow cn\,|\,c(\frac{a}{c}-d) \, \rightarrow \, n \, | \, (\frac{a}{c}-d)$$ 다. 이게 성립하려면 $$a$$는 $$c$$의 배수여야하니, $$a$$와 $$m$$도 서로소가 아니다.
여기까지 우리가 증명한 건 "$$b$$와 $$m$$이 서로소가 아니라면, $$a$$와 $$m$$도 서로소가 아니다"인데, 이건 예제에 나오는 명제의 대우#s-4다. 따라서 예제의 명제 "$$a$$와 $$m$$이 서로소라면, $$b$$와 $$m$$역시 서로소다"도 참이다.

5. 관련 문서

---

• 중국인의 나머지 정리
• 윌슨의 정리
• 페르마의 소정리
• 오일러 정리
• 2차 잉여
• 이산 로그
• 수학 관련 정보
• 정수론

[1] $$a-b$$가 $$m$$으로 나누어 떨어질 때($$m$$ divides $$a-b$$). 즉, 적당한 정수 $$k$$에 대하여 $$a-b=km$$

[2] 기하학의 합동과는 다르다.

[3] $$0 \leq b < m$$일 때에

[4] 혹은 $$a-b=nm$$, $$n$$은 자연수.

[5] $$k=1$$일 때에는 자명하다.

[6] 사실 5의 증명을 반복 적용하면 된다.

[7] d가 a와 m의 최대공약수

[8] d가 b로 나누어 떨어지지 않으면

[9] d가 b로 나누어 떨어지면

[10] 디오판토스 방정식 참조

[11] 최대공약수 참조

[12] 직접 구해야 한다.