# 38주차 · 강의 — 예제 · 연습 · 해설

## 예제 — 방들의 세계에서 계산하고 증명하기

예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 한 뒤 완성본을 보며, 예제 2.3은 설계부터 혼자 한다.

### 예제 2.1 — 덧셈의 잘 정의됨

**명제.** $\mathbb{Z}_n$에서 $[a] = [a']$이고 $[b] = [b']$이면 $[a+b] = [a'+b']$이다. (따라서 $[a] + [b] = [a+b]$는 잘 정의된다.)

**설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 수 차원의 언어로 먼저 번역한다.

|  | **말** | **수식 번역** |
|---|---|---|
| 가정 (출발점) | $[a] = [a']$, $[b] = [b']$ | $\underline{\quad(1)\quad}$ |
| 목표 (도착점) | $[a+b] = [a'+b']$ | $\underline{\quad(2)\quad}$를 만든다 |

:::{container} quotebox
**확인 7.** 번역표의 빈칸 (1)(2)를 채워 보자. 방의 상등과 수의 합동을 잇는

정리는 무엇인가?
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $a \equiv a' \pmod n$이고 $b \equiv b' \pmod n$  (2) $a + b \equiv a' + b' \pmod n$

두 칸 모두 37주차 핵심 정리의 번역이다. 내려갈 때는 $\Leftarrow$ 방향을,

되돌아올 때는 $\Rightarrow$ 방향을 쓴다 — 준비 운동 유형 1이 놓친 두 방향이다.
:::

**1단계 — 가정을 무대에 올린다.** 명제가 "~이면 ~이다" 꼴이므로 앞부분을 참이라 선언하고 시작한다.

:::{container} quotebox
**확인 8.** 첫 문장을 완성해 보자: "$\underline{\qquad}$이고 $\underline{\qquad}$이라 가정하자."
:::

:::{admonition} 답
:class: quotebox dropdown

"$[a] = [a']$이고 $[b] = [b']$이라 가정하자." 이 문장이 놓는 상황은 "같은 방에

이름이 두 벌 붙어 있다"이고, 결과가 갈리는지 확인할 무대를 만드는 것이 첫 줄의

임무다.
:::

**2단계 — 집합 차원에서 수 차원으로 내려간다.** 손에 있는 것은 집합의 상등인데 인용하려는 (C4)는 수의 합동에 대한 정리다. 번역이 필요하다.

:::{container} quotebox
**확인 9.** 둘째 문장을 완성해 보자: "$\underline{\qquad}$에 의해 $a \equiv \underline{\quad}$이고 $b \equiv \underline{\quad} \pmod n$이다."
:::

:::{admonition} 답
:class: quotebox dropdown

"핵심 정리(37주차)에 의해 $a \equiv a'$이고 $b \equiv b' \pmod n$이다."

$\equiv \pmod n$이 동치관계라는 것은 20주차의 (C1)~(C3)에서 확인했으므로 핵심

정리를 적용할 자격이 있다 — 준비 운동 유형 3이 빠뜨린 전제가 여기서 소비된다.
:::

**3단계 — 수 차원에서 이미 증명된 정리를 인용한다.**

:::{container} quotebox
**확인 10.** 셋째 문장을 완성해 보자: "$\underline{\qquad}$에 의해 $a + b \equiv \underline{\qquad} \pmod n$이다." 인용할 정리의 이름과 출처는?
:::

:::{admonition} 답
:class: quotebox dropdown

"(C4) 합 보존(20주차)에 의해 $a + b \equiv a' + b' \pmod n$이다." (C4)는 20주차

예제 2.2에서 증명이 끝났으므로 근거 ④로 이름만 대면 된다. 결과가 갈리지 않는

이유가 전부 이 한 줄에 있다 — 규칙 B에는 이런 보존 정리가 없어서 갈렸다.
:::

**4단계 — 결론을 집합 차원으로 되돌린다.** 증명할 문장은 방에 대한 등식이므로 마지막에 다시 올라와야 한다.

:::{container} quotebox
**확인 11.** 마지막 문장을 완성해 보자: "다시 $\underline{\qquad}$에 의해 $\underline{\qquad}$이다. $\blacksquare$"
:::

:::{admonition} 답
:class: quotebox dropdown

"다시 핵심 정리에 의해 $[a+b] = [a'+b']$이다. $\blacksquare$" 이번에는

$\Rightarrow$ 방향을 쓴다. 이 네 문장이 완성된 증명이다.
:::

**완성본.** 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜"에 스스로 답해 본다.

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $[a] = [a']$이고 $[b] = [b']$이라 가정하자. | 같은 방에 붙은 이름 두 벌을 놓는다 — 결과가 갈리는지 확인할 상황을 만드는 줄. |
| 핵심 정리(37주차)에 의해 $a \equiv a' \pmod n$이고 $b \equiv b' \pmod n$이다. | 방의 상등을 원소의 합동으로 번역(근거 ④). 집합 차원에서 수 차원으로 내려간다. |
| (C4)에 의해 $a + b \equiv a' + b' \pmod n$이다. | 20주차에서 증명해 둔 합 보존 정리를 부품으로 쓴다(근거 ④). 결과가 갈리지 않는 이유가 전부 이 줄에 있다. |
| 다시 핵심 정리에 의해 $[a+b] = [a'+b']$이다. $\blacksquare$ | 수 차원에서 집합 차원으로 역번역. 어느 대표원으로 계산해도 같은 방이 나온다는 결론. |

**대입 시뮬레이션.** 완성본의 문자에 $n = 6$, $a = 2$, $a' = 8$, $b = 3$, $b' = 9$를 넣어 읽어 보자.

:::{container} quotebox
**확인 12.** 이 값들을 넣으면 셋째 줄과 넷째 줄은 각각 어떤 식이 되는가. 그리고

§1.4에서 손으로 확인한 계산과 어떤 관계인가?
:::

:::{admonition} 답
:class: quotebox dropdown

셋째 줄은 $5 \equiv 17 \pmod 6$ ($17 - 5 = 12$), 넷째 줄은 $[5] = [17]$이 된다

(첫째 줄은 $[2] = [8]$, $[3] = [9]$, 둘째 줄은 $2 \equiv 8$, $3 \equiv 9$).

§1.4의 손 계산은 이 네 줄의 특수한 경우다 — 같은 네 줄이 모든 $n$과 모든 이름

벌에 그대로 작동한다.
:::

(곱셈은 셋째$\cdot$넷째 줄만 곱으로 바꾼 같은 네 줄이다 — 문제 7이 그 자리다.)

### 예제 2.2 — $\mathbb{Z}_4$의 연산표

덧셈표와 곱셈표를 만드시오. (표기 단순화: $[k]$를 $k$로 적되, 원소가 동치류라는 것은 잊지 않는다.)

이번에는 설계만 함께 하고 표는 완성본으로 본다.

:::{container} quotebox
**확인 13.** 덧셈표의 $2$행 $3$열에 무엇을 적는가. 그 절차가 정당하다는 근거는

무엇인가?
:::

:::{admonition} 답
:class: quotebox dropdown

$[2] + [3] = [5] = [1]$이므로 $1$을 적는다. 절차는 "대표원을 정수로 더한 뒤

$\bmod 4$로 줄인다"이고, 이것이 규칙이 될 수 있는 근거는 예제 2.1의 잘

정의됨이다 — 대표원을 $6, 7$로 잡아도 $[13] = [1]$로 같은 칸이 나온다.
:::

**풀이.** 덧셈표:

| **$+$** | **0** | **1** | **2** | **3** |
|---|---|---|---|---|
| **0** | 0 | 1 | 2 | 3 |
| **1** | 1 | 2 | 3 | 0 |
| **2** | 2 | 3 | 0 | 1 |
| **3** | 3 | 0 | 1 | 2 |

곱셈표:

| **$\times$** | **0** | **1** | **2** | **3** |
|---|---|---|---|---|
| **0** | 0 | 0 | 0 | 0 |
| **1** | 0 | 1 | 2 | 3 |
| **2** | 0 | 2 | **0** | 2 |
| **3** | 0 | 3 | 2 | 1 |

**관찰.** ① 덧셈표의 각 행은 $0, 1, 2, 3$을 한 번씩 순회한다. ② 곱셈표의 굵은 $0$: $[2][2] = [4] = [0]$이다. $[2] \neq [0]$인데 곱이 $[0]$이 되었다 — 정수와 실수에서는 일어나지 않던 일이다(25주차 문제 13의 영인수 성질). ③ $[3][3] = [9] = [1]$이므로 $[3]$은 자기 자신을 곱해 $[1]$을 만든다.

### 예제 2.3 — $\mathbb{Z}_6$에서 $[2][x] = [4]$ 풀기

$\mathbb{Z}_6$에서 $[2] \cdot [x] = [4]$를 만족하는 $[x]$를 **모두** 구하시오.

이번에는 설계부터 혼자 한다. 전략을 먼저 정한 뒤 확인 상자를 연다.

:::{container} quotebox
**확인 14.** 실수에서 하듯 양변을 $2$로 나눠도 되는가. 안 된다면 어떤 방법이

남는가?
:::

:::{admonition} 답
:class: quotebox dropdown

나눌 수 없다. §1.5에서 확인한 대로 나눗셈은 정의되어 있지 않고, "양변에 역원

곱하기"로 바꿔 적으려 해도 $[2]$의 곱셈 역원이 없다(문제 8(b)). 남는 방법은

전수 확인이다 — $|\mathbb{Z}_6| = 6$이므로 후보가 여섯 개뿐이고, 무대가

유한하면 빠짐없는 확인이 완결된 논증이 된다(유한성은 정의 38.1이 준 도구다).
:::

**풀이.** 여섯 동치류를 전부 대입한다.

$$
[2][0] = [0], \quad [2][1] = [2], \quad [2][2] = [4], \quad [2][3] = [6] = [0], \quad [2][4] = [8] = [2], \quad [2][5] = [10] = [4]
$$

$[4]$가 나온 자리는 $[x] = [2]$와 $[x] = [5]$ 두 곳이다. 후보 여섯 개를 빠짐없이 확인했으므로 다른 해는 없다. 따라서 해는 두 개다.

실수 감각으로 양변을 $2$로 나눠 $[x] = [2]$라고만 답하면 해 하나를 잃는다. $\mathbb{Z}_6$에서 $[2]$는 곱셈 역원을 갖지 않는다 — 어떤 정수 $y$에 대해서도 $2y$는 짝수이고 짝수를 $6$으로 나눈 나머지도 짝수이므로 $[2y] = [1]$이 될 수 없기 때문이다. 일차방정식의 해가 유일하다는 것(26주차 문제 13)은 실수 세계의 성질이었지 모든 세계의 법칙이 아니다.

### 관찰 — 같은 뼈대

예제 2.1과 문제 7은 소재가 다르지만 걸음이 같다. 대응표의 빈칸을 채워 보자.

| **단계** | **예제 2.1 (덧셈)** | **곱셈 (문제 7)** |
|---|---|---|
| ① 이름 두 벌 가정 | $[a] = [a']$, $[b] = [b']$ | $\underline{\quad(1)\quad}$ |
| ② 수 차원으로 번역 | $a \equiv a'$, $b \equiv b' \pmod n$ | $\underline{\quad(2)\quad}$ |
| ③ 보존 정리 인용 | (C4): $a + b \equiv a' + b'$ | $\underline{\quad(3)\quad}$ |
| ④ 집합 차원으로 역번역 | $[a+b] = [a'+b']$ | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 15.** 빈칸을 채우고, 두 열이 다른 곳이 몇 군데인지 세어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $[a] = [a']$, $[b] = [b']$  (2) $a \equiv a'$, $b \equiv b' \pmod n$

(3) (C5): $ab \equiv a'b' \pmod n$  (4) $[ab] = [a'b']$

다른 곳은 ③과 ④ 두 군데다. ④는 ③의 결과를 그대로 역번역한 것이므로, 실제로

손볼 것은 ③에서 인용하는 정리의 이름 하나다.

이 세 걸음을 **번역–보존–역번역**이라 부르기로 한다. 잘 정의됨을 물을 때마다

이 뼈대를 쓰고, 새로 준비할 것은 가운데 걸음의 보존 정리 하나뿐이다.
:::

예제 2.2와 2.3도 뼈대가 같다. 둘 다 유한성을 도구로 쓴다 — 예제 2.2는 표 하나당 $16$칸씩 두 표를, 예제 2.3은 후보 $6$개를 빠짐없이 확인했고, 개수가 유한하다는 근거는 둘 다 정의 38.1($|\mathbb{Z}_4| = 4$, $|\mathbb{Z}_6| = 6$)이다. "모든 $[x]$에 대해"는 보통 문자로 처리하지만, 무대가 유한하면 전부를 확인하는 것으로도 닫힌다 — 빠뜨린 후보가 없기 때문이다.

:::{admonition} 이번 주에 확인한 것
:class: quotebox

잘 정의됨 증명은 번역–보존–역번역의 세 걸음이고, 바뀌는 것은 가운데 걸음에서

인용하는 보존 정리뿐이다. 계산에서는 $|\mathbb{Z}_n| = n$이라는 유한성이

전수 확인이라는 도구를 준다.
:::

## 빈칸 사다리 — 지지대를 하나씩 빼며

훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

### 훈련 1 ●○○ — 수식 빈칸

$\mathbb{Z}_5$에서 계산한다 (표기: $[k]$를 $k$로).

(1) $3 + 4 = [\underline{\quad}]$  (2) $3 \times 4 = [\underline{\quad}]$  (3) $4^2 = [\underline{\quad}]$

(4) $[3]$의 곱셈 역원(곱해서 $[1]$이 되는 동치류): $[\underline{\quad}]$ — 확인: $3 \times \underline{\quad} = \underline{\quad} \equiv 1 \pmod 5$

(5) $\mathbb{Z}_5$의 곱셈표에서 $[0]$이 아닌 두 동치류의 곱이 $[0]$이 되는 칸이 있는가: $\underline{\quad}$

### 훈련 2 ●●○ — 수식과 근거를 함께

이번에는 구조 낱말과 근거 이름도 빈칸이다.

**명제.** $\mathbb{Z}_n$에서 $[a] = [a']$이면 $[a^2] = [a'^2]$이다.

**증명.** $[a] = [a']$이라 $\underline{\quad(1)\quad}$하자. $\underline{\quad(2)\quad}$에 의해 $a \equiv a' \pmod n$이다. 이 합동을 자기 자신과 짝지어 $\underline{\quad(3)\quad}$에 적용하면

$$
a \cdot a \equiv \underline{\quad(4)\quad} \pmod n
$$

이고, 곧 $a^2 \equiv a'^2 \pmod n$이다. 다시 $\underline{\quad(5)\quad}$에 의해 $\underline{\quad(6)\quad}$이다. $\blacksquare$

### 훈련 3 ●●● — 뼈대만 남기고

이번에는 각 칸을 통째로 채운다.

**명제.** $\mathbb{Z}_{12}$에는 $[0]$이 아닌 두 원소로 곱이 $[0]$이 되는 쌍이 존재한다.

**증명의 뼈대.**

- ① 증인 후보를 고르는 방침: $\underline{\quad(1)\quad}$
- ② 두 증인이 $[0]$이 아님을 확인: $\underline{\quad(2)\quad}$
- ③ 곱이 $[0]$임을 계산하고 결론 선언: $\underline{\quad(3)\quad}$

(목표가 "존재한다"이므로 증인 한 쌍을 제시하면 끝난다 — 26주차의 존재 서식이다. 이 훈련이 문제 16의 예행연습이다.)

## 연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다.

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. "$\mathbb{Z}_7$에서 $[5] + [4] = [2]$"만 적으면

절반이고, "정의 38.3에 의해 $[5]+[4] = [9]$이고, $9 \equiv 2 \pmod 7$이므로

핵심 정리에 의해 $[9] = [2]$이다"가 만점이다. 증명 문제에서는 핵심 정리와

(C4)(C5)를 인용한 지점을 이름으로 밝힌 답안만 완결이다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.
:::

### 기본 ●○○

**1.** [백지] $\mathbb{Z}_n$의 정의와 $|\mathbb{Z}_n| = n$의 근거(나눗셈 정리의 존재$\cdot$유일)를 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

근거는 두 조각이다 — "목록이 전부를 덮는다"(나눗셈 정리의 존재)와 "목록에

중복이 없다"(유일성, 또는 같은 뜻의 비합동 확인).
:::

**2.** $\mathbb{Z}_7$에서 계산하시오 (결과를 $[0] \sim [6]$으로): (a) $[5] + [4]$ (b) $[5][4]$ (c) $[6]^2$ (d) $[3]^3$

:::{admonition} 힌트
:class: quotebox dropdown

정의 38.3대로 대표원을 정수로 계산한 뒤 $\bmod 7$로 줄인다. 답안에는

"$5 + 4 = 9$, $9 \equiv 2 \pmod 7$"처럼 계산과 축소를 각각 적는다.
:::

**3.** $\mathbb{Z}_6$에서 $[4] = [22]$인 이유와 $[4] \neq [3]$인 이유를 각각 핵심 정리로 설명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

같음은 합동을 확인해 $\Rightarrow$ 방향으로, 다름은 비합동을 확인해 대우로 쓴다.
:::

**4.** 빈칸 훈련($\mathbb{Z}_5$)을 백지에서 완성하시오.

:::{admonition} 힌트
:class: quotebox dropdown

(4)의 역원은 다섯 후보를 차례로 곱해 찾고, (5)는 곱셈표를 그려 $0$이 나오는

칸을 세는 편이 빠르다.
:::

**5.** 예제 2.1(덧셈의 잘 정의됨)을 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

네 줄이다. 가정 선언 $\to$ 핵심 정리로 합동 번역 $\to$ (C4) 인용 $\to$ 핵심 정리로

역번역. 인용한 정리의 이름을 줄마다 적었는지 확인한다.
:::

**6.** $\mathbb{Z}_5$의 덧셈표와 곱셈표를 작성하시오.

:::{admonition} 힌트
:class: quotebox dropdown

$5 \times 5$ 표 두 개다. 덧셈표는 각 행이 $0 \sim 4$를 한 번씩 순회하고,

곱셈표는 $0$행을 뺀 각 행이 그러한지 확인하면 계산 실수를 잡을 수 있다.
:::

### 표준 ●●○

:::{admonition} 이 절에서 처음 쓰는 세 가지 말 — 역원$\cdot$영인수$\cdot$소거
:class: quotebox

$\mathbb{Z}_n$에서 $[a][y] = [1]$인 $[y]$가 존재하면 그 $[y]$를 $[a]$의

**곱셈 역원**, $[a] + [y] = [0]$인 $[y]$를 $[a]$의 **덧셈 역원**이라 한다.

$[a] \neq [0]$, $[b] \neq [0]$인데 $[a][b] = [0]$일 때 $[a], [b]$를 **영인수**라

하고, $[c][x] = [c][y]$에서 $[c]$를 지워 $[x] = [y]$를 얻는 변형을 **소거**라 한다.

덧셈 역원은 항상 존재한다(문제 14). 곱셈 역원은 있을 수도 없을 수도 있고

(예제 2.3의 $[2]$), 있을 때만 "양변에 역원을 곱한다"가 근거 ③으로 허용된다.

소거는 정수$\cdot$실수에서 늘 되던 변형이지만 $\mathbb{Z}_n$에서는 보장되지 않는다 —

27주차 문제 19에서 집합의 '지우기'가 무효였던 것과 같은 계열이고, 무효인

이유는 문제 11에서 반례로 확인한다.
:::

**7.** 곱셈 $[a][b] = [ab]$가 잘 정의됨을 증명하시오 (예제 2.1의 곱 버전 — (C5)).

**8.** $\mathbb{Z}_6$의 곱셈표를 작성하고, (a) 영인수 쌍을 모두 찾고 (b) 곱셈 역원을 갖는 방을 모두 찾으시오.

:::{admonition} 힌트
:class: quotebox dropdown

표를 채운 뒤 두 번 훑는다. (a)는 $0$행$\cdot$$0$열 밖에서 $0$ 찾기, (b)는 같은

범위에서 $1$ 찾기다. 찾은 뒤 그 대표원과 $6$의 공통 약수를 살펴본다.
:::

**9.** $\mathbb{Z}_7$에서 $[3][x] = [1]$의 해를 구하시오 — 즉 $[3]$의 역원. 그리고 그 역원을 이용해 $[3][x] = [5]$를 푸시오.

:::{admonition} 힌트
:class: quotebox dropdown

앞부분은 $3x \equiv 1 \pmod 7$인 $x$를 일곱 후보에서 찾는 일이고, 뒷부분은

"양변에 역원을 곱한다"(근거 ③)로 적는다.
:::

**10.** $\mathbb{Z}_8$에서 $[x]^2 = [1]$의 해를 **모두** 구하시오 (전수 대입). 이 결과가 17주차 문제 15(홀수의 제곱은 $8m+1$)와 어떻게 연결되는지 한 문장으로 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

여덟 후보의 제곱을 전부 적고, 해로 나온 대표원들이 공통으로 갖는 성질(홀수인가

짝수인가)을 본다.
:::

**11.** $\mathbb{Z}_6$에서 $[3][x] = [3][y]$인데 $[x] \neq [y]$인 사례를 제시하시오 — "소거 금지"의 반례 완전 서식으로.

:::{admonition} 힌트
:class: quotebox dropdown

문제 8의 $[3]$ 행에는 같은 값이 여러 번 나온다. 반례 서식은 세 조각이다:

제시 / 가정이 참임을 확인 / 결론이 거짓임을 확인.
:::

**12.** 20주차 문제 11($7^{42}$의 일의 자리)을 $\mathbb{Z}_{10}$의 언어로 다시 쓰시오: $[7]$의 거듭제곱 $[7]^1, [7]^2, [7]^3, [7]^4, \dots$이 $\mathbb{Z}_{10}$에서 어떤 순환을 그리는지 나열하고 $[7]^{42}$를 구하시오.

:::{admonition} 힌트
:class: quotebox dropdown

$7^{42}$를 정수로 계산하지 않는다. $[7]^k$를 하나씩 곱하되 매번 $\bmod 10$으로

줄이면 곧 $[1]$이 나오고, $42$를 그 주기로 나눈 나머지가 답의 자리를 정한다.
:::

**13.** 다음 '정의' 시도가 잘 정의되지 **않음**을 반례로 보이시오: "$\mathbb{Z}_6$에서 $f([a]) = [a$를 2로 나눈 몫$]$, 즉 $f([2k]) = [k]$." (힌트: $[2] = [8]$인데 $f$의 출력은?)

**14.** $\mathbb{Z}_n$에서 $[a] + [x] = [0]$의 해(덧셈 역원)가 항상 존재함을 보이고, $\mathbb{Z}_6$에서 각 방의 덧셈 역원을 표로 만드시오.

:::{admonition} 힌트
:class: quotebox dropdown

증인 제시다. $[a] + [\,?\,] = [a + ?] = [0]$이 되려면 괄호 안의 정수 합이 $n$의

배수여야 한다.
:::

### 도전 ●●●

:::{admonition} 이 문제가 빌려 쓰는 사실 — 유클리드 보조정리
:class: quotebox

$p$가 소수이고 $p \mid ab$이면 $p \mid a$ 또는 $p \mid b$이다. 지금은 증명 없이

인정하고 쓴다 — 33주차 문제 16에서 이 보조정리가 소인수분해의 유일성을

떠받친다는 것까지 확인했고, 증명 자체는 정수론 과목의 몫으로 남겨 두었다.

"소수"라는 조각이 왜 필요한지는 2주차 문제 15의 반례가 보여 준다:

$6 \mid (4 \times 9)$이지만 $6 \nmid 4$이고 $6 \nmid 9$이다.
:::

**15.** $p$가 소수일 때 $\mathbb{Z}_p$에 영인수가 없음을 증명하시오 — 즉 $[a][b] = [0]$이면 $[a] = [0]$ 또는 $[b] = [0]$. (힌트: $[ab] = [0] \iff p \mid ab$ — 유클리드 보조정리(33주차 문제 16: $p \mid ab \Rightarrow p \mid a \lor p \mid b$)를 **사실로 인정**하고 사용하시오)

:::{admonition} 힌트
:class: quotebox dropdown

예제 2.1과 같은 왕복이다: 가정을 수 차원으로 번역 $\to$ 보조정리 적용 $\to$ 역번역.

$[x] = [0] \iff p \mid x$를 먼저 확인한다.
:::

**16.** 역으로, $n$이 합성수이면 $\mathbb{Z}_n$에 영인수가 존재함을 증명하시오. (힌트: $n = ab$, $1 < a, b < n$ — 이 $[a], [b]$가 증인)

:::{admonition} 힌트
:class: quotebox dropdown

훈련 3의 $\mathbb{Z}_{12}$ 판을 문자로 옮긴다. 정의 15.3이 분해를 내주고

$1 < a < n$이 $[a] \neq [0]$을 보장한다 — 그 부등식의 사용처를 명시한다.
:::

**17.** $\mathbb{Z}_5$에서 $[2]^k$ ($k = 1, 2, 3, 4$)를 계산해 $[0]$ 아닌 모든 방이 $[2]$의 거듭제곱으로 나오는지 확인하시오. $\mathbb{Z}_8$에서 $[3]^k$는 어떤가 — 같은 현상이 일어나는가?

**18.** (진단) 다음 답안의 결함을 지적하시오. 실제로 해가 있는지 전수 대입으로 확인하고, 논증의 어느 단계가 무효인지 짚으시오.

:::{container} quotebox
"$\mathbb{Z}_6$에서 $[4][x] = [2]$를 푼다. $[4] = [2][2]$이므로 양변을 $[2]$로 나누면 $[2][x] = [1]$, 다시 나누면 $[x] = [2]^{-1}[1]$… 그런데 $[2]$의 역원이 없으므로 해가 없다. $\blacksquare$"
:::

:::{admonition} 힌트
:class: quotebox dropdown

결론이 틀렸다는 것과 논증이 무효라는 것을 각각 따로 보인다. 앞쪽은 여섯 후보

전수 대입, 뒤쪽은 "나누기는 근거 목록에 없다"(§1.5)의 적용 지점 찾기다.
:::

**19.** $\mathbb{Z}_n$에서 덧셈 교환법칙 $[a] + [b] = [b] + [a]$와 분배법칙 $[a]([b] + [c]) = [a][b] + [a][c]$가 성립함을 증명하시오. (힌트: 전부 $\mathbb{Z}$의 해당 법칙 + 연산 정의로 한 줄씩 — "위층의 법칙은 아래층에서 상속된다")

**20.** (서술) (a) "잘 정의됨" 검문이 필요한 이유를 "방의 이름이 여러 개"라는 사실과 연결해 두 문장 이내로. (b) $\mathbb{Z}_5$와 $\mathbb{Z}_6$의 곱셈 세계의 차이(영인수$\cdot$역원$\cdot$소거)를 요약하고, 그 차이가 5와 6의 어떤 성질에서 오는지 한 문장으로.

## 백지 재현 — 복습 프로토콜

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

**1차 시도 (4일차) — 틀 카드 허용.** 번역–보존–역번역 3단 뼈대(§2 관찰)와 근거 목록(§1.5)만 펴 놓고 예제 2.1을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

**2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다.

- [ ] 정의 38.1을 "동치류 전체의 집합"이라는 조각까지 그대로 썼다.
- [ ] $|\mathbb{Z}_n| = n$의 근거를 두 조각(덮음 / 중복 없음)으로 나눠 적었다.
- [ ] 정의 38.2(잘 정의됨)와 정의 38.3(두 연산)을 썼다.
- [ ] 예제 2.1을 백지에 재현했고, (C4)를 인용한 줄을 손가락으로 짚을 수 있다.
- [ ] $\mathbb{Z}_4$ 또는 $\mathbb{Z}_6$의 곱셈표를 그려 영인수를 찾았다.
- [ ] 예제 2.3에서 해가 두 개인 이유(역원 부재)를 한 문장으로 설명했다.
- [ ] 소수 $\mathbb{Z}_p$와 합성수 $\mathbb{Z}_n$의 차이를 영인수$\cdot$역원$\cdot$소거로 나눠 설명했다.

**막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다.

| **막힌 지점** | **처방** |
|---|---|
| "원소가 동치류"라는 말이 낯설다 | §1.1~§1.2 — $S$가 왜 막혔는지부터 다시 읽는다 |
| 정의 38.1이 정확히 기억나지 않는다 | §1.3 해부 표 — 조각의 이유와 함께 다시 외운다 |
| 잘 정의됨이 왜 필요한지 흐릿하다 | §1.4의 규칙 B — 답이 갈리는 계산을 손으로 한 번 더 |
| 증명의 첫 줄이 나오지 않는다 | 예제 2.1의 번역표 — 출발점과 도착점을 수 차원으로 먼저 적는다 |
| 셋째 줄에서 무엇을 인용할지 모르겠다 | §1.5 근거 목록 ④ — 덧셈이면 (C4), 곱셈이면 (C5) |
| 방정식에서 나누고 싶어진다 | §1.5의 확인 6 (다)와 예제 2.3 — 역원 존재 확인이 먼저다 |
| 표를 다 채웠는데 무엇을 볼지 모르겠다 | 예제 2.2의 관찰 — $0$이 나온 칸과 $1$이 나온 칸을 각각 센다 |

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

## 해설

각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

### 빈칸 사다리 — 훈련 1

(1) $[2]$ ($3+4 = 7 \equiv 2$)  (2) $[2]$ ($12 \equiv 2$)  (3) $[1]$ ($16 \equiv 1$) (4) $[2]$ ($3 \times 2 = 6 \equiv 1 \pmod 5$)  (5) 없다 — $0$행$\cdot$$0$열 밖에는 $0$이 나오지 않는다.

※ (4)의 역원은 다섯 후보를 차례로 곱해 보는 전수 확인으로 찾는다. (5)의 "없다"는 문제 15에서 소수라는 조건으로 일반화된다.

### 빈칸 사다리 — 훈련 2

(1) 가정  (2) 핵심 정리(37주차)  (3) (C5) 곱 보존(20주차) (4) $a' \cdot a'$  (5) 핵심 정리  (6) $[a^2] = [a'^2]$

※ (C5)는 두 합동을 받아 곱의 합동을 내주는 정리이므로 합동 하나를 자기 자신과 짝지어 넣을 수 있다 — $a \equiv a'$을 두 번 넣으면 $a \cdot a \equiv a' \cdot a'$이 나온다. 이 훈련은 문제 7의 특수한 경우($b = a$, $b' = a'$)이므로, 문제 7을 먼저 풀었다면 근거 ④로 한 줄에 끝난다.

### 빈칸 사다리 — 훈련 3

(1) $12$를 $1$보다 크고 $12$보다 작은 두 수의 곱으로 쪼갠다. $12 = 3 \times 4$를 택해 증인 후보를 $[3]$과 $[4]$로 잡는다. (2) $0 < 3 < 12$이므로 $3$을 $12$로 나눈 나머지는 $3 \neq 0$이고, 따라서 $3 \not\equiv 0 \pmod{12}$, 핵심 정리에 의해 $[3] \neq [0]$이다. 같은 이유로 $[4] \neq [0]$이다. (3) $[3][4] = [12] = [0]$이다. $[0]$이 아닌 두 원소의 곱이 $[0]$이므로 증인이 확보되었고, 따라서 $\mathbb{Z}_{12}$에는 그런 쌍이 존재한다. $\blacksquare$

※ $12 = 2 \times 6$으로 잡아 $[2], [6]$을 증인으로 써도 된다. 존재 명제는 증인 하나면 충분하므로 어느 분해를 택해도 완결이다.

### 문제 1

**접근.** 정의 38.1을 쓴 뒤 크기의 근거를 두 조각으로 나눈다 — "모든 동치류가 목록 안에 있다"(덮음)와 "목록의 항목들이 서로 다르다"(중복 없음).

**풀이.** 정의: 자연수 $n$에 대해 $\mathbb{Z}_n$은 $\equiv \pmod n$의 동치류 전체의 집합이고 $\mathbb{Z}_n = \{[0], \dots, [n-1]\}$, $|\mathbb{Z}_n| = n$이다. ① 덮음: 임의의 정수 $a$에 대해 나눗셈 정리(33주차 예제 2.2)로 $a = nq + r$, $0 \le r < n$인 $q, r$이 존재한다. $a - r = nq$이므로 $a \equiv r \pmod n$이고, 핵심 정리에 의해 $[a] = [r]$이다. $r \in \{0, \dots, n-1\}$이므로 모든 동치류가 목록 안에 있다. ② 중복 없음: $0 \le r < r' < n$이면 $0 < r' - r < n$이라 $r' - r$은 $n$의 배수가 아니므로 $r \not\equiv r' \pmod n$이고, 핵심 정리의 대우에 의해 $[r] \neq [r']$이다. (나눗셈 정리의 유일성(33주차 문제 10)이 "각 정수가 목록의 정확히 한 항목에 대응한다"를 같은 내용으로 말해 준다.) 두 근거를 합치면 $|\mathbb{Z}_n| = n$이다.

**복기.** 유한집합의 크기를 세는 답안은 늘 이 두 조각이다 — 빠짐없이 덮는가, 겹치지 않는가. 37주차 분할 조건과 같은 구조다.

### 문제 2

**접근.** 대표원을 정수로 계산한 뒤 $\bmod 7$로 줄인다(정의 38.3). 답안에는 계산과 축소를 각각 적는다 — 축소의 근거는 핵심 정리다.

**풀이.** (a) $[5] + [4] = [9]$이고 $9 - 2 = 7$이므로 $9 \equiv 2 \pmod 7$, 따라서 $[2]$. (b) $[5][4] = [20]$이고 $20 - 6 = 14 = 7 \times 2$이므로 $20 \equiv 6$, 따라서 $[6]$. (c) $[6]^2 = [36]$이고 $36 - 1 = 35 = 7 \times 5$이므로 $36 \equiv 1$, 따라서 $[1]$. (d) $[3]^3 = [27]$이고 $27 - 6 = 21 = 7 \times 3$이므로 $27 \equiv 6$, 따라서 $[6]$.

(검산: (c)는 $[6] = [-1]$이므로 $[6]^2 = [(-1)^2] = [1]$로도 같은 답이 나온다 — 대표원을 바꿔도 답이 같은 것이 잘 정의됨의 실제 효용이다.)

**복기.** 중간중간 줄이는 편이 짧다 — (d)를 $[3][3][3] = [9][3] = [2][3] = [6]$ 으로 처리하면 $27$을 만들 필요가 없다. 이 요령이 문제 12에서 쓰인다.

### 문제 3

**접근.** 핵심 정리는 양방향이다. 같음은 합동을 확인해 $\Rightarrow$ 방향으로, 다름은 비합동을 확인해 대우로 쓴다. 합동 확인은 차가 $6$의 배수인지 보는 일이다.

**풀이.** $[4] = [22]$인 이유: $22 - 4 = 18 = 6 \times 3$이므로 $6 \mid (22 - 4)$, 곧 $4 \equiv 22 \pmod 6$이다. 핵심 정리에 의해 $[4] = [22]$이다. $[4] \neq [3]$인 이유: $4 - 3 = 1$은 $6$의 배수가 아니므로 $4 \not\equiv 3 \pmod 6$이다. 핵심 정리의 대우($x \not\equiv y$이면 $[x] \neq [y]$)에 의해 $[4] \neq [3]$이다.

**복기.** 두 동치류가 다름을 보이는 일은 무한집합을 원소 단위로 비교하는 일이 아니다 — 대표원 두 개의 비합동 하나면 끝난다. 무한집합의 상등 판정을 유한한 계산으로 바꾼 것이 핵심 정리의 값어치다.

### 문제 4

**접근.** (1)~(3)은 정수 계산 후 $\bmod 5$ 축소, (4)는 다섯 후보 전수 확인, (5)는 곱셈표에서 $0$ 찾기다.

**풀이.** (1) $3 + 4 = 7 \equiv 2 \pmod 5$이므로 $[2]$. (2) $3 \times 4 = 12 \equiv 2$이므로 $[2]$. (3) $4^2 = 16 \equiv 1$이므로 $[1]$. (4) 후보를 차례로 곱하면 $3 \times 1 = 3$, $3 \times 2 = 6 \equiv 1$이므로 역원은 $[2]$이다 ($3 \times 0 = 0$, $3 \times 3 = 9 \equiv 4$, $3 \times 4 = 12 \equiv 2$로 다섯 후보를 빠짐없이 확인했고 나머지 후보는 $[1]$을 주지 않는다). (5) 없다 — 문제 6의 곱셈표에서 $0$행$\cdot$$0$열 밖의 열여섯 칸에 $0$이 하나도 없다.

**복기.** (4)와 (5)는 각각 문제 9와 문제 15의 축소판이다. 역원이 전부 존재하고 영인수가 없다는 두 현상은 $5$가 소수라는 사실에서 온다 — 문제 20 (b)의 답이다.

### 문제 5

**접근.** 네 줄이다 — 가정 선언 $\to$ 핵심 정리로 합동 번역 $\to$ (C4) 인용 $\to$ 핵심 정리로 역번역.

**풀이.** $[a] = [a']$이고 $[b] = [b']$이라 가정하자. 핵심 정리(37주차)에 의해 $a \equiv a' \pmod n$이고 $b \equiv b' \pmod n$이다. (C4) 합 보존(20주차)에 의해 $a + b \equiv a' + b' \pmod n$이다. 다시 핵심 정리에 의해 $[a+b] = [a'+b']$이다. $\blacksquare$ 따라서 $[a] + [b] = [a+b]$는 대표원의 선택에 무관하므로 잘 정의된다.

**복기.** 자가 채점 항목은 셋이다. ① 첫 줄이 이름 두 벌을 놓았는가 ② 셋째 줄에 (C4)라는 이름이 적혔는가 ③ 마지막 줄이 집합 차원으로 되돌아왔는가. ③이 빠지면 증명한 것은 수의 합동이지 방의 상등이 아니다.

### 문제 6

**접근.** 각 칸은 정수로 계산한 뒤 $\bmod 5$로 줄인다. 다 채운 뒤 덧셈표는 각 행이 $0 \sim 4$를 한 번씩 순회하고, 곱셈표는 $0$행을 뺀 각 행이 그러한지 확인하면 실수를 잡을 수 있다.

**풀이.** 덧셈표:

| **$+$** | **0** | **1** | **2** | **3** | **4** |
|---|---|---|---|---|---|
| **0** | 0 | 1 | 2 | 3 | 4 |
| **1** | 1 | 2 | 3 | 4 | 0 |
| **2** | 2 | 3 | 4 | 0 | 1 |
| **3** | 3 | 4 | 0 | 1 | 2 |
| **4** | 4 | 0 | 1 | 2 | 3 |

곱셈표:

| **$\times$** | **0** | **1** | **2** | **3** | **4** |
|---|---|---|---|---|---|
| **0** | 0 | 0 | 0 | 0 | 0 |
| **1** | 0 | 1 | 2 | 3 | 4 |
| **2** | 0 | 2 | 4 | 1 | 3 |
| **3** | 0 | 3 | 1 | 4 | 2 |
| **4** | 0 | 4 | 3 | 2 | 1 |

계산 예: 곱셈표 $3$행 $4$열은 $3 \times 4 = 12 \equiv 2 \pmod 5$이므로 $2$이다. 관찰: $0$행$\cdot$$0$열 밖에 $0$이 없고(영인수 없음), $0$행을 제외한 각 행에 $1$이 정확히 한 번 나온다(모든 $[0]$ 아닌 원소가 역원을 가짐).

**복기.** 표를 채운 뒤 무엇을 보는지가 실력이다 — $0$이 나온 칸(영인수)과 $1$이 나온 칸(역원)을 센다. 문제 8에서 $\mathbb{Z}_6$에 같은 두 항목을 적용하면 결과가 정반대로 나온다.

### 문제 7

**접근.** 관찰 절의 대응표 오른쪽 열이 그대로 답이다 — 예제 2.1에서 바뀌는 곳은 셋째 줄의 인용 정리와 그에 따라 따라오는 넷째 줄뿐이고, 셋째 줄에서 (C4) 대신 (C5)를 인용한다.

**풀이.** $[a] = [a']$이고 $[b] = [b']$이라 가정하자. 핵심 정리(37주차)에 의해 $a \equiv a' \pmod n$이고 $b \equiv b' \pmod n$이다. (C5) 곱 보존(20주차)에 의해 $ab \equiv a'b' \pmod n$이다. 다시 핵심 정리에 의해 $[ab] = [a'b']$이다. $\blacksquare$ 따라서 $[a][b] = [ab]$는 대표원의 선택에 무관하므로 잘 정의된다.

(검산: $n = 6$, $a = 2$, $a' = 8$, $b = 3$, $b' = 9$이면 $[6] = [72]$가 되어야 한다 — $72 - 6 = 66 = 6 \times 11$이므로 성립한다.)

**복기.** 두 증명의 차이가 정리 이름 하나뿐이라는 것은, 잘 정의됨 증명의 난이도가 "그에 맞는 보존 정리가 이미 증명되어 있는가"에 전적으로 달렸다는 뜻이다.

### 문제 8

**접근.** $6 \times 6$ 표를 채운 뒤 두 번 훑는다 — (a)는 $0$행$\cdot$$0$열 밖에서 $0$ 찾기, (b)는 같은 범위에서 $1$ 찾기다.

**풀이.** 곱셈표:

| **$\times$** | **0** | **1** | **2** | **3** | **4** | **5** |
|---|---|---|---|---|---|---|
| **0** | 0 | 0 | 0 | 0 | 0 | 0 |
| **1** | 0 | 1 | 2 | 3 | 4 | 5 |
| **2** | 0 | 2 | 4 | 0 | 2 | 4 |
| **3** | 0 | 3 | 0 | 3 | 0 | 3 |
| **4** | 0 | 4 | 2 | 0 | 4 | 2 |
| **5** | 0 | 5 | 4 | 3 | 2 | 1 |

(a) $0$행$\cdot$$0$열 밖에서 $0$이 나오는 칸은 $[2][3]$, $[3][2]$, $[3][4]$, $[4][3]$이다. 확인: $[2][3] = [6] = [0]$, $[3][4] = [12] = [0]$. 따라서 영인수 쌍은 $\{[2], [3]\}$과 $\{[3], [4]\}$이고, 영인수인 원소는 $[2], [3], [4]$다. (b) $1$이 나오는 칸은 $[1][1] = [1]$과 $[5][5] = [25] = [1]$뿐이다. 따라서 곱셈 역원을 갖는 방은 $[1]$과 $[5]$ 둘뿐이며 각각 자기 자신이 역원이다. $[2], [3], [4]$의 행에는 $1$이 한 번도 나오지 않으므로 역원이 없다.

**관찰.** 역원을 가진 대표원 $1, 5$는 $6$과의 공약수가 $\pm 1$뿐이고, 역원이 없는 $2, 3, 4$는 각각 $6$과 $2$ 또는 $3$을 공유한다. "역원 보유와 $n$과의 서로소성이 맞물린다"는 관찰은 지금은 표에서 읽은 사실로 두고, 증명은 정수론 과목의 몫이다.

**복기.** 문제 6의 $\mathbb{Z}_5$와 정반대 결과다. 같은 절차를 두 무대에 적용해 결과가 갈리는 것을 확인하는 것이 이번 주 관찰의 핵심이고, 갈리는 이유는 문제 15$\cdot$16에서 소수성으로 확정된다.

### 문제 9

**접근.** 앞부분은 $3x \equiv 1 \pmod 7$인 $x$를 일곱 후보에서 찾는 일이고, 뒷부분은 "양변에 역원을 곱한다"(근거 ③)로 적어야 근거 목록 안에 남는다.

**풀이.** 역원 찾기: $[3][0] = [0]$, $[3][1] = [3]$, $[3][2] = [6]$, $[3][3] = [9] = [2]$, $[3][4] = [12] = [5]$, $[3][5] = [15] = [1]$, $[3][6] = [18] = [4]$이다. 일곱 후보를 빠짐없이 확인했으므로 $[3][x] = [1]$의 해는 $[x] = [5]$뿐이고, $[3]$의 곱셈 역원은 $[5]$이다. 방정식 풀기: $[3][x] = [5]$의 양변에 $[5]$를 곱하면(근거 ③)

$$
[5]([3][x]) = [5][5]
$$

이다. 좌변은 정의 38.3을 두 번 적용해 $[5]([3][x]) = [5][3x] = [5(3x)]$이고, $\mathbb{Z}$의 곱셈 결합법칙 $5(3x) = (5 \cdot 3)x$를 쓴 뒤 다시 정의 38.3으로 올라오면 $[(5 \cdot 3)x] = [15][x] = [1][x] = [x]$이다 — 결합법칙 자체가 정의 38.3으로 $\mathbb{Z}$에 내려갔다 올라오는 왕복으로 얻어진다(문제 19와 같은 방식). 우변은 $[5][5] = [25] = [4]$이다. 따라서 $[x] = [4]$이다. 검산: $[3][4] = [12] = [5]$로 원래 방정식을 만족한다.

**복기.** 역원이 존재하면 "나누기"가 "역원 곱하기"로 되살아나고 소거도 가능해져 해가 유일해진다 — $\mathbb{Z}_7$이 실수처럼 구는 이유다. 역원이 없을 때는 예제 2.3과 문제 18의 상황이 된다.

### 문제 10

**접근.** 여덟 후보의 제곱을 전부 적고, 해로 나온 대표원들이 공통으로 갖는 성질을 본다 — 거기서 17주차 문제 15와의 연결이 드러난다.

**풀이.** 전수 대입:

$$
[0]^2 = [0], \quad [1]^2 = [1], \quad [2]^2 = [4], \quad [3]^2 = [9] = [1], \quad [4]^2 = [16] = [0], \quad [5]^2 = [25] = [1], \quad [6]^2 = [36] = [4], \quad [7]^2 = [49] = [1]
$$

$[1]$이 나온 자리는 $[1], [3], [5], [7]$ 네 곳이다. 후보 여덟 개를 빠짐없이 확인했으므로 해는 이 넷뿐이다(실수에서 $x^2 = 1$의 해는 둘인데 여기서는 넷이다). 연결: 해로 나온 대표원 $1, 3, 5, 7$은 정확히 $0 \le r < 8$인 홀수 전부이므로, "$\mathbb{Z}_8$에서 홀수 대표원의 제곱은 $[1]$"은 "모든 홀수 $n$에 대해 $n^2 = 8m + 1$"(17주차 문제 15)을 동치류의 언어로 옮긴 문장이다.

(검산: $17^2 = 289 = 8 \times 36 + 1$이므로 $[17]^2 = [1]$이고, $[17] = [1]$이므로 위 목록과도 어긋나지 않는다.)

**복기.** 17주차에서 정수의 언어로 증명한 사실이 여기서는 여덟 칸짜리 표의 한 줄로 보인다. 무대가 유한하면 "모든 홀수"에 대한 명제가 유한 개의 확인으로 닫힌다.

### 문제 11

**접근.** 문제 8의 $[3]$ 행에는 $3$이 여러 번 나온다 — 서로 다른 두 입력이 같은 출력을 주는 자리가 곧 반례다. 서식은 세 조각이다: 제시 / 가정이 참임을 확인 / 결론이 거짓임을 확인.

**풀이.** 반례: $\mathbb{Z}_6$에서 $[x] = [1]$, $[y] = [3]$. 가정 확인 — $[3][1] = [3]$이고 $[3][3] = [9] = [3]$이므로($9 - 3 = 6$) $[3][x] = [3][y]$가 성립한다. 결론 확인 — $3 - 1 = 2$는 $6$의 배수가 아니므로 $1 \not\equiv 3 \pmod 6$이고, 핵심 정리에 의해 $[1] \neq [3]$이다. 가정이 참인데 "$[x] = [y]$"가 거짓이므로, $\mathbb{Z}_6$에서 $[3]$을 양변에서 지우는 소거는 정당한 변형이 아니다. $\blacksquare$

**복기.** 소거가 무너진 이유는 $[3]$이 곱셈 역원을 갖지 않는다는 것이다(문제 8(b)). 역원이 있으면 양변에 그것을 곱해 소거가 정당해지고, 없으면 지우기는 근거 없는 변형이다 — 27주차 문제 19와 같은 진단이다.

### 문제 12

**접근.** $7^{42}$를 정수로 계산하지 않는다 — $[7]^k$를 하나씩 곱하되 매번 $\bmod 10$으로 줄이면 곧 $[1]$이 나오고 거기서 주기가 확정된다.

**풀이.** 거듭제곱을 차례로 줄이며 계산한다.

$$
[7]^1 = [7], \quad [7]^2 = [49] = [9], \quad [7]^3 = [7][9] = [63] = [3], \quad [7]^4 = [7][3] = [21] = [1]
$$

$[7]^4 = [1]$이므로 그다음부터는 같은 값이 되풀이된다($[7]^5 = [1][7] = [7]$). 따라서 $[7]$의 거듭제곱은 $[7] \to [9] \to [3] \to [1]$을 주기 $4$로 순환한다. $42 = 4 \times 10 + 2$이므로

$$
[7]^{42} = \left([7]^4\right)^{10}[7]^2 = [1]^{10}[9] = [9]
$$

이다. 즉 $7^{42}$의 일의 자리는 $9$이고, 20주차 문제 11의 답과 일치한다.

**복기.** 20주차의 "$7^4 \equiv 1 \pmod{10}$이므로 지수를 $4$로 나눈 나머지를 본다"가, 지금은 "$\mathbb{Z}_{10}$에서 $[7]$의 거듭제곱이 그리는 순환"으로 보인다. 무대가 유한하면 거듭제곱은 반드시 되풀이된다 — 값이 $n$가지뿐이기 때문이다.

### 문제 13

**접근.** §1.4의 규칙 B와 같은 구조다. 같은 방의 이름 둘에 규칙을 적용해 출력이 갈리는지 보고, 두 출력이 다르다는 것도 핵심 정리로 확인한다.

**풀이.** $\mathbb{Z}_6$에서 $[2] = [8]$이다 — $8 - 2 = 6$이므로 $2 \equiv 8 \pmod 6$이고 핵심 정리에 의해 두 방이 같다. 같은 방에 규칙을 적용하면, 대표원 $2 = 2 \times 1$에서는 $f([2]) = [1]$이고 대표원 $8 = 2 \times 4$에서는 $f([8]) = [4]$이다. 그런데 $4 - 1 = 3$은 $6$의 배수가 아니므로 $1 \not\equiv 4 \pmod 6$이고, 핵심 정리에 의해 $[1] \neq [4]$이다. 같은 입력에 서로 다른 출력이 나왔으므로 이 규칙은 잘 정의되지 않는다. $\blacksquare$

**복기.** 잘 정의됨을 부정하는 답안에도 세 조각이 필요하다 — ① 두 이름이 같은 방임을 확인 ② 각각의 출력을 계산 ③ 두 출력이 다른 방임을 확인. "$2$로 나누기"에 (C4)(C5) 같은 보존 정리가 없어서 이런 일이 생긴다 — 보존 정리가 없는 연산은 동치류 위로 올라오지 못한다.

### 문제 14

**접근.** 증인 제시다(26주차의 존재 서식). $[a] + [\,?\,] = [a + ?] = [0]$이 되려면 괄호 안의 정수 합이 $n$의 배수여야 하므로 가장 간단한 증인은 $n - a$다.

**풀이.** $[a] \in \mathbb{Z}_n$을 임의로 잡고 증인으로 $[x] = [n - a]$를 제시한다. 정의 38.3에 의해

$$
[a] + [n - a] = [a + (n - a)] = [n]
$$

이고, $n \equiv 0 \pmod n$이므로 핵심 정리에 의해 $[n] = [0]$이다. 따라서 $[a] + [n-a] = [0]$이고 덧셈 역원이 존재한다. $[a]$는 임의였으므로 모든 원소가 덧셈 역원을 갖는다. $\blacksquare$ 유일성도 성립한다: $[a] + [x] = [0] = [a] + [x']$ 이면 양변에 $[n-a]$를 더해 $[x] = [x']$을 얻는다. 이 한 줄은 덧셈의 결합법칙과 항등원 $[0]$을 쓰는데, 둘 다 정의 38.3으로 $\mathbb{Z}$에 내려갔다 올라오는 왕복으로 확보된다 — $([n-a] + [a]) + [x] = [(n-a) + a + x] = [n-a] + ([a] + [x])$이고 $[0] + [x] = [0 + x] = [x]$이다(문제 19와 같은 방식). 덧셈에서는 역원이 항상 있어 소거가 늘 정당하다(곱셈에서 무너진 것과 대조된다 — 문제 11).

$\mathbb{Z}_6$의 덧셈 역원 표:

| **$[a]$** | **$[0]$** | **$[1]$** | **$[2]$** | **$[3]$** | **$[4]$** | **$[5]$** |
|---|---|---|---|---|---|---|
| 덧셈 역원 | $[0]$ | $[5]$ | $[4]$ | $[3]$ | $[2]$ | $[1]$ |

(검산: $[2] + [4] = [6] = [0]$, $[3] + [3] = [6] = [0]$.)

**복기.** 덧셈과 곱셈의 비대칭이 이번 주의 큰 그림이다 — 덧셈 역원은 항상 존재하지만 곱셈 역원은 조건부이고, 그 조건이 문제 15$\cdot$16에서 소수성과 맞물린다.

### 문제 15

**접근.** 예제 2.1과 같은 왕복이다: 가정을 수 차원으로 번역 $\to$ 유클리드 보조정리 적용 $\to$ 결론을 집합 차원으로 역번역. 번역의 열쇠는 "$[x] = [0] \iff x \equiv 0 \pmod p \iff p \mid x$"다.

**풀이.** $p$를 소수라 하고 $\mathbb{Z}_p$에서 $[a][b] = [0]$이라 가정하자. 정의 38.3에 의해 $[ab] = [0]$이고, 핵심 정리에 의해 $ab \equiv 0 \pmod p$, 곧 $p \mid ab$이다. 유클리드 보조정리(지금은 인정하고 쓴다 — 33주차 문제 16)에 의해 $p \mid a$ 또는 $p \mid b$이다. $p \mid a$인 경우 $a \equiv 0 \pmod p$이므로 핵심 정리에 의해 $[a] = [0]$이고, $p \mid b$인 경우 같은 논증으로 $[b] = [0]$이다. 어느 경우든 $[a] = [0]$ 또는 $[b] = [0]$이므로 $\mathbb{Z}_p$에는 영인수가 없다. $\blacksquare$

**복기.** 25주차 문제 13에서 실수에 대해 확인한 영인수 성질이 소수 무대에서 되살아났다. 되살리는 대가가 유클리드 보조정리이고, 그것이 없는 무대에서는 성질이 그대로 무너진다 — 문제 16이 그 붕괴를 증인으로 보인다.

### 문제 16

**접근.** 훈련 3의 $\mathbb{Z}_{12}$ 판을 문자로 옮긴다. 합성수의 정의가 분해 $n = ab$를 내주고 $1 < a < n$이 $[a] \neq [0]$을 보장한다 — 그 부등식의 사용처를 명시하는 것이 채점 항목이다.

**풀이.** $n$을 합성수라 하자. 정의 15.3에 의해 $n = ab$이고 $1 < a < n$, $1 < b < n$인 정수 $a, b$가 존재한다. $0 < a < n$이므로 $a$를 $n$으로 나눈 나머지는 $a$ 자신이고 $0$이 아니다. 따라서 $a \not\equiv 0 \pmod n$이고 핵심 정리에 의해 $[a] \neq [0]$이며, 같은 이유로 $[b] \neq [0]$이다. 곱을 계산하면 정의 38.3에 의해

$$
[a][b] = [ab] = [n] = [0]
$$

이다(마지막 등식은 $n \equiv 0 \pmod n$과 핵심 정리). 따라서 $[a], [b]$가 $[0]$이 아니면서 곱이 $[0]$인 쌍이므로 $\mathbb{Z}_n$에 영인수가 존재한다. $\blacksquare$

(검산: $n = 6 = 2 \times 3$이면 증인은 $[2], [3]$이고 실제로 $[2][3] = [0]$이다 — 문제 8(a)의 표와 일치한다.)

**복기.** 문제 15와 합치면 "$n \ge 2$일 때 $\mathbb{Z}_n$에 영인수가 없다 $\iff$ $n$이 소수"가 된다($n = 1$은 $\mathbb{Z}_1 = \{[0]\}$이라 $[0]$이 아닌 원소 자체가 없으므로 양쪽 모두에서 제외한다). 한 방향은 유클리드 보조정리를, 다른 방향은 증인 제작만을 쓴다 — 동치의 두 방향이 난이도가 전혀 다를 수 있다는 사례다.

### 문제 17

**접근.** 두 경우 모두 $[1]$이 나오는 순간 순환이 닫힌다 — 그때까지 나온 값을 모아 $[0]$ 아닌 원소 전체와 비교한다.

**풀이.** $\mathbb{Z}_5$에서

$$
[2]^1 = [2], \quad [2]^2 = [4], \quad [2]^3 = [8] = [3], \quad [2]^4 = [16] = [1]
$$

이므로 나온 값은 $\{[2], [4], [3], [1]\}$이고, 이는 $\mathbb{Z}_5$에서 $[0]$이 아닌 원소 전부다. 따라서 $[0]$ 아닌 모든 방이 $[2]$의 거듭제곱으로 나온다. $\mathbb{Z}_8$에서는

$$
[3]^1 = [3], \quad [3]^2 = [9] = [1], \quad [3]^3 = [3], \quad [3]^4 = [1]
$$

이므로 나온 값은 $\{[3], [1]\}$ 두 개뿐이고 주기가 $2$에서 닫힌다. $\mathbb{Z}_8$에서 $[0]$이 아닌 원소는 일곱 개이므로 전부를 순회하지 못한다. 따라서 같은 현상은 일어나지 않는다. 특히 $[2], [4], [6]$처럼 짝수 대표원을 갖는 방은 홀수 대표원의 거듭제곱으로 나올 수 없다 — 홀수의 거듭제곱은 늘 홀수이고 홀수를 $8$로 나눈 나머지도 홀수이기 때문이다.

**복기.** 하나의 원소가 거듭제곱만으로 무대 전체를 훑는 일은 소수 무대에서 일어나고 합성수 무대에서는 대체로 일어나지 않는다. 확인 방법은 문제 12와 같다.

### 문제 18

**접근.** 두 가지를 각각 보여야 한다. ① 결론("해가 없다")이 실제로 틀렸다 — 전수 대입으로 해를 찾아낸다. ② 논증이 무효다 — "나누기는 근거 목록에 없다"를 어느 줄에 적용할지 고른다.

**풀이.** 먼저 전수 대입으로 해를 확인한다. $\mathbb{Z}_6$에서

$$
[4][0] = [0], \quad [4][1] = [4], \quad [4][2] = [8] = [2], \quad [4][3] = [12] = [0], \quad [4][4] = [16] = [4], \quad [4][5] = [20] = [2]
$$

$[2]$가 나온 자리는 $[x] = [2]$와 $[x] = [5]$ 두 곳이므로 해가 존재하며 그것도 두 개다 — 답안의 결론 "해가 없다"는 거짓이다. 논증의 결함은 "양변을 $[2]$로 나누면"이라는 첫 변형에 있다. $\mathbb{Z}_6$에는 나눗셈 연산이 정의되어 있지 않고(정의 38.3이 준 것은 덧셈과 곱셈뿐이다), 같은 뜻을 "양변에 $[2]$의 역원을 곱한다"로 바꿔 적으려 해도 $[2]$는 곱셈 역원을 갖지 않는다(문제 8(b)). $[4] = [2][2]$에서 $[2]$ 하나를 지우는 소거 역시 정당하지 않다(문제 11). 즉 무효인 변형으로 얻은 $[2][x] = [1]$은 원래 방정식과 아무 관계가 없고, 그 방정식에 해가 없다는 사실도 원래 방정식에 대해 아무것도 말해 주지 않는다. 답안이 스스로 "$[2]$의 역원이 없다"를 확인했다는 점도 짚어 둘 만하다 — 그것을 알았다면 앞 단계의 나누기부터 쓸 수 없었다는 뜻이다.

**복기.** $\mathbb{Z}_n$에서 나누기와 소거는 역원의 존재를 확인한 뒤에만 허용되는 조건부 도구다. 그리고 무효인 변형에서 나온 "해 없음"은 해가 없다는 증거가 아니다 — 결론의 진위와 논증의 유효성은 별개로 판정한다.

### 문제 19

**접근.** 각 줄에서 하는 일은 셋뿐이다 — 정의 38.3으로 내려가기, $\mathbb{Z}$의 법칙 쓰기, 다시 정의 38.3으로 올라오기. 등호마다 근거 이름을 붙이면 완결된다.

**풀이.** (교환법칙) 임의의 $[a], [b] \in \mathbb{Z}_n$에 대해

$$
[a] + [b] = [a + b] = [b + a] = [b] + [a]
$$

이다. 첫째 등호는 정의 38.3, 둘째 등호는 $\mathbb{Z}$의 덧셈 교환법칙 $a + b = b + a$(같은 정수이므로 같은 동치류다), 셋째 등호는 다시 정의 38.3이다. $\blacksquare$

(분배법칙) 임의의 $[a], [b], [c] \in \mathbb{Z}_n$에 대해

$$
[a]([b] + [c]) = [a][b + c] = [a(b+c)] = [ab + ac] = [ab] + [ac] = [a][b] + [a][c]
$$

이다. 첫째$\cdot$둘째 등호는 정의 38.3, 셋째 등호는 $\mathbb{Z}$의 분배법칙 $a(b+c) = ab + ac$, 넷째 등호는 정의 38.3의 덧셈 부분을 거꾸로 읽은 것, 다섯째 등호도 정의 38.3이다. $\blacksquare$

**복기.** 연산이 잘 정의되기만 하면 대수 법칙들은 $\mathbb{Z}$에서 그대로 상속된다 — 정의 38.3으로 내려갔다 올라오는 왕복만 남는다. 결합법칙$\cdot$곱셈 교환법칙도 같은 두 줄로 처리된다.

### 문제 20

**접근.** (a)는 §1.4의 두 규칙이 재료다 — 이름이 여러 개라는 사실과 결과가 갈릴 수 있다는 사실을 잇는다. (b)는 문제 6$\cdot$8의 표 관찰에 문제 15$\cdot$16이 확정한 원인을 붙인다.

**풀이.** (예시 답안) (a) 동치류는 $[2] = [8]$처럼 한 대상이 무한히 많은 이름을 가지므로, 대표원을 골라 계산하는 규칙은 이름을 어떻게 고르든 같은 결과가 나온다는 것이 증명되기 전까지 같은 입력에 두 답을 줄 수 있다. 그런 규칙은 정의가 아니므로, 잘 정의됨 확인이 정의의 일부다. (b) $\mathbb{Z}_5$에서는 곱셈표의 $0$행$\cdot$$0$열 밖에 $0$이 없고(영인수 없음) $0$행을 제외한 각 행에 $1$이 정확히 한 번 나오므로 $[0]$ 아닌 모든 원소가 곱셈 역원을 가지며, 따라서 소거와 "역원 곱하기"가 늘 가능하다. 반면 $\mathbb{Z}_6$에서는 $[2][3] = [0]$ 같은 영인수가 있어 소거가 무너지고 역원을 갖는 방은 $[1], [5]$ 둘뿐이다. 이 차이는 $5$가 소수이고 $6$은 합성수라는 데서 온다 — 합성수의 분해 $6 = 2 \times 3$이 그대로 영인수 쌍을 만들어 내고(문제 16), 소수 무대에서는 유클리드 보조정리가 그런 쌍의 존재를 막는다(문제 15).

**복기.** 서술 문제의 채점 기준도 근거다 — (b)에서 "소수라서"라고만 적으면 절반이고, 소수성이 영인수의 부재로 번역되는 경로(문제 15$\cdot$16)를 지목해야 완결이다.

---

**다음 주 예고:** 39주차는 8부(관계) 전체의 백지 시험이다. 관계의 세 성질 판정(36주차), 동치류와 분할(37주차), 그리고 이번 주의 $\mathbb{Z}_n$ 계산과 잘 정의됨이 한자리에서 검사된다. 잘 정의됨은 8부에서 끝나는 주제가 아니다 — 40주차에서 함수의 정의역이 동치류들의 집합일 때 같은 확인이 함수 자격 심사로 다시 나온다. 이번 주의 네 줄짜리 왕복을 손이 기억하도록 만들어 두면 그때 새로 배울 것이 없다.