모듈로 합동(Congruent Modulo)

정의1

임의의 정수 $a,b \in \mathbb{Z}$가 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해  

$(a - b)/n \in \mathbb{Z}$으로 $a-b = q\cdot n$이 되는 정수 $q \in \mathbb{Z}$가 존재할때

$a$와 $b$가 $n$에 대해 모듈로 합동(congruent modulo n)이라 하고 $a \equiv b \pmod{ n}$로 표기한다.

$(a - b)/n \notin \mathbb{Z}$이면 $a$와 $b$가 $n$에 대해 모듈로 합동이 아니라 하고 $a \not \equiv b \pmod{ n}$로 표기한다.

 

나눗셈 정리로 $a = q\cdot n + r$이고 $0\le r < n$인 정수 $q,r \in \mathbb{Z}$이 유일하게 존재하므로

$\bmod n = \{ (a,r) \in \mathbb{Z} \times \mathbb{Z} : \text{어떤 } q \in \mathbb{Z} \text{에 대해 } a= q\cdot n+r\text{이고 } 0 \le r < n \text{이다. } \}$인

함수$\bmod n : \mathbb{Z} \to \mathbb{Z}$을 나머지 연산자(remainder operator) 또는 모듈로 연산자(modulo operator)로 정의한다.

$\bmod n$는 이항연산과 비슷하게 $(\! \bmod n)(a) =r = a \bmod n $으로 표기한다.

 

 

 

정리1

임의의 정수 $a,b \in \mathbb{Z}$와 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해

$a \equiv b \pmod{ n}$이기 위한 필요충분조건은 $a \bmod n$ $ = b \bmod n$인 것이다.

증명

$a \equiv b \pmod{ n}$이면 

$a-b = k\cdot n$이 되는 정수 $k \in \mathbb{Z}$가 존재하므로 $a = b + k\cdot n$이고 

$n > 0$이므로 나눗셈 정리로 $b = q\cdot n + r$이고 $0\le r <n$인 정수 $q,r \in \mathbb{Z}$가 존재한다.

따라서 $a = b + k \cdot n = (q\cdot n + r) + k\cdot n = (q + k)\cdot n + r$이 되어

$a$와 $b$를 $n$으로 나누었을때의 나머지는 $r$이므로 $ a\bmod n = r = b \bmod n$이다.

역으로 $ a\bmod n = r = b \bmod n$이면 

$a = q_1\cdot n + r$과 $b = q_2\cdot n + r$이 성립하고 $0\le r < n$인 정수 $q_1,q_2,r \in \mathbb{Z}$이 존재하여

$a - b = (q_1\cdot n + r) - (q_2\cdot n + r) = (q_1 -q_2)\cdot n$이므로 $(a - b)/n \in \mathbb{Z}$이고 $a \equiv b \pmod{ n}$이다.

 

 

 

정리2

임의의 정수 $a,b,c,d \in \mathbb{Z}$와 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 다음이 성립한다.

반사성 : $a \equiv a \pmod{ n}$

대칭성 : $a\equiv b \pmod{n}$이면 $b\equiv a \pmod{n}$이다.

추이성 : $a\equiv b \pmod{n}$이고 $b\equiv c \pmod{n}$이면 $a\equiv c \pmod{n}$이다.

덧셈에 대해 닫힘 :

1. $a\equiv b \pmod{n}$이고 $c\equiv d \pmod{n}$이면 $a +c \equiv b +d \pmod{n}$이다.

2. $a\equiv b \pmod{n}$이면 $a + c\equiv b +c \pmod{n}$이다.

곱셈에 대해 닫힘 : 

1. $a\equiv b \pmod{n}$이고 $c\equiv d \pmod{n}$이면 $a \cdot c \equiv b \cdot d \pmod{n}$이다.

2. $a\equiv b \pmod{n}$이면 $a \cdot c\equiv b \cdot c \pmod{n}$이다.

거듭제곱 : $a\equiv b \pmod{n}$이면 모든 $k \in \mathbb{N}$에 대해 $a^k \equiv b^k \pmod{n}$이다.

증명

반사성

$a - a = 0 = 0\cdot n$이므로 $a \equiv a \pmod{ n}$이다.

대칭성

$a\equiv b \pmod{n}$이면 $a - b = q\cdot n$인 정수 $q \in \mathbb{Z}$가 존재하고 $b - a = -q \cdot n$이므로 $b\equiv a \pmod{n}$이다.

추이성

$a\equiv b \pmod{n}$이고 $b\equiv c \pmod{n}$이면 $a - b = q_1\cdot n$이고 $b - c = q_2\cdot n$인 정수 $q_1,q_2 \in \mathbb{Z}$가 존재하여

$a- c=a - b + b - c = q_1\cdot n + q_2\cdot n= (q_1 + q_2)\cdot n$이므로 $a\equiv c \pmod{n}$이다.

덧셈에 대해 닫힘

1.

$a\equiv b \pmod{n}$이고 $c\equiv d \pmod{n}$이면 $a - b = q_1\cdot n$이고 $c - d = q_2\cdot n$인 정수 $q_1,q_2 \in \mathbb{Z}$가 존재하여

$a + c - (b + d) = a - b + c - d = q_1\cdot n + q_2\cdot n = (q_1 + q_2)\cdot n$이므로 $a +c \equiv b +d \pmod{n}$이다.

2.

$a\equiv b \pmod{n}$이면 $a - b = q\cdot n$인 정수 $q \in \mathbb{Z}$가 존재하여

$a + c - (b + c) = a + c - c -b  = a- b = q\cdot n$이므로 $a + c\equiv b +c \pmod{n}$이다.

곱셈에 대해 닫힘

1.

$a\equiv b \pmod{n}$이고 $c\equiv d \pmod{n}$이면 $a - b = q_1\cdot n$이고 $c - d = q_2\cdot n$인 정수 $q_1,q_2 \in \mathbb{Z}$가 존재하여

$\begin{align*}a\cdot c - b\cdot d & = a\cdot c - b\cdot c + b\cdot c - b\cdot d \\[0.5em] & = c\cdot (a- b) + b\cdot (c -d) \\[0.5em] & = c\cdot q_1\cdot n + b\cdot q_2 \cdot n \\[0.5em] & = (c\cdot q_1 + b\cdot q_2)\cdot n \text{ 이므로} \end{align*}$

$a \cdot c \equiv b \cdot d \pmod{n}$이다.

2. 

$a\equiv b \pmod{n}$이면 $a - b = q\cdot n$인 정수 $q \in \mathbb{Z}$가 존재하여

$a\cdot c -b\cdot c = c\cdot (a -b ) = c\cdot q\cdot n $이므로 $a \cdot c\equiv b \cdot c \pmod{n}$이다.

거듭제곱

$k = 0$이면 $a^0 - b^0 = 1 - 1 = 0 = 0\cdot n$이므로 $a^0 \equiv b^0 \pmod{n}$이다.

$k\ge 1$일때 $k \in \mathbb{Z}^+$에 대해서는 귀납법을 사용한다.

$k = 1$이면 자명하게 성립하므로

모든 $m \in \mathbb{Z}^+$에 대해 $a^m \equiv b^m \pmod{n}$이라 가정할때

$a^m - b^m = q_m\cdot n$인 정수 $q_m \in \mathbb{Z}$이 존재하여 $a^m = b^m + q_m\cdot n$이므로

$\begin{align*} a^{m +1} - b^{m+1} & = a^m\cdot a - b^m \cdot b \\[0.5em] & = (b^m + q_m\cdot n)\cdot a - b^m \cdot b \\[0.5em] & = a\cdot b^m + a\cdot q_m\cdot n - b^m \cdot b \\[0.5em] & = (a -b)\cdot b^m + a\cdot q_m \cdot n \\[0.5em] & = q_1 \cdot n \cdot b^m + a\cdot q_m \cdot n \\[0.5em] & = (q_1 \cdot b^m + a\cdot q_m)\cdot n \text{ 이 되어}  \end{align*}$

모든 $k \in \mathbb{N}$에 대해 $a^k \equiv b^k \pmod{n}$이다.

 

 

 

정리9

임의의 정수 $a, b \in \mathbb{Z}$와 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 다음이 성립한다.

1. $(a + b) \bmod n$ $ = ((a \bmod n) +  (b \bmod n) ) \bmod n = ((a \bmod n) +  b ) \bmod n = (a  +  (b \bmod n) ) \bmod n $

2. $ (a\cdot b) \bmod n = ((a\bmod n)\cdot (b \bmod n)) \bmod n = ((a\bmod n)\cdot b) \bmod n = (a\cdot (b \bmod n)) \bmod n$ 

증명

모듈로 연산자의 정의로

$a = q_a\cdot n + a \bmod n$이고 $0\le a \bmod n < n$인 $q_a \in Z$가 존재하여

$a - a\bmod n = q_a \cdot n$이고 $a \equiv a \bmod n \pmod{ n}$이다.

또 $b = q_b\cdot n + b \bmod n$이고 $0\le b \bmod n < n$인 $q_b \in Z$가 존재하여

$b - b\bmod n = q_b \cdot n$이고 $b \equiv b \bmod n \pmod{ n}$이다.

1.

모듈로 합동 정리로

$ \begin{align*} a+ b & \equiv  a \bmod n + b \bmod n \pmod{ n} \\[0.5em] & \equiv a + b\bmod n \pmod{n} \\[0.5em] & \equiv a \bmod n +b \pmod{n} \text{ 이므로} \end{align*}$

위 정리로

$(a+b)\bmod n = ((a\bmod n) + (b \bmod n)) \bmod n $이고

$(a+b)\bmod n = (a + (b\bmod n)  ) \bmod n $이고

$ (a+b)\bmod n = ((a\bmod n) + b ) \bmod n $이다.

2.

모듈로 합동 정리로

$ \begin{align*} a\cdot b & \equiv  (a \bmod n) \cdot ( b \bmod n) \pmod{ n} \\[0.5em] & \equiv a \cdot ( b\bmod n ) \pmod{n} \\[0.5em] & \equiv ( a \bmod n ) \cdot b \pmod{n} \text{ 이므로} \end{align*}$

위 정리로

$(a\cdot b)\bmod n= ((a\bmod n) \cdot (b \bmod n)) \bmod n $이고 

$(a\cdot b)\bmod n= (a \cdot (b\bmod n)  ) \bmod n $이고 

$(a\cdot b)\bmod n = ( (a \bmod n) \cdot b ) \bmod n $이다.

 

 

 

정리3

임의의 정수 $a,b,c \in \mathbb{Z}$와 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해

$c\cdot a \equiv c\cdot b \pmod{ n}$이면 $a \equiv b \pmod{\dfrac{n}{\gcd(c,n)}}$이다.

증명

$c\cdot a \equiv c\cdot b \pmod{ n}$이면 $c\cdot (a - b) = c\cdot a - c\cdot b = q\cdot n$인 정수 $q \in \mathbb{Z}$가 존재하고

$\gcd(c,n)$ $ = d$이면 $c = s_1\cdot d$이고 $n = s_2\cdot d$인 정수 $s_1,s_2 \in \mathbb{Z}$가 존재한다.

$ s_1\cdot d \cdot (a - b) =  c\cdot (a - b)  = q\cdot n = q\cdot s_2\cdot d$이므로 $s_1\cdot (a - b) = q\cdot s_2$가 되어 $(s_1 \cdot (a-b)) / s_2 \in \mathbb{Z}$이고

최대공약수 정리로 $\gcd(s_1, s_2) = \gcd(\frac{c}{d},\frac{n}{d}) = 1$이므로 유클리드 보조정리로 $ (a-b) / s_2 \in \mathbb{Z}$이다.

따라서 $a - b = k\cdot s_2 = k \cdot \dfrac{n}{d} = k\cdot \dfrac{n}{\gcd(c,n)}$인 정수 $k \in \mathbb{Z}$가 존재하여 $a \equiv b \pmod{\dfrac{n}{\gcd(c,n)}}$이다.

 

 

 

정리10

모든 $n \in \mathbb{N}$에 대해 $2^n \bmod 3$은 $1$ 또는 $2$이다.

증명

$n \in \mathbb{N}$에 대한 귀납법을 사용하여 증명한다.

$n = 0$이면 $2^0 = 1 = 0\cdot 3 + 1$이므로 $2^0 \bmod 3 = 1$이다.

모든 $k \in \mathbb{N}$에 대해 정리가 성립할때 

$2^k \bmod 3 = 1$이면

$2 = 0\cdot 3 +2 $이고 $2 \bmod 3 = 2$이므로

위 정리로 $2^{k+1} \bmod 3 = (2^k \cdot 2) \bmod 3 = ((2^k \bmod 3) \cdot (2 \bmod 3)  ) \bmod 3 = (1\cdot 2) \bmod 3 = 2  $이다.

$2^k \bmod 3 = 2$이면

$4 = 1\cdot 3 + 1 $이고 $4 \bmod 3 = 1$이므로

위 정리로 $2^{k+1} \bmod 3 = (2^k \cdot 2) \bmod 3 = ((2^k \bmod 3) \cdot (2 \bmod 3)  ) \bmod 3 = (2\cdot 2) \bmod 3 = 1 $이다.

따라서 모든 $n \in \mathbb{N}$에 대해 $2^n \bmod 3$은 $1$ 또는 $2$이다.

 

 

 

정의2

임의의 정수 $a \in \mathbb{Z}$에 대해

$a = 2\cdot k$가 되는 정수 $k \in \mathbb{Z}$가 존재하면 $a$를 짝수(even number)라 정의하고

$a$가 짝수가 아니면 $a$를 홀수(odd number)로 정의한다.

아래 정리로 홀수는 $a = 2\cdot k +1$이 되는 정수 $k \in \mathbb{Z}$가 존재한다.

 

 

 

정리4

임의의 정수 $a \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $a$가 짝수이기 위한 필요충분조건은 $a \equiv 0 \pmod{ 2}$인 것이다.

2. $a$가 홀수이기 위한 필요충분조건은 $a = 2\cdot k +1$이 되는 정수 $k \in \mathbb{Z}$가 존재하는 것이다.

3. $a$가 홀수이기 위한 필요충분조건은 $a \equiv 1 \pmod{ 2}$인 것이다.

증명

1.

$a$가 짝수이면

$a = 2\cdot k$가 되는 정수 $k \in \mathbb{Z}$가 존재하므로 $a - 0 = 2\cdot k$가 되어 $a \equiv 0 \pmod{ 2}$이다.

$a \equiv 0 \pmod{ 2}$이면

$a - 0 = 2\cdot k$가 되는 정수 $k \in \mathbb{Z}$가 존재하므로 $a = 2\cdot k$가 되어 $a$는 짝수이다.

2.

$a$가 홀수이면

짝수가 아니므로 $a = 2\cdot q +r$이고 $r \ne 0$이 되는 정수 $q,r \in \mathbb{Z}$이 존재한다.

$2 > 0$이므로 나눗셈 정리로 $0\le r < 2$인데 $r \ne 0$이므로 $r = 1$이다.

$a = 2\cdot k +1$이 되는 정수 $k \in \mathbb{Z}$가 존재하면

$a - 1 = 2\cdot k$이므로 $a \equiv 1 \pmod{ 2}$이 되어 $a \not\equiv 0 \pmod{ 2}$이므로 1번의 대우로 $a$는 홀수이다.

3.

$a$가 홀수이면 

2번으로 $a = 2\cdot k +1$이 되는 정수 $k \in \mathbb{Z}$가 존재하여 $a - 1 = 2\cdot k$이므로 $a \equiv 1 \pmod{ 2}$이다.

$a \equiv 1 \pmod{ 2}$이면

$a - 1 = 2\cdot k$가 되는 정수 $k \in \mathbb{Z}$가 존재하여 $a = 2\cdot k +1$이므로 2번으로 $a$는 홀수이다.

 

 

 

정리5

임의의 정수 $a,b \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $a$가 짝수이고 $b$도 짝수이면 $a + b$도 짝수이다.

2. $a$가 홀수이고 $b$가 짝수이면 $a+ b$는 홀수이다.

3. $a$가 홀수이고 $b$도 홀수이면 $a+ b$는 짝수이다.

4. $a$가 짝수이고 $b$도 짝수이면 $a \cdot b$도 짝수이다.

5. $a$가 홀수이고 $b$가 짝수이면 $a \cdot b$는 짝수이다.

6. $a$가 홀수이고 $b$도 홀수이면 $a \cdot b$는 홀수이다.

7. $a^2 = a\cdot a$가 짝수이면 $a$는 짝수이다.

8. $a^2 = a\cdot a$가 홀수이면 $a$는 홀수이다.

증명

1.

$a$가 짝수이고 $b$도 짝수이면

$a= 2\cdot k_1$이고 $b = 2\cdot k_2$인 정수 $k_1,k_2 \in \mathbb{Z}$가 존재하므로

$a + b = 2\cdot k_1 + 2\cdot k_2 = 2\cdot (k_1 + k_2)$가 되어 $a + b$는 짝수이다.

2.

$a$가 홀수이고 $b$가 짝수이면 

$a= 2\cdot k_1 +1 $이고 $b = 2\cdot k_2$인 정수 $k_1,k_2 \in \mathbb{Z}$가 존재하므로

$a + b = 2\cdot k_1 + 1 + 2\cdot k_2 = 2\cdot (k_1 + k_2) + 1$이 되어 $a+ b$는 홀수이다.

3. 

$a$가 홀수이고 $b$도 홀수이면

$a= 2\cdot k_1 +1 $이고 $b = 2\cdot k_2+1$인 정수 $k_1,k_2 \in \mathbb{Z}$가 존재하므로

$a + b = 2\cdot k_1 + 1 +2\cdot k_2 + 1 = 2\cdot (k_1 + k_2) + 2 = 2\cdot (k_1 + k_2 + 1)$이 되어 $a+ b$는 짝수이다.

4.

$a$가 짝수이고 $b$도 짝수이면

$a= 2\cdot k_1$이고 $b = 2\cdot k_2$인 정수 $k_1,k_2 \in \mathbb{Z}$가 존재하므로

$a\cdot b = 2\cdot k_1 \cdot 2\cdot k_2 = 2 \cdot (2\cdot k_1 \cdot k_2)$가 되어 $a \cdot b$도 짝수이다.

5.

$a$가 홀수이고 $b$가 짝수이면

$a= 2\cdot k_1 +1 $이고 $b = 2\cdot k_2$인 정수 $k_1,k_2 \in \mathbb{Z}$가 존재하므로

$a\cdot b = (2\cdot k_1 + 1)\cdot 2\cdot k_2 = 2\cdot (2\cdot k_1\cdot k_2 + k_2)$가 되어 $a \cdot b$는 짝수이다.

6. 

$a$가 홀수이고 $b$도 홀수이면

$a= 2\cdot k_1 +1 $이고 $b = 2\cdot k_2+1$인 정수 $k_1,k_2 \in \mathbb{Z}$가 존재하므로

$a\cdot b = (2\cdot k_1 + 1)\cdot (2\cdot k_2 + 1) = 4\cdot k_1\cdot k_2 +2\cdot k_2 + 2\cdot k_1 + 1 = 2\cdot (2\cdot k_1\cdot k_2 + k_2 + k_1) + 1$이 되어

$a \cdot b$는 홀수이다.

7.

$a^2 = a\cdot a$가 짝수일때 $a$가 홀수라고 가정하면 6번으로 $a^2$는 홀수가 되어 모순이다.

따라서 $a$는 짝수이다.

8. 

$a^2 = a\cdot a$가 홀수일때 $a$가 짝수라고 가정하면 4번으로 $a^2$는 짝수가 되어 모순이다.

따라서 $a$는 홀수이다.

 

 

 

정리6(선형합동식의 해)

임의의 정수 $a,b \in \mathbb{Z}$와 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 $\gcd(a,n)$ $= d$일때

$a\cdot x \equiv b \pmod{ n}$가 성립하는 $x \in \mathbb{Z}$가 존재하기 위한 필요충분조건은 $b / d \in \mathbb{Z}$인 것이다.

이때 $a\cdot x_0 \equiv b \pmod{ n}$인 임의의 $x_0 \in \mathbb{Z}$에 대해

$a\cdot x \equiv b \pmod{n}$인 모든 $x \in \mathbb{Z}$는 $x \equiv \left ( x_0 + i \cdot \dfrac{ n}{d} \right) \pmod{n}$이 되는 $ i = 0, 1 ,2,\cdots, d -1$가 존재하고

$i\ne j$인 모든 $i, j = 0,1 ,2,\cdots, d -1$에 대해 $\left ( x_0 + i \cdot \dfrac{n}{d} \right ) \not \equiv \left ( x_0 + j \cdot \dfrac{ n}{d} \right) \pmod{n}$이다.

증명

$a\cdot x \equiv b \pmod{ n}$이면

$a\cdot x - b = n\cdot y$인 정수 $y \in \mathbb{Z}$가 존재하므로 $a\cdot x - n\cdot y = b$이고

최대공약수의 정의로 $a /d \in \mathbb{Z}$이고 $n / d \in \mathbb{Z}$이므로 $a = d \cdot q_1$이고 $n = d \cdot q_2$인 정수 $q_1,q_2 \in \mathbb{Z}$가 존재하여

$b= a\cdot x - n\cdot y = d\cdot q_1 \cdot x - d\cdot q_2 y = d\cdot (q_1 \cdot x - q_2 \cdot y)$이므로 $b/d \in \mathbb{Z}$이다.

역으로 $b / d \in \mathbb{Z}$이면

$b = d\cdot q $인 정수 $q \in \mathbb{Z}$가 존재하고 베주항등식으로 $d = \gcd(a,n) = a\cdot q_1 - n\cdot q_2  $인 정수 $q_1,q_2 \in \mathbb{Z}$가 존재하여

$b = d\cdot q = (a\cdot q_1 - n\cdot q_2)\cdot q = a\cdot q_1\cdot q - n\cdot q_2\cdot q$이고 $a\cdot (q_1\cdot q) - b = n\cdot (q_2\cdot q)$이므로

$a\cdot (q_1 \cdot q) \equiv b \pmod{n}$인 $x = q_1\cdot q \in \mathbb{Z}$가 존재한다.

 

$a\cdot x_0 \equiv b \pmod{ n}$이고 $a\cdot x \equiv b \pmod{ n}$인 임의의 $x_0,x \in \mathbb{Z}$에 대해

$a\cdot x_0 +n\cdot y_0 = b = a\cdot x + n\cdot y$인 $y_0,y \in \mathbb{Z}$가 존재하므로 $a\cdot (x -x_0) = n\cdot (y_0 - y)$이고

$\gcd(a,n)$ $= d$이므로 $a = d \cdot r$이고 $n = d \cdot s$인 정수 $r, s \in \mathbb{Z}$에 대해

$ d\cdot r \cdot (x - x_0)= a\cdot (x - x_0) = n\cdot (y_0 - y) = d\cdot s \cdot (y_0 - y)$가 되어

$  r\cdot (x - x_0) = s \cdot (y_0 - y)$이고 $s\cdot (y_0 - y) / r \in \mathbb{Z}$이다.

또 $\gcd(a,n) = \gcd(d\cdot r, d\cdot s) = d$이므로 최대공약수 정리로 $\gcd(r,s) = 1$이고

유클리드 정리로 $(y_0 - y) / r \in \mathbb{Z}$이 되어 $y_0 - y = t\cdot r$인 정수 $t \in \mathbb{Z}$가 존재하므로

$ r\cdot (x - x_0) = s \cdot (y_0 - y) = s\cdot t\cdot r$이고 $x - x_0 = s\cdot t$이다.

$r = \dfrac{a}{d}$이고 $s = \dfrac{n}{d}$이므로

$x = x_0 + s\cdot t = x_0 + \dfrac{n}{d}\cdot t$이고 $y = y_0 - r\cdot t = y_0 - \dfrac{a}{d}\cdot t$가 되어

$b = a\cdot x + n\cdot y = a\cdot \left ( x_0 +\dfrac{n}{d}\cdot t \right ) + n \cdot \left (y_0 - \dfrac{a}{d}\cdot t \right )$이므로

$a\cdot x \equiv b \pmod{ n}$인 모든 $x \in \mathbb{Z}$는 $x = \left ( x_0 +\dfrac{n}{d}\cdot t \right )$가 되는 $t \in \mathbb{Z}$가 존재한다.

따라서 나눗셈 정리로 $t = q\cdot d + i$이고 $0\le i \le d-1$인 $q,i \in \mathbb{Z}$가 존재하므로

$\begin{align*} x & \equiv x_0 +\frac{n}{d}\cdot t  \pmod{n} \\[0.5em] & \equiv x_0 +\frac{n}{d}\cdot (q\cdot d + i) \pmod{n} \\[0.5em] & \equiv x_0 +q\cdot n + \frac{n}{d}\cdot i \pmod{n} \\[0.5em] & \equiv x_0 + \frac{n}{d}\cdot i \pmod{n} \text{ 이다. }\end{align*}$

또 $i\ne j$인 임의의 $i, j = 0,1 ,2,\cdots, d -1$에 대해 $\left ( x_0 + i \cdot \dfrac{n}{d} \right )  \equiv \left ( x_0 + j \cdot \dfrac{ n}{d} \right) \pmod{n}$이라 가정하면

$n\cdot q = \left ( x_0 + i \cdot \dfrac{n}{d} \right )- \left ( x_0 + j \cdot \dfrac{ n}{d} \right)  = i\cdot \dfrac{n}{d} -j\cdot \dfrac{n}{d}$인 $q \in \mathbb{Z}$가 존재하여 $ i \cdot \dfrac{n}{d} \equiv  j \cdot \dfrac{ n}{d} \pmod{n}$이고

$n = d\cdot \dfrac{n}{d} + 0$이므로 유클리드 호제법으로 $\gcd(n, \frac{n}{d}) = \gcd(\frac{n}{d},0) = \dfrac{n}{d}$이 되어 $\dfrac{n}{\gcd(\frac{n}{d},n)} = n\cdot \dfrac{d}{n} = d$이고

위 정리로 $ i \equiv  j  \pmod{d}$이므로 모순이 되어 $\left ( x_0 + i \cdot \dfrac{n}{d} \right ) \not \equiv \left ( x_0 + j \cdot \dfrac{ n}{d} \right) \pmod{n}$이다.

 

 

 

정리7(중국인의 나머지 정리)

$r\ge 2$인 $r \in \mathbb{Z}^+$개의 임의의 양의 정수 $n_1,n_2,\cdots, n_r \in \mathbb{Z}^+$이

$i\ne j$인 모든 $i,j = 1,2,\cdots, r$에 대해 $\gcd(n_i,n_j)$ $= 1$이면

임의의 정수 $a_1,a_2,\cdots, a_r \in \mathbb{Z}$에 대해

$x \equiv a_1 \pmod{ n_1}$

$x \equiv a_2 \pmod{ n_2}$

           $\vdots$

$x \equiv a_r \pmod{ n_r}$을 동시에 만족하는 $x \in \mathbb{Z}$가 존재하고

위 식을 만족하는 모든 $x,x_0 \in \mathbb{Z}$은 $x \equiv x_0 \pmod{n_1\cdot n_2\cdot \; \cdots \; \cdot n_r}$이다.

증명

$k = 1,2,\cdots, r$에 대해 $N_k = \dfrac{n_1\cdot n_2\cdot \; \cdots \; \cdot n_r}{n_k} = n_1\cdot n_2 \cdot \; \cdots \; \cdot n_{k-1}\cdot n_{k+1} \cdot \; \cdots \; \cdot n_r $를 정의할때

$i\ne k$인 모든 $i = 1,2,\cdots, r$에 대해 $\gcd(n_i,n_k) = 1$이므로 서로소 정리로 $\gcd(N_k, n_k) = 1$이 되어

위 정리로 $N_k \cdot x_k \equiv 1 \pmod{n_k}$이 되는 $x_k \in \mathbb{Z}$가 존재한다.

$i\ne k$인 모든 $i = 1,2,\cdots, r$에 대해

$(N_i - 0) / n_k \in \mathbb{Z}$이므로 $N_i  \equiv 0 \pmod{n_k}$는 곱셈정리로 $a_i \cdot N_i \cdot x_i \equiv a_i\cdot 0 \cdot x_i \pmod{n_k}$가 되어

덧셈정리로 $a_1\cdot N_1\cdot x_1 + a_2 \cdot N_2 \cdot x_2 + \cdots + a_r\cdot N_r \cdot x_r \equiv a_k \cdot N_k \cdot x_k \pmod{n_k}$이고

$N_k \cdot x_k \equiv 1 \pmod{n_k}$이므로 $a_1\cdot N_1\cdot x_1 + a_2 \cdot N_2 \cdot x_2 + \cdots + a_r\cdot N_r \cdot x_r \equiv a_k\cdot 1 \pmod{n_k}$이다.

따라서 $x =a_1\cdot N_1\cdot x_1 + a_2 \cdot N_2 \cdot x_2 + \cdots + a_r\cdot N_r \cdot x_r$로 두면 

모든 $k = 1,2,\cdots, r$에 대해 $x \equiv a_k \pmod{ n_k}$가 성립한다.

 

모든 $k = 1,2,\cdots, r$에 대해 $x_0 \equiv a_k \pmod{ n_k}$인 $x_0 \in \mathbb{Z}$이 존재하면 $x \equiv x_0 \pmod{ n_k}$가 되어

$(x - x_0) / n_1 \in \mathbb{Z}$과 $(x - x_0) / n_2 \in \mathbb{Z}$가 성립하고

$\gcd(n_1,n_2) = 1$이므로 최대공약수 정리로 $(x - x_0) / (n_1\cdot n_2) \in \mathbb{Z}$이고

서로소 정리로 $\gcd(n_1\cdot n_2, n_3) = 1$이므로 $(x - x_0) / n_3 \in \mathbb{Z}$에 대해

최대공약수 정리로 $(x - x_0) / (n_1\cdot n_2\cdot n_3) \in \mathbb{Z}$이다.

반복하여 서로소 정리로 $\gcd(n_1\cdot n_2\cdot \; \cdots \; \cdot n_{r-1}, n_r) = 1$이므로 $(x - x_0) / (n_1\cdot n_2 \cdot \; \cdots \; \cdot n_{r-1}) \in \mathbb{Z}$에 대해

최대공약수 정리로 $(x - x_0) / (n_1\cdot n_2 \cdot \; \cdots \; \cdot n_{r-1}\cdot n_{r}) \in \mathbb{Z}$이 되어 $x \equiv x_0 \pmod{n_1\cdot n_2\cdot \; \cdots \; \cdot n_r}$이다.

 

 

 

정리8

임의의 정수 $a,b,c,d ,r ,s\in \mathbb{Z}$와 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 $\gcd(a\cdot d - b\cdot c, n)$ $= 1$일때

$a\cdot x + b\cdot y \equiv r \pmod{ n}$이고 $c\cdot x + d\cdot y \equiv s \pmod{ n}$인 $x,y \in \mathbb{Z}$가 존재하고

위 식을 만족하는 모든 $x_0,y_0 \in \mathbb{Z}$은 $ x \equiv x_0 \pmod{ n}$이고 $ y \equiv y_0 \pmod{ n}$이다.

증명

$\gcd(a\cdot d - b\cdot c, n) = 1$이므로 위 정리로 

$(a\cdot d - b\cdot c)\cdot x \equiv d\cdot r - b\cdot s \pmod{n}$인 $x \in \mathbb{Z}$가 존재하고

$(a\cdot d - b\cdot c)\cdot y \equiv a\cdot s - c\cdot r \pmod{n}$인 $y \in \mathbb{Z}$가 존재한다.

또 위 정리로 $t \cdot (a\cdot d - b\cdot c) \equiv 1 \pmod{n}$인 $t \in \mathbb{Z}$이 존재하여 곱셈정리로

$t \cdot (a\cdot d - b\cdot c)\cdot x \equiv t \cdot (d\cdot r - b\cdot s) \pmod{n}$이고 $t \cdot (a\cdot d - b\cdot c)\cdot y \equiv t \cdot ( a\cdot s - c\cdot r) \pmod{n}$이므로

$x \equiv t \cdot (d\cdot r - b\cdot s) \pmod{n}$이고 $ y \equiv t \cdot ( a\cdot s - c\cdot r) \pmod{n}$이다.

위 정리로 $t_0 \cdot (a\cdot d - b\cdot c) \equiv 1 \pmod{n}$인 모든 $t_0 \in \mathbb{Z}$은 $ t \equiv t_0 \pmod{ n}$이므로

$x_0 \equiv t_0 \cdot (d\cdot r - b\cdot s) \pmod{n}$이고 $ y_0 \equiv t_0 \cdot ( a\cdot s - c\cdot r) \pmod{n}$인 모든 $x_0,y_0 \in \mathbb{Z}$에 대해

$\begin{align*} x & \equiv t \cdot (d\cdot r - b\cdot s) \pmod{n} \\[0.5em] & \equiv t_0 \cdot (d\cdot r - b\cdot s) \pmod{n} \\[0.5em] &\equiv x_0 \pmod{n} \end{align*}$   이고        $\begin{align*} y & \equiv t \cdot ( a\cdot s - c\cdot r) \pmod{n} \\[0.5em] & \equiv t_0 \cdot (a\cdot s - c\cdot r) \pmod{n} \\[0.5em] & \equiv y_0 \pmod{n} \end{align*}$   이다.

 

$(a\cdot d - b\cdot c)\cdot x \equiv d\cdot r - b\cdot s \pmod{n}$와 $(a\cdot d - b\cdot c)\cdot y \equiv a\cdot s - c\cdot r \pmod{n}$에 대해

$a\cdot d \cdot x - b\cdot c\cdot x -  d\cdot r + b\cdot s = n\cdot q_1$이고 $a\cdot d \cdot y - b\cdot c\cdot y - a\cdot s + c\cdot r = n\cdot q_2$인

$q_1, q_2 \in \mathbb{Z}$가 존재하여

$ n\cdot q_1 = d\cdot a \cdot x - b\cdot c\cdot x  + (d\cdot b\cdot y  - b\cdot d \cdot y ) -  d\cdot r + b\cdot s  = d\cdot (a\cdot x + b\cdot y - r) - b\cdot (c\cdot x + d\cdot y - s) \text{ 이고}$

$n\cdot q_2 = (a\cdot c \cdot x - c\cdot a \cdot x) + a\cdot d \cdot y - b\cdot c\cdot y  - a\cdot s + c\cdot r = a\cdot (c\cdot x + d\cdot y - s) - c\cdot (a\cdot x + b\cdot y - r) \text{ 이므로}$

$ n\cdot q_1\cdot a = a \cdot  d\cdot (a\cdot x + b\cdot y - r) - a\cdot b\cdot (c\cdot x + d\cdot y - s) $와

$n\cdot q_2 \cdot b =  a\cdot b\cdot  (c\cdot x + d\cdot y - s) - c\cdot b\cdot (a\cdot x + b\cdot y - r) $를 더하면

$n \cdot (q_1\cdot a + q_2\cdot b) = (a \cdot  d - c\cdot b) \cdot (a\cdot x + b\cdot y - r) $이고

$(a \cdot  d - c\cdot b) \cdot (a\cdot x + b\cdot y - r) \equiv 0 \pmod{n} $이 되어

$\dfrac{n}{\gcd(a\cdot d - b\cdot c, n)} = n$에 대해 위 정리로 $a\cdot x + b\cdot y - r \equiv 0 \pmod{n} $이고 $a\cdot x + b\cdot y  \equiv r \pmod{n} $이다.

또 $ n\cdot q_1\cdot c = c \cdot  d\cdot (a\cdot x + b\cdot y - r) - c \cdot b\cdot (c\cdot x + d\cdot y - s) $와

$n\cdot q_2 \cdot d =  a\cdot d \cdot  (c\cdot x + d\cdot y - s) - c\cdot d \cdot (a\cdot x + b\cdot y - r) $를 더하면

$n \cdot (q_1\cdot c + q_2\cdot d) = (a \cdot  d - c\cdot b) \cdot (c\cdot x + d\cdot y - s) $이고

$ (a \cdot  d - c\cdot b) \cdot (c\cdot x + d\cdot y - s) \equiv 0 \pmod{n} $이 되어

$\dfrac{n}{\gcd(a\cdot d - b\cdot c, n)} = n$에 대해 위 정리로 $c\cdot x + d\cdot y - s \equiv 0 \pmod{n} $이고 $c\cdot x + d\cdot y  \equiv s \pmod{n} $이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/50#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/50#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

David M. Burton - Elementary Number Theory - 9780073383149