합동식

양의 정수 $m$ 과 두 정수 $a, b$ 사이에 $m ∣ (a - b)$ 인 관계가 있을 때, “ $a$ 와 $b$ 는 법 $m$ 에 관하여 합동이다”라고 하고, 이것을

a \equiv b (mod m)

으로 나타낸다. 이 식을 합동식이라 한다. $a$ 와 $b$ 가 법 $m$ 에 관하여 합동이 아닌 경우에는

a \neq \equiv b (mod m)

으로 나타낸다.

예를들어 $a$ 가 $b$ 의 배수이면, $b ∣ a$ , 즉 $b ∣ (a - 0)$ 이므로

a \equiv 0 (mod b)

라고 할 수 있다.

합동식의 성질

임의의 정수 $a$ 에 대하여

$a \equiv a (mod m)$ ¹
$a \equiv b (mod m) \Rightarrow b \equiv a (mod m)$ ²
$a \equiv b (mod m), b \equiv c (mod m) \Rightarrow a \equiv c (mod m)$ ³

임의의 정수 $c$ 에 대하여 $a \equiv b (mod m), c \equiv d (mod m)$ 일 때

$a \pm c \equiv b \pm d (mod m)$ (복호동순) ⁴
$a + c \equiv b + c (mod m)$ ⁵
$a c \equiv b d (mod m)$ ⁶
임의의 양의 정수 $n$ 에 대하여 $a^{n} \equiv b^{n} (mod m)$ ⁷

완전 잉여계(Total Residue System)

자연수 $m$ 에 대해, 정수 $a_{1}, a_{2}, \dots, a_{m}$ 가 다음 조건을 만족할 때 이 수들을 법 $m$ 에 대한 완전 잉여계라고 한다.

각각의 $a_{i}$ 는 서로 다른 $m$ 개의 수이다.
각각의 $a_{i}$ 는 어떤 정수 $b$ 와 합동이다. 즉, 모든 정수는 $a_{i}$ 중 하나와 $(mod m)$ 에서 합동이다.

{a_{1}, a_{2}, \dots, a_{m}}

은 정수 전체를 $m$ 으로 나누었을 때 나올 수 있는 모든 나머지를 정확히 하나씩 포함한다.

예를 들어

${0, 1, 2, 3, 4}$ 는 법 $5$ 에 대한 완전 잉여계다.
${- 2, - 1, 0, 1, 2}$ 도 법 $5$ 에 대한 완전 잉여계다.

${0, 1, 2, 3, 4}$ 와 ${- 2, - 1, 0, 1, 2}$ 가 법 5에 대한 두 완전잉여계라 하면, 다음과 같이 일대일 대응이 이루어진다.

- 2 - 1 012 \equiv 3 (mod 5), \equiv 4 (mod 5), \equiv 0 (mod 5), \equiv 1 (mod 5), \equiv 2 (mod 5)

완전 잉여계는 여러 가지로 구성할 수 있다. 어떤 수를 기준으로 대칭을 만들거나, 음수를 포함하는 것도 가능하다. 단, 완전 잉여계의 원소는 법 $m$ 에 대해 중복 없이 하나씩만 나와야 한다.

기약 잉여계(Reduced Residue System)

자연수 $m$ 에 대해, 정수 $b_{1}, b_{2}, \dots, b_{r}$ 가 다음 조건을 만족할 때 이 수들을 법 $m$ 에 대한 기약 잉여계라고 한다.

$1 \leq b_{i} < m$ 또는 $0 \leq b_{i} < m$ 사이의 수들 중에서
각각의 $b_{i}$ 는 $m$ 과 서로소이다. 즉, $g cd (b_{i}, m) = 1$
서로 다른 $ϕ (m)$ 개의 수로 이루어진다. ( $ϕ (m)$ 은 오일러 함수, 즉 $m$ 보다 작고 서로소인 수의 개수)

{b_{1}, b_{2}, \dots, b_{ϕ (m)}}

는 법 $m$ 에 대한 기약 잉여계다.

예를 들어

$m = 10$ 일 때, $ϕ (10) = 4$ 이고, ${1, 3, 7, 9}$ 는 $g cd (b_{i}, 10) = 1$ 이므로 기약 잉여계입니다.
$m = 7$ 일 때, $ϕ (7) = 6$ , ${1, 2, 3, 4, 5, 6}$ 는 모두 7과 서로소이므로 기약 잉여계입니다.

기약 잉여계의 각 원소는 $m$ 보다 작은 자연수이며, $m$ 과 서로소인 수들로만 이루어져야 한다. 기약 잉여계는 $ϕ (m)$ 개의 원소를 가져야 하며, 이 조건을 만족하는 수라면 다양한 조합이 가능하다. 기약 잉여계는 (법 $m$ 에 대한)곱셈에 대해 군 구조를 가진다.

소약법칙

정수에서 $ab = a c$ 이고 $a \neq = 0$ 이면 $b = c$ 가 성립한다. 이러한 것을 소약법칙이라 하는데, 합동식에서도 소약법칙이 성립할까?

예를 들어

2 \cdot 3 \equiv 2 \cdot 5 (mod 4)

가 성립한다. 그러나

3 \neq \equiv 5 (mod 4)

이므로 소약법칙이 성립하지 않는다.

하지만 다음과 같은 경우에는 소약법칙이 성립한다.

ab \equiv a c (mod m)

이고, $a$ 가 $m$ 과 서로소( $g cd (a, m) = 1$ ) 이면

b \equiv c (mod m)

이다.

증명

\Rightarrow \Rightarrow ab \equiv a c (mod m) m ∣ (ab - a c) m ∣ a (b - c)

$g cd (a, m) = 1$ 이므로 $m ∣ (b - c)$ 이어야 한다. 따라서

b \equiv c (mod m)

예제

$17$ 을 $5$ 로 나눈 나머지를 구하여라. ⁸
$36$ 을 $6$ 으로 나눈 나머지를 구하여라. ⁹
$2^{10}$ 을 $11$ 로 나눈 나머지를 구하여라.¹⁰
$1 1^{n} \equiv 1 (mod 5)$ 임을 보여라. ¹¹
$2^{20} - 1$ 이 $41$ 로 나누어 떨어짐을 보여라. ¹²
$2^{10} \cdot 1 4^{40} - 1$ 은 $11$ 의 배수임을 보여라. ¹³
$3^{2002}$ 를 $7$ 로 나눈 나머지를 구하여라. ¹⁴
$x^{2} + y^{2} = 1003$ 을 만족하는 정수 $x, y$ 는 없음을 증명하여라. ¹⁵

(반사성) $a - a = 0 \Rightarrow m ∣ 0$ ↩
(대칭성) $a - b \equiv 0 (mod m) \Rightarrow b - a = - (a - b) \equiv 0 (mod m)$ ↩
(추이성) $a - b \equiv 0, b - c \equiv 0 \Rightarrow a - c = (a - b) + (b - c) \equiv 0 (mod m)$ ↩
(복호동순) $a - b \equiv 0, c - d \equiv 0 \Rightarrow (a \pm c) - (b \pm d) = (a - b) \pm (c - d) \equiv 0 (mod m)$ ↩
(덧셈보존) $a - b \equiv 0 \Rightarrow (a + c) - (b + c) = a - b \equiv 0$ ↩
(곱셈보존) $a c = (b + km) (d + l m) = b d + m (k d + k l m + b l) \Rightarrow a c \equiv b d (mod m)$ ↩
(거듭제곱보존) $a - b = km$ 이면, 귀납법으로 $a^{n} - b^{n} = (a - b) q$ 꼴이 되어 $m ∣ (a^{n} - b^{n})$ ↩
$17 = 5 \cdot 3 + 2$ 이므로, $17 \equiv 2 (mod 5)$ 이다. ↩
$36 = 6 \cdot 6 + 0$ 이므로, $36 \equiv 0 (mod 6)$ 이다. ↩
$2^{10} = 1024 = 11 \cdot 93 + 1$ 이므로, $2^{10} \equiv 1 (mod 11)$ 이다. ↩
$11 \equiv 1 (mod 5)$ 이므로, $1 1^{n} \equiv 1^{n} \equiv 1 (mod 5)$ 이다. ↩
$2^{5} \equiv - 9 (mod 41)$ 이므로 $2^{20} \equiv 81 \equiv - 1 (mod 41)$ 이다. 따라서 $2^{20} - 1 \equiv 0 (mod 41)$ 이다. ↩
$2^{5} \equiv - 1 (mod 11)$ 이므로 $2^{10} \equiv 1 (mod 11)$ 이다. 또한 $14 \equiv 3 (mod 11)$ 이므로 $1 4^{40} \equiv 3^{40} \equiv 1 (mod 11)$ 이다. 따라서 $2^{10} \cdot 1 4^{40} \equiv 1 \cdot 1 \equiv 1 (mod 11)$ 이다. 따라서 $2^{10} \cdot 1 4^{40} - 1 \equiv 0 (mod 11)$ 이다. ↩
$3^{3} \equiv - 1 (mod 7)$ 이므로 $3^{2001} \equiv (- 1)^{667} \equiv - 1 (mod 7)$ 이다. 따라서 $3^{2002} \equiv - 3 \equiv 4 (mod 7)$ 이다. ↩
$x^{2} + y^{2} = 1003$ 을 만족하는 정수 $x, y$ 가 존재하면, $x^{2} + y^{2} \equiv 1003 (mod 4)$ 이어야 한다. $x^{2}, y^{2}$ 는 각각 $0$ 또는 $1$ 로 나누어 떨어져야 하므로, $x^{2} + y^{2}$ 는 $0, 1, 2$ 중 하나가 되어야 한다. 그러나 $1003 \equiv 3 (mod 4)$ 이므로, $x^{2} + y^{2} = 1003$ 을 만족하는 정수 $x, y$ 는 존재하지 않는다. ↩

Ray

Explorer

합동식

합동식의 성질

완전 잉여계(Total Residue System)

기약 잉여계(Reduced Residue System)

소약법칙

증명

예제

Graph View

Table of Contents

Backlinks

Ray

Explorer

합동식

합동식의 성질

완전 잉여계(Total Residue System)

기약 잉여계(Reduced Residue System)

소약법칙

증명

예제

Footnotes

Graph View

Table of Contents

Backlinks