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

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}\)를 만든다

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

정리는 무엇인가?

답

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

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

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

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

확인 8. 첫 문장을 완성해 보자: “\(\underline{\qquad}\)이고 \(\underline{\qquad}\)이라 가정하자.”

답

“\([a] = [a']\)이고 \([b] = [b']\)이라 가정하자.” 이 문장이 놓는 상황은 “같은 방에

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

임무다.

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

확인 9. 둘째 문장을 완성해 보자: “\(\underline{\qquad}\)에 의해 \(a \equiv \underline{\quad}\)이고 \(b \equiv \underline{\quad} \pmod n\)이다.”

답

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

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

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

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

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

답

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

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

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

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

확인 11. 마지막 문장을 완성해 보자: “다시 \(\underline{\qquad}\)에 의해 \(\underline{\qquad}\)이다. \(\blacksquare\)”

답

“다시 핵심 정리에 의해 \([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\)를 넣어 읽어 보자.

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

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

답

셋째 줄은 \(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\)로 적되, 원소가 동치류라는 것은 잊지 않는다.)

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

확인 13. 덧셈표의 \(2\)행 \(3\)열에 무엇을 적는가. 그 절차가 정당하다는 근거는

무엇인가?

답

\([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]\)를 모두 구하시오.

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

확인 14. 실수에서 하듯 양변을 \(2\)로 나눠도 되는가. 안 된다면 어떤 방법이

남는가?

답

나눌 수 없다. §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}\)

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

답

(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]\)에 대해”는 보통 문자로 처리하지만, 무대가 유한하면 전부를 확인하는 것으로도 닫힌다 — 빠뜨린 후보가 없기 때문이다.

이번 주에 확인한 것

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

인용하는 보존 정리뿐이다. 계산에서는 \(|\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\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “\(\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\)유일)를 쓰시오.

힌트

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

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

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

힌트

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

“\(5 + 4 = 9\), \(9 \equiv 2 \pmod 7\)”처럼 계산과 축소를 각각 적는다.

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

힌트

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

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

힌트

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

칸을 세는 편이 빠르다.

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

힌트

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

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

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

힌트

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

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

표준 ●●○#

이 절에서 처음 쓰는 세 가지 말 — 역원\(\cdot\)영인수\(\cdot\)소거

\(\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) 곱셈 역원을 갖는 방을 모두 찾으시오.

힌트

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

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

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

힌트

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

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

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

힌트

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

짝수인가)을 본다.

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

힌트

문제 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}\)를 구하시오.

힌트

\(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\)에서 각 방의 덧셈 역원을 표로 만드시오.

힌트

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

배수여야 한다.

도전 ●●●#

이 문제가 빌려 쓰는 사실 — 유클리드 보조정리

\(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\))를 사실로 인정하고 사용하시오)

힌트

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

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

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

힌트

훈련 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. (진단) 다음 답안의 결함을 지적하시오. 실제로 해가 있는지 전수 대입으로 확인하고, 논증의 어느 단계가 무효인지 짚으시오.

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

힌트

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

전수 대입, 뒤쪽은 “나누기는 근거 목록에 없다”(§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주차에서 함수의 정의역이 동치류들의 집합일 때 같은 확인이 함수 자격 심사로 다시 나온다. 이번 주의 네 줄짜리 왕복을 손이 기억하도록 만들어 두면 그때 새로 배울 것이 없다.