[정수론] 합동 (Congruence)

합동 (Congruence)

합동 관계 (congruence relation)

$m$에 대하여 $m \mid (a - b)$인 경우 $a \equiv b \pmod{m}$으로 표기하고, "법(modulo) $m$에 관한 합동관계"라고 한다. 영어로는 congruence relation modulo $m$ 이다.

※ LaTeX으로 합동을 표기할 때는 \equiv 를 사용하고, modulo는 \mod{m} 또는 \pmod{m} 를 사용한다. 

 

다음 세 문장은 동치이다.

• $a \equiv b \pmod{m}$
• $a = b + mt$인 정수 $t$가 존재한다.
• $a = mq_1 + r$이고 $b = mq_2 + r$를 만족하는 정수 $q_1, q_2, r$가 존재한다.

그리고 다음이 성립한다.

• $a \equiv a \pmod{m}$
• $a \equiv b \pmod{m} \Rightarrow b \equiv a \pmod{m}$
• $a \equiv b \pmod{m}, \ b \equiv c \pmod{m} \Rightarrow a \equiv c \pmod{m}$

 

$k$개의 정수쌍이 합동이면 합/곱 역시 합동관계이다. 즉,

$\forall k \in Z$에 대하여 $a_i \equiv b_i \pmod{m}$이면

• $\sum_{i} a_i \equiv \sum_{i} b_i \pmod{m}$
• $\prod_{i} a_i \equiv \prod_{i} b_i \pmod{m}$

특히 $a \equiv b \pmod{m}$인 경우,

• $na \equiv nb \pmod{m}$, $a + c \equiv b + c \pmod{m}$
• $a^n \equiv b^n \pmod{m}$, $ac \equiv bc \pmod{m}$

서로 합동이라면, 덧셈, 곱셈, 거듭제곱에서도 합동관계가 보존된다.

Example

$3^{20}$을 $43$으로 나눈 나머지를 구해보자.

$3^4 = 81 \equiv -5 \pmod{43}$이므로 $3^{20} = (3^4)^5 \equiv (-5)^5 = (-25)(125) \pmod{43}$

한편 $125 \equiv -4 \pmod{43}$이므로

$(-25)(125) \equiv (-25)(-4) = 100 \equiv 14 \pmod{43}$

따라서 $3^{20} \equiv 14 \pmod{43}$ 이다.

 

다항식에서의 합동

정수 계수를 갖는 다항식이 다음과 같다고 하자.

\[ f(x) = c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n \]

\[ g(x) = d_0 + d_1 x + d_2 x^2 + \cdots + d_n x^n \]

그리고 양의 정수 $m$에 대하여 $a \equiv b \pmod{m}$라 하자. 그러면 다음이 성립한다.

• $f(a) \equiv f(b) \pmod{m}$
• $c_k \equiv d_k \pmod{m} (0 \le k \le n)$이면 $f(a) \equiv g(b) \pmod{m}$

 

3의 배수와 9의 배수 판정

초등학교때 "모든 자릿수의 수를 더한 수가 3의 배수이면, 원래 수도 3의 배수이다"

또는 "모든 자릿수의 수를 더한 수가 9의 배수이면, 원래 수도 9의 배수이다"를 배웠다.

위에서 설명한 다항식에서의 합동을 이용하여 증명할 수 있다.

우리가 사용하는 수 체계가 10진법임을 이용한다.

 

높은자리부터 표기하므로 $f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots a_1 x + a_0$라 하자.

모든 자릿수의 합은 $c = f(1)$이고, 10진법으로 표기한 수를 $b$라 하면 $b = f(10)$이다.

한편, $10 \equiv 1 \pmod{3}$이므로 $b = f(10) \equiv f(1) = c \pmod{3}$ 이다.

따라서 만약 $3 \mid b$ 라면 $3 \mid b \iff b \equiv 0 \pmod{3} \iff c \equiv 0 \pmod{3} \iff 3 \mid c$ 이다.

 

9의 배수도 동일하게 증명할 수 있다.

 

11의 배수도 비슷하게 증명할 수 있다.

낮은 자리수부터 차례대로 더하고 뺀 수를 $d = a_0 - a_1 + a_2 - a_3 + \cdots + (-1)^{n} a_n$이라 하자.

$10 \equiv -1 \pmod{11}$이므로 $b = f(10) \equiv f(-1) = d \pmod{11}$ 임을 이용하여 증명이 가능하다.

 

$N = 583461$의 경우, 각 자릿수의 합이 $27$이고 $3 \mid 27$, $9 \mid 27$이므로 $N$은 3의 배수이면서 9의 배수이다.

 

합동에서의 나눗셈 (Division in Congruence)

$a \equiv b \pmod{m}$이면 $ca \equiv cb \pmod{m}$임을 위에서 설명했다.

그렇다면 그 역도 성립하는가? $ca \equiv cb \pmod{m} \Rightarrow a \equiv b \pmod{m}$ ??

NO! 그렇지 않다.

$2 \cdot 4 \equiv 2 \cdot 1 \pmod{6}$이지만 $4 \not\equiv 1 \pmod{6}$이다.

다음이 성립한다.

\[ ca \equiv cb \pmod{m} \Rightarrow a \equiv b \pmod{\frac{m}{d}}, \ d = \gcd(c, n) \]

 

따라서, collorary로 $m$이 소수인 경우에는 $\gcd(p, c)=1$이므로 다음이 성립한다.

\[ ca \equiv cb \pmod{p} \text{, and } p \nmid c \text{ where } p \text{ is prime} \Rightarrow a \equiv b \pmod{p} \]

 

그리고 항등식과 다른 성질을 갖는다. 특히,

$ab \equiv 0 \pmod{m}$이라고해서 $a \equiv 0 \pmod{m}$이거나 $b \equiv 0 \pmod{m}$은 아니다.

반례) $a = 4,\ b=3,\ m=12$