38주차 — \mathbb{Z}_n: 나머지들의 산술 세계

내용

38주차 — \(\mathbb{Z}_n\): 나머지들의 산술 세계#

이 주의 길잡이

핵심 문장: 대표원으로 계산하는 규칙은, 대표원을 바꿔 잡아도 같은 동치류가 나올 때에만 정의가 된다.

이 주의 위치: 50주 과정의 38주차. 8부(관계)의 마지막 학습 주다 — 39주차는 8부 전체를 닫는 백지 시험이다. 37주차의 동치류가 원소가 되고, 20주차의 (C4)(C5)가 그 위에 연산을 얹을 자격을 준다.

원서 대응: BoP(Book of Proof) 11.4 (Integers Modulo n) — 병행자 참고용이고, 이 교재는 원서 없이 읽을 수 있다.

이번 주 목표#

\(\mathbb{Z}_n\)의 정의와 \(|\mathbb{Z}_n| = n\)의 근거(나눗셈 정리의 존재\(\cdot\)유일)를 백지에 쓸 수 있다.
연산 \([a] + [b] = [a+b]\)와 \([a][b] = [ab]\)의 잘 정의됨을 (C4)(C5)를 인용해 증명할 수 있다.
\(\mathbb{Z}_4\)\(\cdot\)\(\mathbb{Z}_5\)\(\cdot\)\(\mathbb{Z}_6\)의 연산표를 작성하고 영인수\(\cdot\)역원\(\cdot\)소거 실패를 판정할 수 있다.
“\(\mathbb{Z}_n\)에서 나누기는 근거 목록에 없다”를 반례로 설명할 수 있다.

본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

준비 운동 (37주차 복습)#

핵심 정리(\(x\,R\,y \iff [x] = [y]\))를 진술하시오.
\(\mathbb{Z}\) 위 \(\equiv \pmod 4\)의 동치류를 모두 나열하시오 (각각 원소 4개씩 예시).
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\) 계산을 배웠지만 그 계산이 벌어지는 무대를 집합으로 만든 적은 없다. 지금까지의 도구 — 정수와 합동 — 만으로 그 무대를 만들어 보자.

시도 — 나머지 다섯 개를 원소로 삼기

\(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}\)의 결합법칙에서 곧바로 나오지 않는다.

확인 1. \(S\) 위에서 \(3 \oplus 4 = 2\)라고 적었다. 같은 내용을 정수의 등식

“\(3 + 4 = 2\)”로 적으면 무엇이 문제인가?

답

\(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}\)

확인 2. 빈칸 (1)~(7)을 채우고, \(\equiv \pmod 4\)의 서로 다른 동치류가 몇

개인지 답해 보자.

답

(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) [백지 암기 대상]#

자연수 \(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)를 인용할 통로가 사라진다 — 이 조각 하나가 이번 주 전체의 근거를 연다.

확인 3. \(\mathbb{Z}_6\)의 원소 \([2]\)는 수인가 집합인가. 그리고 \([2] = [8]\)이

참인 이유를 근거와 함께 적어 보자.

답

집합이다: \([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\) 위에 규칙을 두 개 적어 보자. 둘 다 “대표원을 골라 정수 세계에서 계산한 뒤 결과의 동치류를 답으로 삼는다”는 같은 꼴이다.

겉모양이 같은 두 규칙

규칙 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를 구별할 수 없다는 데 있다 — 정의를 문장으로 적는다는 이전 주까지의 도구가 여기서 막힌다.

확인 4. 규칙 A의 답이 갈리지 않은 것은 우연인가. 우연이 아님을 확정하려면

무엇을 증명해야 하는가?

답

지금 확인한 것은 \(n = 6\), 이름 한 벌뿐이므로 사례 하나다. 사례를 아무리 모아도

증명이 되지 않는다는 것은 1주차에서 확인했다. 확정하려면 “임의의 \(n\)과 임의의

\(a, a', b, b'\)에 대해 \([a] = [a']\), \([b] = [b']\)이면 \([a+b] = [a'+b']\)”를

증명해야 한다 — 이 문장이 예제 2.1의 명제다.

정의 38.2 — 잘 정의됨 (well-defined) [백지 암기 대상]#

대표원을 골라 계산하는 규칙이 잘 정의된다는 것은, 대표원을 어떻게 바꿔

잡아도 결과가 같은 동치류가 된다는 뜻이다. 곧 \([a] = [a']\)이고 \([b] = [b']\)일

때, 두 대표원 벌로 계산한 결과의 동치류가 서로 같다.

정의 38.3 — \(\mathbb{Z}_n\)의 덧셈과 곱셈 (addition and multiplication in \(\mathbb{Z}_n\)) [백지 암기 대상]#

\[ [a] + [b] = [a + b], \qquad [a] \cdot [b] = [ab] \]

두 규칙이 잘 정의됨은 예제 2.1(덧셈)과 문제 7(곱셈)에서 증명한다.

정의 38.3의 좌변과 우변은 사는 차원이 다르다. 조각마다 하는 일을 갈라 보면 —

조각	하는 일	증명에서의 역할
좌변 \([a] + [b]\)	동치류 두 개에 대한 연산	정의하려는 대상 — 집합 차원
우변 \([a + b]\)	대표원의 정수 합의 동치류	계산이 실제로 일어나는 자리 — 수 차원
대표원 \(a, b\)	방의 이름을 하나씩 고른 것	선택이 개입하는 유일한 지점 — 잘 정의됨 확인이 필요한 이유
등호	정의한다는 선언	잘 정의됨이 증명되기 전에는 선언에 그친다

조각 삭제 실험. 잘 정의됨 확인을 빼면 규칙 A와 규칙 B가 같은 자격을 갖고, 목록에 정의가 아닌 규칙이 섞여 들어온다 — 이 확인이 곧 정의의 일부다. 같은 질문은 40주차의 함수(정의역이 동치류들의 집합일 때)에서 다시 나온다.

확인 5. 잘 정의됨을 증명하는 4단계 뼈대를 채워 보자.

① 이름 두 벌을 가정: \([a] = [a']\), \([b] = [b']\)

② 집합 차원 \(\to\) 수 차원 번역: \(\underline{\qquad}\) (근거: \(\underline{\qquad}\))

③ 수 차원에서 보존: \(\underline{\qquad}\) (근거: \(\underline{\qquad}\))

④ 수 차원 \(\to\) 집합 차원 역번역: \(\underline{\qquad}\) (근거: \(\underline{\qquad}\))

답

② \(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이 이 지점을 정면으로 다룬다.

확인 6. 다음 세 문장은 각각 허용되는가. 허용되면 몇 번 근거인가.

(가) “(C5)에 의해 \(ab \equiv a'b' \pmod n\)이다.”

(나) “\(q_1 + q_2\)는 정수이므로”

(다) “\(\mathbb{Z}_6\)에서 양변을 \([2]\)로 나누면 \([x] = [3]\)이다.”

답

(가) 허용 — 근거 ④. (C5)는 20주차에서 증명이 끝났으므로 이름으로 인용할 수 있다.

(나) 허용 — 근거 ② 닫힘성.

(다) 불허 — 나눗셈은 정의되어 있지 않다. 같은 뜻을 적으려면 \([2]\)의 곱셈

역원이 존재함을 먼저 보인 뒤 “양변에 그 역원을 곱한다”(근거 ③)로 바꿔야 하는데,

\(\mathbb{Z}_6\)에서는 그 역원이 없으므로(문제 8(b)) 바꿔 쓴 뒤에도 성립하지 않는다.

정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장만 외우지 말고 §1.3의 조각별 이유와 함께 외운다.