# 38주차 — $\mathbb{Z}_n$: 나머지들의 산술 세계 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 대표원으로 계산하는 규칙은, 대표원을 바꿔 잡아도 같은 동치류가 나올 때에만 정의가 된다. **이 주의 위치**: 50주 과정의 38주차. 8부(관계)의 마지막 학습 주다 — 39주차는 8부 전체를 닫는 백지 시험이다. 37주차의 동치류가 원소가 되고, 20주차의 (C4)(C5)가 그 위에 연산을 얹을 자격을 준다. **원서 대응**: BoP(Book of Proof) 11.4 (Integers Modulo n) — 병행자 참고용이고, 이 교재는 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. $\mathbb{Z}_n$의 정의와 $|\mathbb{Z}_n| = n$의 근거(나눗셈 정리의 존재$\cdot$유일)를 백지에 쓸 수 있다. 1. 연산 $[a] + [b] = [a+b]$와 $[a][b] = [ab]$의 **잘 정의됨**을 (C4)(C5)를 인용해 증명할 수 있다. 1. $\mathbb{Z}_4$$\cdot$$\mathbb{Z}_5$$\cdot$$\mathbb{Z}_6$의 연산표를 작성하고 영인수$\cdot$역원$\cdot$소거 실패를 판정할 수 있다. 1. "$\mathbb{Z}_n$에서 나누기는 근거 목록에 없다"를 반례로 설명할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (37주차 복습) 1. 핵심 정리($x\,R\,y \iff [x] = [y]$)를 진술하시오. 1. $\mathbb{Z}$ 위 $\equiv \pmod 4$의 동치류를 모두 나열하시오 (각각 원소 4개씩 예시). 1. 20주차의 (C4)와 (C5)를 진술하시오. ### 자주 나오는 세 가지 답 — 1번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 한 방향만.** "$[x] = [y]$이면 $x\,R\,y$"까지만 적는다. 이 방향은 옳고 이번 주 증명의 둘째 줄(가정을 합동으로 내리는 줄)에서 그대로 쓰인다. 빠진 것은 반대 방향, 곧 마지막 줄에서 쓸 $\Rightarrow$ 방향이다 — 이번 주의 증명은 가정에서 $\Leftarrow$를, 결론에서 $\Rightarrow$를 각각 쓴다. 한쪽만 기억하면 증명의 절반에서 인용할 근거가 없어진다. - **유형 2 — 소속과 상등의 혼동.** "$x\,R\,y$이면 $y \in [x]$"라고 적는다. 이 문장도 참이다 — 동치류의 정의를 그대로 읽은 것이다. 다만 핵심 정리가 주장하는 것은 원소의 **소속**이 아니라 두 집합의 **상등** $[x] = [y]$이고, 한 방이 이름을 여러 개 갖는다는 사실은 상등으로만 표현된다. - **유형 3 — 전제 누락.** "$x\,R\,y \iff [x] = [y]$"만 적고 "$R$이 동치관계일 때"를 빠뜨린다. 결론의 진술은 정확하다. 빠진 것은 무대다 — 37주차 문제 13에서 $\le$로 확인한 대로 동치관계가 아니면 이 문장은 무너진다. ## 개념 — 동치류들의 집합에 연산 얹기 ### 1 "5개짜리 산술 세계"를 만들려다 막히는 자리 20주차에서 $\bmod n$ 계산을 배웠지만 그 계산이 벌어지는 무대를 집합으로 만든 적은 없다. 지금까지의 도구 — 정수와 합동 — 만으로 그 무대를 만들어 보자. :::{admonition} 시도 — 나머지 다섯 개를 원소로 삼기 :class: quotebox $S = \{0, 1, 2, 3, 4\}$로 두고, $S$ 위의 연산 $\oplus$를 "정수로 더한 뒤 5로 나눈 나머지"로 정한다. 그러면 $3 \oplus 4 = 2$, $2 \oplus 2 = 4$이다. ::: $\oplus$는 "동그라미 플러스"로 읽고, 이 절에서만 쓰는 임시 기호다. 계산은 된다. 막히는 곳은 그다음이다. $\oplus$는 방금 새로 만든 기호이므로, 20주차에서 증명해 둔 (C1)~(C5)가 $\oplus$에 대해서는 한 글자도 말해 주지 않는다. 게다가 $\oplus$는 두 단계 절차("정수로 더한다 $\to$ 나머지를 취한다")라서 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$조차 $\mathbb{Z}$의 결합법칙에서 곧바로 나오지 않는다. :::{container} quotebox **확인 1.** $S$ 위에서 $3 \oplus 4 = 2$라고 적었다. 같은 내용을 정수의 등식 "$3 + 4 = 2$"로 적으면 무엇이 문제인가? ::: :::{admonition} 답 :class: quotebox dropdown $3 + 4 = 2$는 정수에 대한 거짓 문장이다. 참인 문장은 $3 + 4 \equiv 2 \pmod 5$ 이다. 즉 새 세계의 등호는 합동에서 온 것인데, $S$의 원소를 정수로 잡으면 그 사정이 표기에 남지 않는다 — 매번 바깥에서 설명해야 하는 세계는 아직 집합으로 만들어진 것이 아니다. ::: 필요한 것은 "$3+4$와 $2$가 처음부터 같은 대상인 세계"다. 37주차의 동치류가 정확히 그 일을 한다 — 합동인 정수들을 하나로 묶어 한 대상으로 만든다. ### 2 동치류를 원소로 — 구체 사례부터 $n = 4$로 두고 표를 채워 보자. 각 정수 $m$의 동치류 $[m]$이 $[0], [1], [2], [3]$ 중 어느 것과 같은지 판정하고 근거를 적는다. | **$m$** | **$[m]$의 원소 예시** | **$[0], [1], [2], [3]$ 중 어느 것과 같은가** | **근거** | |---|---|---|---| | $0$ | $\dots, -8, -4, 0, 4, 8, \dots$ | $[0]$ | $0 \equiv 0 \pmod 4$ | | $5$ | $\dots, -3, 1, 5, 9, \dots$ | $\underline{\quad(1)\quad}$ | $5 \equiv 1 \pmod 4$ | | $7$ | $\dots, -1, 3, 7, 11, \dots$ | $\underline{\quad(2)\quad}$ | $\underline{\quad(3)\quad}$ | | $-2$ | $\dots, -6, -2, 2, 6, \dots$ | $\underline{\quad(4)\quad}$ | $\underline{\quad(5)\quad}$ | | $100$ | $\dots, 92, 96, 100, \dots$ | $\underline{\quad(6)\quad}$ | $\underline{\quad(7)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(7)을 채우고, $\equiv \pmod 4$의 서로 다른 동치류가 몇 개인지 답해 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $[1]$ (2) $[3]$ (3) $7 \equiv 3 \pmod 4$ (4) $[2]$ (5) $-2 \equiv 2 \pmod 4$ (6) $[0]$ (7) $100 \equiv 0 \pmod 4$ 서로 다른 동치류는 네 개다. 어떤 정수를 가져와도 네 개 중 하나로 떨어지고 그 네 개는 서로 다르다. 이 "네 개"가 새 세계의 원소 전부다. ::: 이 관찰에 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 표에서 이미 한 일에 이름을 붙였을 뿐이다. ### 정의 38.1 — $\mathbb{Z}_n$ (integers modulo n) [백지 암기 대상] :::{container} quotebox 자연수 $n$에 대해, $\mathbb{Z}_n$은 $\mathbb{Z}$ 위 $\equiv \pmod n$의 동치류 전체의 집합이다: $$ \mathbb{Z}_n = \{[0], [1], [2], \dots, [n-1]\}, \qquad |\mathbb{Z}_n| = n $$ ::: 기호 $\mathbb{Z}_n$은 "제트 엔"으로 읽고 아래 첨자 $n$은 법(modulus)이다. $[a]$는 "$a$의 동치류"로 읽는다. 동치류를 가리키는 짧은 말로 "방"도 함께 쓴다(37주차의 약칭이고 이번 주 문제 진술에도 등장한다). **$|\mathbb{Z}_n| = n$의 근거.** ① **목록이 전부를 덮는다.** 나눗셈 정리에 의해 임의의 정수 $a$에 대해 $a = nq + r$, $0 \le r < n$인 정수 $q, r$이 존재하고 (33주차 예제 2.2) 유일하다(33주차 문제 10). $a - r = nq$이므로 $a \equiv r \pmod n$, 핵심 정리에 의해 $[a] = [r]$이다. ② **목록에 중복이 없다.** $0 \le r < r' < n$이면 $0 < r' - r < n$이라 $r' - r$은 $n$의 배수가 아니므로 $r \not\equiv r' \pmod n$, 핵심 정리에 의해 $[r] \neq [r']$이다(25주차 예제 2.2가 "합동 $\iff$ 같은 나머지"로 이 논증을 완성해 두었다). 두 사실을 합치면 원소가 정확히 $n$개다. ### 3 정의 38.1 해부 — 조각마다 하는 일 | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "$\equiv \pmod n$의" | 같음의 기준 선언 | $n$이 바뀌면 세계가 통째로 바뀐다 — $\mathbb{Z}_5$와 $\mathbb{Z}_6$은 별개의 무대다 | | "동치류" | 원소의 정체 | 원소는 수가 아니라 무한집합이다 — $[2] \in \mathbb{Z}_6$은 $\{\dots, -4, 2, 8, \dots\}$ | | "전체의 집합" | 모으기 | 무한집합들을 새 세계의 점으로 취급한다 | | "$\{[0], \dots, [n-1]\}$" | 대표원 목록 | 계산할 때 손에 쥐는 유한한 이름표 | | "$\lvert \mathbb{Z}_n \rvert = n$" | 크기 — 정의가 선언한 것이 아니라 §1의 두 조각(덮음 / 중복 없음)으로 증명되는 따름 사실 | 원소가 유한하므로 전수 확인이 완결된 논증이 된다 | **조각 삭제 실험.** 둘째 조각의 "동치류"를 "나머지"로 바꿔 $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$이라 적으면 §1.1의 $S$로 되돌아간다. $[3] + [4] = [2]$ 자리에 거짓 문장 $3 + 4 = 2$가 남고 (C1)~(C5)를 인용할 통로가 사라진다 — 이 조각 하나가 이번 주 전체의 근거를 연다. :::{container} quotebox **확인 3.** $\mathbb{Z}_6$의 원소 $[2]$는 수인가 집합인가. 그리고 $[2] = [8]$이 참인 이유를 근거와 함께 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 집합이다: $[2] = \{\dots, -10, -4, 2, 8, 14, \dots\}$로 원소가 무한히 많다. $8 - 2 = 6$이므로 $2 \equiv 8 \pmod 6$이고, 핵심 정리(37주차)에 의해 $[2] = [8]$이다. 한 방이 이름을 여러 개 갖는다는 이 사실이 §1.4부터 문제가 된다. ::: ### 4 연산을 얹으려다 막히는 자리 — 겉모양이 같은 두 규칙 $\mathbb{Z}_6$ 위에 규칙을 두 개 적어 보자. 둘 다 "대표원을 골라 정수 세계에서 계산한 뒤 결과의 동치류를 답으로 삼는다"는 같은 꼴이다. :::{admonition} 겉모양이 같은 두 규칙 :class: quotebox 규칙 A: $[a] + [b] = [a + b]$ 규칙 B: $[a] \diamond [b] = [\max(a, b)]$ ::: $\diamond$는 "다이아몬드"로 읽는다 — 규칙 B를 위해 임시로 만든 기호다. 문장만 보면 둘 다 흠이 없다. 그런데 $[2] = [8]$(확인 3)을 이용해 이름을 바꿔 넣으면 결과가 갈린다. 규칙 A는 $[2] + [3] = [5]$이고 $[8] + [3] = [11]$인데 $11 - 5 = 6$이므로 $[11] = [5]$ — **같은 답**이다. 규칙 B는 $[2] \diamond [3] = [3]$이고 $[8] \diamond [3] = [8] = [2]$인데 $3 - 2 = 1$은 $6$의 배수가 아니므로 $[3] \neq [2]$ — **다른 답**이다. 규칙 B는 정의가 아니다. 같은 입력에 두 답을 주기 때문이다. 문제는 규칙을 **쓰는 방식만으로는 A와 B를 구별할 수 없다**는 데 있다 — 정의를 문장으로 적는다는 이전 주까지의 도구가 여기서 막힌다. :::{container} quotebox **확인 4.** 규칙 A의 답이 갈리지 않은 것은 우연인가. 우연이 아님을 확정하려면 무엇을 증명해야 하는가? ::: :::{admonition} 답 :class: quotebox dropdown 지금 확인한 것은 $n = 6$, 이름 한 벌뿐이므로 사례 하나다. 사례를 아무리 모아도 증명이 되지 않는다는 것은 1주차에서 확인했다. 확정하려면 "임의의 $n$과 임의의 $a, a', b, b'$에 대해 $[a] = [a']$, $[b] = [b']$이면 $[a+b] = [a'+b']$"를 증명해야 한다 — 이 문장이 예제 2.1의 명제다. ::: ### 정의 38.2 — 잘 정의됨 (well-defined) [백지 암기 대상] :::{container} quotebox 대표원을 골라 계산하는 규칙이 **잘 정의된다**는 것은, 대표원을 어떻게 바꿔 잡아도 결과가 같은 동치류가 된다는 뜻이다. 곧 $[a] = [a']$이고 $[b] = [b']$일 때, 두 대표원 벌로 계산한 결과의 동치류가 서로 같다. ::: ### 정의 38.3 — $\mathbb{Z}_n$의 덧셈과 곱셈 (addition and multiplication in $\mathbb{Z}_n$) [백지 암기 대상] :::{container} quotebox $$ [a] + [b] = [a + b], \qquad [a] \cdot [b] = [ab] $$ 두 규칙이 잘 정의됨은 예제 2.1(덧셈)과 문제 7(곱셈)에서 증명한다. ::: 정의 38.3의 좌변과 우변은 사는 차원이 다르다. 조각마다 하는 일을 갈라 보면 — | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | 좌변 $[a] + [b]$ | 동치류 두 개에 대한 연산 | 정의하려는 대상 — 집합 차원 | | 우변 $[a + b]$ | 대표원의 정수 합의 동치류 | 계산이 실제로 일어나는 자리 — 수 차원 | | 대표원 $a, b$ | 방의 이름을 하나씩 고른 것 | 선택이 개입하는 유일한 지점 — 잘 정의됨 확인이 필요한 이유 | | 등호 | 정의한다는 선언 | 잘 정의됨이 증명되기 전에는 선언에 그친다 | **조각 삭제 실험.** 잘 정의됨 확인을 빼면 규칙 A와 규칙 B가 같은 자격을 갖고, 목록에 정의가 아닌 규칙이 섞여 들어온다 — 이 확인이 곧 정의의 일부다. 같은 질문은 40주차의 함수(정의역이 동치류들의 집합일 때)에서 다시 나온다. :::{container} quotebox **확인 5.** 잘 정의됨을 증명하는 4단계 뼈대를 채워 보자. ① 이름 두 벌을 가정: $[a] = [a']$, $[b] = [b']$ ② 집합 차원 $\to$ 수 차원 번역: $\underline{\qquad}$ (근거: $\underline{\qquad}$) ③ 수 차원에서 보존: $\underline{\qquad}$ (근거: $\underline{\qquad}$) ④ 수 차원 $\to$ 집합 차원 역번역: $\underline{\qquad}$ (근거: $\underline{\qquad}$) ::: :::{admonition} 답 :class: quotebox dropdown ② $a \equiv a' \pmod n$이고 $b \equiv b' \pmod n$ — 핵심 정리(37주차). ③ $a + b \equiv a' + b' \pmod n$ — (C4) 합 보존(20주차). ④ $[a + b] = [a' + b']$ — 다시 핵심 정리. 곱셈이면 ③의 (C4)를 (C5)로 바꾸고 ④를 $[ab] = [a'b']$로 바꾸면 그만이다. 이 뼈대를 문장으로 완성한 것이 예제 2.1이다. ::: ### 5 근거 목록 갱신 — 칸은 그대로 네 개 증명에서 쓸 수 있는 것은 여전히 네 칸이다. 늘어나는 것은 칸이 아니라 내용물이다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 1~37주차의 정의 전부 + **정의 38.1(무대), 38.2(잘 정의됨), 38.3(연산)** | "$[a] + [b]$"를 "$[a+b]$"로 푸는 것이 정의 38.3의 인용이다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | "$q_1 + q_2$는 정수이므로"를 별도 설명 없이 쓴다 | | ③ 등식의 성질 | 대입 / 전개 / 묶기 / 양변에 같은 것을 연산 | 양변에 같은 동치류를 곱한다 | | ④ 이미 증명한 명제 | 37주차 핵심 정리, 20주차 (C1)~(C5), 33주차 나눗셈 정리, 25주차 예제 2.2 + **이번 주의 예제 2.1과 문제 7** | "(C4)에 의해", "핵심 정리에 의해"가 이번 주 답안의 표준 문구다 | 목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 **나누기는 목록 어디에도 없다** — 정의 38.3이 준 것은 덧셈과 곱셈 두 개뿐이고, $\mathbb{Z}_n$에 나눗셈 연산은 정의된 적이 없다. 예제 2.3과 문제 18이 이 지점을 정면으로 다룬다. :::{container} quotebox **확인 6.** 다음 세 문장은 각각 허용되는가. 허용되면 몇 번 근거인가. (가) "(C5)에 의해 $ab \equiv a'b' \pmod n$이다." (나) "$q_1 + q_2$는 정수이므로" (다) "$\mathbb{Z}_6$에서 양변을 $[2]$로 나누면 $[x] = [3]$이다." ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ④. (C5)는 20주차에서 증명이 끝났으므로 이름으로 인용할 수 있다. (나) 허용 — 근거 ② 닫힘성. (다) 불허 — 나눗셈은 정의되어 있지 않다. 같은 뜻을 적으려면 $[2]$의 곱셈 역원이 존재함을 먼저 보인 뒤 "양변에 그 역원을 곱한다"(근거 ③)로 바꿔야 하는데, $\mathbb{Z}_6$에서는 그 역원이 없으므로(문제 8(b)) 바꿔 쓴 뒤에도 성립하지 않는다. ::: 정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장만 외우지 말고 §1.3의 조각별 이유와 함께 외운다.