# 20주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 판정과 증명을 함께 만들기 이번 주의 예제는 세 가지 일을 나눠 맡는다. 예제 2.1은 정의로 판정하는 답안을 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 한 뒤 증명을 산문으로 보며, 예제 2.3은 설계부터 혼자 해 본다. ### 예제 2.1 — 판정은 정의로 $91 \equiv 7 \pmod{12}$인가? $58 \equiv 5 \pmod 9$인가? **설계 — 쓰기 전에 정하는 두 가지.** 판정 문제에도 출발점과 도착점이 있다. 출발점은 주어진 세 수이고, 도착점은 "정의가 요구하는 등식이 있는가"라는 물음이다. 물음을 정의로 번역해 표에 먼저 적는다. | | **주어진 것 (출발점)** | **정의로 번역한 물음 (도착점)** | |---|---|---| | 첫째 | $a = 91$, $b = 7$, $n = 12$ | $12 \mid (91 - 7)$인가, 곧 $84 = 12 \times (\text{정수})$인가 | | 둘째 | $a = 58$, $b = 5$, $n = 9$ | $\underline{\qquad(?)\qquad}$ | :::{container} quotebox **확인 12.** 둘째 행의 빈칸을 채워 보자. 정의 20.1을 그대로 적용하면 무엇을 확인해야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown $9 \mid (58 - 5)$인가, 곧 $53 = 9 \times (\text{정수})$인가. 판정에서 할 일은 언제나 이 하나다 — 차를 구하고, 그 차가 법의 배수인지 본다. 두 수의 크기나 부호는 묻지 않는다. ::: **1단계 — 차를 구한다.** 정의가 요구하는 것은 $a - b$이므로 뺄셈부터 한다. :::{container} quotebox **확인 13.** 두 물음의 차 $a - b$를 각각 구하고, 그 차를 법의 곱셈 등식으로 적어 보자. "$84 = 12 \times \underline{\quad}$", "$53 = 9 \times \underline{\quad} + \underline{\quad}$". ::: :::{admonition} 답 :class: quotebox dropdown $91 - 7 = 84$이고 $84 = 12 \times 7$ — 곱하는 수 7이 정수이므로 $12 \mid 84$이다. $58 - 5 = 53$이고 $53 = 9 \times 5 + 8$ — 9의 배수는 45와 54로 53을 건너뛰므로 $53 = 9c$인 정수 $c$는 없고, 따라서 $9 \nmid 53$이다. ::: **2단계 — 판정을 문장으로 적는다.** 계산 결과만 적으면 답안이 되지 않는다. 글쓰기 규칙 1조와 6조대로, 근거를 앞에 두고 판정을 문장으로 닫는다. :::{container} quotebox **확인 14.** 둘째 물음의 결론 문장을 완성해 보자. "따라서 $\underline{\qquad}$이므로 $58 \underline{\quad} 5 \pmod 9$이다." ::: :::{admonition} 답 :class: quotebox dropdown "따라서 $9 \nmid 53$이므로 $58 \not\equiv 5 \pmod 9$이다." 부정 판정에서는 $\nmid$와 $\not\equiv$를 짝지어 쓴다. "합동이 아니다"까지 적어야 판정이 닫힌다 — 차를 구해 놓고 멈추면 물음에 답하지 않은 것이다. ::: **완성본.** 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 정의 20.1에 의해, $91 \equiv 7 \pmod{12}$은 $12 \mid (91 - 7)$과 같은 뜻이다. | 물음을 정의로 번역하는 첫 줄. 판정의 기준을 명시해 두면 이후 계산의 목표가 고정된다. | | $91 - 7 = 84$이고 $84 = 12 \times 7$이며 $7$은 정수이므로 $12 \mid 84$이다. | 차를 구하고 곱 등식으로 적는다(근거 ①). 나눗셈 "$84 \div 12 = 7$"은 연습장의 계산이고, 답안에는 곱 등식을 적는다. | | 따라서 $91 \equiv 7 \pmod{12}$이다. | 역번역으로 판정을 닫는다. | | 마찬가지로 $58 \equiv 5 \pmod 9$은 $9 \mid (58 - 5)$와 같은 뜻인데, $58 - 5 = 53$이고 $53 = 9c$인 정수 $c$는 존재하지 않는다($9 \times 5 = 45$, $9 \times 6 = 54$). | 부정 판정의 근거는 "정수가 없다"를 보이는 것이다. 이웃한 두 배수로 끼워 넣으면 존재하지 않음이 확인된다. | | 따라서 $9 \nmid 53$이므로 $58 \not\equiv 5 \pmod 9$이다. | 부정 판정도 문장으로 닫는다. | **검산.** 나머지 관점으로 교차 확인해 보면 — $91 = 12 \times 7 + 7$과 $7 = 12 \times 0 + 7$은 나머지가 둘 다 7로 같고, $58 = 9 \times 6 + 4$와 $5 = 9 \times 0 + 5$는 나머지가 4와 5로 다르다. 두 판정이 §1.2 표와 같은 방식으로 일치한다. 검산은 연습장에서 하고, 답안에는 위 다섯 줄만 적는다. ### 예제 2.2 — 합 보존 (C4)의 증명 **명제.** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이면 $a + c \equiv b + d \pmod n$이다. 이번에는 설계만 함께 하고, 증명은 완성된 형태로 본다. 먼저 번역표를 채운다. | | **말** | **정의로 번역** | |---|---|---| | 가정 (출발점) | $a \equiv b$, $c \equiv d \pmod n$ | $n \mid (a - b)$, $n \mid (c - d)$ | | 목표 (도착점) | $a + c \equiv b + d \pmod n$ | $n \mid \big(\underline{\qquad(?)\qquad}\big)$ | :::{container} quotebox **확인 15.** 목표 칸의 빈칸을 채워 보자. 결론을 정의 20.1로 번역하면 어떤 수가 $n$의 배수여야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown $n \mid \big((a + c) - (b + d)\big)$. 결론에 등장하는 두 수가 $a+c$와 $b+d$이므로, 정의가 요구하는 것은 그 둘의 차다. 출발점은 배수 두 개이고 도착점도 배수 하나 — 남은 일은 도착점의 그 차를 출발점의 두 배수로 만들어 내는 것이다. ::: :::{container} quotebox **확인 16.** $(a+c) - (b+d)$를 괄호를 풀고 다시 묶어, 가정이 붙잡고 있는 두 덩어리 $(a-b)$와 $(c-d)$가 드러나게 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown $(a+c) - (b+d) = a + c - b - d = (a - b) + (c - d)$. 덧셈의 교환$\cdot$결합법칙만 썼고 새로 도입한 것은 없다(근거 ③). 그런데 이 꼴이 나오는 순간 2주차 예제 2.2("배수 두 개의 합은 배수")가 그대로 적용된다 — 증명이 끝난 것이다. ::: **증명.** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이라 가정하자. 정의 20.1에 의해 $n \mid (a - b)$이고 $n \mid (c - d)$이다. 2주차 예제 2.2(배수의 합은 배수)에 의해 $$ n \mid \big((a - b) + (c - d)\big) $$ 이고, 덧셈의 교환$\cdot$결합법칙으로 $(a-b) + (c-d) = (a+c) - (b+d)$이므로 $n \mid \big((a+c) - (b+d)\big)$이다. 따라서 정의 20.1에 의해 $a + c \equiv b + d \pmod n$이다. $\blacksquare$ 네 문장의 구조는 **번역 $\to$ 조합 $\to$ 역번역**이다. 첫 문장이 가정을 선언하고, 둘째 문장이 정의로 번역하고, 셋째 문장이 이미 증명한 정리로 조합하고, 넷째 문장이 정의로 되돌린다. 이번 주 증명의 대부분이 이 네 문장이다. **곱 보존 (C5)는 조합 단계에 변형 하나가 더 필요하다.** 같은 설계를 (C5)에 적용하면 도착점은 $n \mid (ac - bd)$인데, $ac - bd$ 안에는 $(a-b)$도 $(c-d)$도 보이지 않는다. 가정이 붙잡고 있는 덩어리가 식에 드러나 있지 않은 것이다. :::{container} quotebox **확인 17.** $ac - bd$의 가운데에 $-bc + bc$를 삽입해 보자. 값은 변하지 않는데 식이 어떻게 쪼개지는가. ::: :::{admonition} 답 :class: quotebox dropdown $ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d)$. $-bc + bc = 0$이므로 값은 그대로이고, 대신 가정이 붙잡을 수 있는 두 덩어리 $(a-b)$와 $(c-d)$가 각각 인수로 드러난다. 이 "빼고 더하기"는 17주차 문제 16(역삼각부등식에서 $x = (x-y) + y$로 쪼갠 자리)에 이어 두 번째 등장이고, 목표에 필요한 덩어리가 식에 없을 때 그 덩어리가 나타나도록 항을 쪼개는 표준 수법이다. ::: 그다음은 2주차의 부품 두 개로 끝난다. $n \mid (a-b)$이므로 $n \mid c(a-b)$이고 $n \mid (c-d)$이므로 $n \mid b(c-d)$이며(2주차 훈련 1: 배수에 정수를 곱해도 배수), 두 배수의 합도 배수이므로(2주차 예제 2.2) $n \mid (ac - bd)$이다. 완전한 증명문을 쓰는 것은 문제 17이다. ### 예제 2.3 — 요일 계산 오늘이 수요일이면 100일 후는 무슨 요일인가? 이번에는 설계부터 혼자 한다. 무엇을 법으로 잡을지, 무엇의 나머지를 구할지 연필로 먼저 적은 뒤 아래 산문과 대조한다. **풀이.** 요일은 7일마다 되풀이되므로 요일 계산은 법 7의 세계다. $100$을 7로 나누면 $100 = 7 \times 14 + 2$이고, $100 - 2 = 98 = 7 \times 14$이므로 $7 \mid (100 - 2)$, 곧 $100 \equiv 2 \pmod 7$이다. 따라서 100일 후의 요일은 2일 후의 요일과 같다. 수요일에서 이틀 뒤는 금요일이므로, 답은 금요일이다. 이 풀이에서 실제로 한 일은 번역 하나다 — "요일이 7일마다 반복된다"를 "법 7"로 옮기고, 큰 수 100을 법 7에서 작은 수 2로 갈아 끼웠다. 달력 문제와 주기 문제는 대개 이렇게 적절한 법의 합동으로 번역된다. 법을 무엇으로 잡을지가 유일한 설계 판단이고, 나머지는 §1.6의 갈아 끼우기다. ### 관찰 — 같은 뼈대 예제 2.2, 문제 17(곱 보존), 훈련 2(추이성)는 소재가 다르지만 뼈대가 같다. 아래 표의 빈칸을 채워 그 뼈대를 확인해 보자. | **단계** | **예제 2.2 (합 보존)** | **곱 보존 (C5)** | **추이 (C3)** | |---|---|---|---| | ① 가정 선언 | $a \equiv b$, $c \equiv d$라 가정 | $a \equiv b$, $c \equiv d$라 가정 | $a \equiv b$, $b \equiv c$라 가정 | | ② 정의로 번역 | $n \mid (a-b)$, $n \mid (c-d)$ | $n \mid (a-b)$, $n \mid (c-d)$ | $n \mid (a-b)$, $n \mid \underline{\quad(1)\quad}$ | | ③ 목표의 차를 아는 배수들로 조합 | $(a+c)-(b+d) = (a-b)+(c-d)$ | $ac - bd = \underline{\qquad(2)\qquad}$ | $a - c = \underline{\qquad(3)\qquad}$ | | ④ 정의로 역번역 | $a + c \equiv b + d$ | $ac \equiv bd$ | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 18.** 빈칸 (1)~(4)를 채우고, ③ 단계의 세 식에 공통된 일이 무엇인지 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $b - c$ (2) $c(a-b) + b(c-d)$ (3) $(a-b) + (b-c)$ (4) $a \equiv c \pmod n$. ③ 단계의 공통점: **목표가 요구하는 차를, 가정이 이미 배수임을 보장하는 덩어리들의 합(또는 정수배의 합)으로 다시 쓴다.** 세 경우 모두 이 한 줄이 증명의 전부이고, 나머지 세 단계는 번역과 역번역이다. ::: :::{admonition} 이번 주에 확인한 것 :class: quotebox 합동 증명은 **번역 $\to$ 조합 $\to$ 역번역**의 세 박자다. 번역과 역번역은 정의 20.1이 기계적으로 처리하므로, 생각할 곳은 조합 한 곳뿐이다. 조합에서 쓰는 부품은 2주차의 세 정리(배수의 합, 배수에 정수 곱하기, 부호 뒤집기)이고, 덩어리가 식에 보이지 않을 때 꺼내는 수법이 "빼고 더하기"다. ::: ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** $a \equiv b \pmod n$이면 임의의 정수 $c$에 대해 $a - c \equiv b - c \pmod n$이다. **증명.** $a \equiv b \pmod n$이라 가정하고 $c$를 임의의 정수라 하자. 정의에 의해 $n \mid \underline{\quad(1)\quad}$이다. 그런데 괄호를 풀어 정리하면 $$ (a - c) - (b - c) = \underline{\quad(2)\quad} $$ 이므로 $n \mid \big((a-c) - (b-c)\big)$이다. 따라서 정의에 의해 $\underline{\quad(3)\quad}$이다. $\blacksquare$ ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장도 빈칸이다. **명제 ((C3), 추이).** $a \equiv b \pmod n$이고 $b \equiv c \pmod n$이면 $a \equiv c \pmod n$이다. **증명.** $a \equiv b$이고 $b \equiv c \pmod n$이라 $\underline{\quad(1)\quad}$하자. $\underline{\quad(2)\quad}$에 의해 $n \mid (a - b)$이고 $n \mid \underline{\quad(3)\quad}$이다. $\underline{\quad(4)\quad}$에 의해 두 배수의 합도 배수이므로 $$ n \mid \big((a-b) + (b-c)\big), \quad\text{즉}\quad n \mid \underline{\quad(5)\quad} $$ 이다. 따라서 정의에 의해 $\underline{\quad(6)\quad}$이다. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 세 박자의 각 칸을 통째로 채운다. **명제.** $a \equiv b \pmod n$이고 $n \mid c$이면 $a + c \equiv b \pmod n$이다. **증명의 뼈대.** - ① 가정 선언: $\underline{\quad(1)\quad}$ - ② 정의로 번역: $\underline{\quad(2)\quad}$ - ③ 목표의 차를 아는 배수들로 조합하고 역번역: $\underline{\quad(3)\quad}$ (도착점은 $n \mid \big((a+c) - b\big)$이다. 그 차를 어떤 두 덩어리의 합으로 다시 쓸지가 관건이고, 이 명제는 (C4)에 $c \equiv 0$을 넣은 경우에 해당한다 — 해설의 주석과 대조해 볼 자리다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 합동 증명의 첫 줄은 언제나 정의 번역 "$n \mid (\cdot)$"이다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "$17 \equiv 5 \pmod 6$은 참(나머지가 같으니까)"은 0점이고, "$17 - 5 = 12 = 6 \times 2$이므로 $6 \mid 12$, 정의에 의해 참"이 만점이다. 증명 문항에서는 여기에 두 가지가 더 걸린다 — 정의 번역이 첫 줄에 있는가, 인용한 정리((C4) 등)가 그 시점에 이미 증명된 것인가. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** 참$\cdot$거짓을 정의($n \mid (a-b)$ 확인)로 판정하시오. (a) $17 \equiv 5 \pmod 6$ (b) $8 \equiv -1 \pmod 3$ (c) $21 \equiv 7 \pmod 8$ (d) $-3 \equiv 7 \pmod 5$ (e) $100 \equiv 2 \pmod 7$ :::{admonition} 힌트 :class: quotebox dropdown 각 항목에서 할 일은 둘뿐이다 — 차 $a - b$를 구하고, 그 차가 법의 배수인지 곱 등식으로 확인한다. 음수 차가 나와도 그대로 진행한다: $-10 = 5 \times (-2)$처럼 곱하는 수가 정수이기만 하면 배수다. ::: **2.** "$a \equiv b \pmod n$"을 (a) $\mid$ 기호로, (b) $\exists$ 기호로 번역하시오. 그리고 (c) "두 정수 $a, b$는 10으로 나눈 나머지(일의 자리)가 같다"를 합동식으로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown (a)는 정의 20.1을 그대로 옮기면 되고, (b)는 거기에 2주차 정의 2.1을 한 겹 더 푼다. (c)는 §1.6에서 "일의 자리는 법 10"이라 한 것을 기호로 옮기는 자리다. ::: **3.** 다음 수는 mod 5에서 $0, 1, 2, 3, 4$ 중 어느 것과 합동인가? $17$, $23$, $-4$, $40$ :::{admonition} 힌트 :class: quotebox dropdown 각 수에서 5의 배수를 더하거나 빼서 $0$ 이상 $5$ 미만으로 옮긴다. 옮긴 뒤에는 차가 5의 배수인지 곱 등식으로 확인한다. 음수 $-4$는 5를 더해 본다. ::: **4.** (C1) 반사성: 모든 정수 $a$에 대해 $a \equiv a \pmod n$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 정의가 요구하는 것은 $n \mid (a - a)$이다. $a - a$는 무엇이고, 그 수가 $n$의 배수인지는 2주차 문제 2(a)에서 $7 \mid 0$으로 판정한 것과 같은 계산이다 — 일반의 $n \mid 0$은 여기서 $0 = n \times 0$으로 직접 확인한다. ::: **5.** (C2) 대칭성: $a \equiv b \pmod n$이면 $b \equiv a \pmod n$임을 증명하시오. (힌트: 2주차 문제 8) :::{admonition} 힌트 :class: quotebox dropdown 가정이 주는 것은 $n \mid (a-b)$이고 목표가 요구하는 것은 $n \mid (b-a)$이다. 두 수는 부호만 다르다 — $b - a = -(a-b)$이고, 배수의 부호를 뒤집어도 배수라는 것이 2주차 문제 8이다. ::: **6.** "$n$이 홀수 $\Longleftrightarrow$ $n \equiv 1 \pmod 2$"를 두 방향으로 설명하시오 (정의 대조). :::{admonition} 힌트 :class: quotebox dropdown 양방향 모두 정의 번역이다. $n \equiv 1 \pmod 2$는 $2 \mid (n-1)$이고, 이를 한 겹 더 풀면 $n - 1 = 2k$인 정수 $k$가 존재한다 — 이 등식을 $n$에 대해 정리하면 홀수의 정의(정의 1.2)와 나란히 놓인다. ::: ### 표준 ●●○ **7.** (C3) 추이성을 백지에서 증명하시오 (빈칸 훈련의 완성본). **8.** (C4) 합 보존을 백지에서 증명하시오 (예제 2.2 재현). **9.** $a \equiv b \pmod n$이면 다음이 성립함을 각각 증명하시오. (a) $a + c \equiv b + c \pmod n$ (임의의 정수 $c$) (b) $ka \equiv kb \pmod n$ (임의의 정수 $k$) :::{admonition} 힌트 :class: quotebox dropdown (a)는 두 가지 길이 있다 — 정의로 직접 계산하거나, (C4)에 $c \equiv c$(반사성)를 끼워 넣는다. 두 번째 길은 (C1)이 장식이 아니라 부품이라는 것을 보여 준다. (b)는 $ka - kb = k(a-b)$로 묶고 2주차 훈련 1을 인용한다. ::: **10.** $a \equiv b \pmod n$이면 $a^2 \equiv b^2 \pmod n$임을 (C5)를 인용해 두 줄로 증명하시오. **11.** $7^{42}$의 일의 자리를 구하시오 (예제 2.3의 방법; $7^k$의 mod 10 주기를 먼저 찾을 것). :::{admonition} 힌트 :class: quotebox dropdown §1.6의 $3^{100}$과 같은 절차다. $7^1, 7^2, 7^3, 7^4$를 법 10에서 줄여 1이 나오는 지수를 찾고, 42를 그 주기로 나눈 나머지로 위치를 정한다. ::: **12.** 오늘이 화요일이면 365일 후는 무슨 요일인가? ($365$를 7로 나눈 나머지부터) **13.** 정수 $x$가 $2 \mid x$이고 $3 \mid x$이면 $6 \mid x$임을 증명하시오. (힌트: $x = 3k$로 쓴 뒤, $3k$가 짝수라는 사실에서 $k$가 짝수임을 끌어내라 — "홀수 $\times$ 홀수 = 홀수"(1주차 문제 8)의 대우가 열쇠. 5주차 문제 9의 빚 청산) :::{admonition} 이 문제가 빌려 쓰는 사실 — 대우를 부품으로 쓰기 :class: quotebox 문제의 힌트가 가리키는 사실은 "$3k$가 짝수이면 $k$는 짝수이다"이다. 이것은 1주차 문제 8("홀수와 홀수의 곱은 홀수")의 대우("곱이 짝수이면 두 인수 중 적어도 하나가 짝수이다")를 이 상황에 적용한 것이다 — 3은 홀수이므로 짝수인 쪽은 $k$일 수밖에 없다. 같은 말을 뒤집으면, $k$까지 홀수라면 곱 $3k$가 홀수가 되어 가정과 어긋난다. 19주차에서 대우가 원명제와 동치임을 확인했으므로, 이미 증명한 명제의 대우는 따로 증명하지 않고 근거 ④로 인용할 수 있다. 답안에서는 대우를 인용하거나, 힌트대로 "만약 $k$가 홀수라면 …이 되어 모순이므로 $k$는 짝수다"로 적어도 된다. ::: **14.** "$n^2 + 1 \equiv 0 \pmod 4$인 정수 $n$은 존재하지 않는다"를 증명하시오. (힌트: 17주차 문제 9 — $n^2$은 mod 4에서 0 또는 1) :::{admonition} 힌트 :class: quotebox dropdown 존재하지 않음을 보이는 방법은 가능한 값을 전부 훑는 것이다. 17주차 문제 9가 $n^2$의 후보를 두 개로 줄여 주므로, 각 후보에 (C4)로 1을 더해 $n^2+1$의 후보를 만들고, 그 목록에 0이 없음을 확인한다. ::: ### 도전 ●●● **15.** (9의 배수 판정법) 세 자리 자연수 $N = 100a + 10b + c$에 대해 $$ N \equiv a + b + c \pmod 9 $$ 임을 증명하시오. (힌트: $10 \equiv 1 \pmod 9$에서 (C5)로 $100 \equiv 1$, 그다음 (C4)$\cdot$문제 9(b)로 조립) 그리고 이것이 왜 "자릿수 합이 9의 배수 $\Longleftrightarrow$ 원래 수가 9의 배수"라는 판정법이 되는지 한 문장으로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 출발점은 $10 - 1 = 9$라는 사실 하나다. 여기서 $10 \equiv 1 \pmod 9$이 나오고, (C5)를 $10 \equiv 1$과 $10 \equiv 1$에 적용하면 $100 \equiv 1$이 나온다. 그다음 문제 9(b)로 계수 $a, b$를 곱해 붙이고, (C4)로 세 조각을 더한다. 마지막 문장은 $9 \mid \big(N - (a+b+c)\big)$로 되돌려 놓고, 2주차 예제 2.2(배수의 합)와 2주차 문제 7(배수의 차)로 양방향을 잇는 자리다. ::: **16.** 친구가 $437 \times 254 = 110{,}898$이라고 계산했다. 곱셈을 다시 하지 않고, mod 9 검산(문제 15의 원리)으로 이 계산이 틀렸음을 보이시오. :::{admonition} 힌트 :class: quotebox dropdown 좌변의 두 세 자리 수를 각각 자릿수 합으로 법 9에서 줄이고(문제 15), (C5)로 두 값을 곱해 줄인다. 우변은 세 자리가 아니므로 문제 15가 그대로 닿지 않는다 — 9로 나누어떨어지는지 정의로 직접 확인한다. 두 값이 다르면 등식이 성립할 수 없다. ::: **17.** (C5) 곱 보존을 백지에서 증명하시오 — "빼고 더하기" 다리 놓기 포함. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2의 확인 17에서 만든 항등식 $ac - bd = c(a-b) + b(c-d)$가 몸통이다. 그 앞뒤로 정의 번역과 역번역을 붙이고, 두 덩어리가 각각 배수임을 2주차 훈련 1로, 합이 배수임을 2주차 예제 2.2로 근거 붙인다. ::: **18.** 17주차 문제 15("홀수의 제곱은 $8m+1$ 꼴")를 합동 언어로 재진술하고, 그것을 이용해 "$a, b$가 홀수이면 $a^2 + b^2 \equiv 2 \pmod 8$"을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 재진술은 정의 번역이다 — $n^2 = 8m + 1$은 $n^2 - 1 = 8m$, 곧 $8 \mid (n^2-1)$이고 이는 $n^2 \equiv 1 \pmod 8$이다. 재진술을 끝내면 두 홀수에 각각 적용하고 (C4)로 더하기만 하면 된다. ::: **19.** (글쓰기 교정) 다음 답안을 규칙 6조에 비추어 교정하시오 (내용은 옳다고 치고, 서술만). :::{container} quotebox "$n = 2k+1$. $\Rightarrow n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1 = $ 홀수. $\blacksquare$" ::: :::{admonition} 힌트 :class: quotebox dropdown 여섯 조항을 차례로 대조하며 위반을 세어 본다. 첫 글자가 무엇인가(1조), $k$는 소개되었는가(2조), 마지막 등호의 오른쪽은 수인가(3조), $\Rightarrow$가 접속사로 쓰였는가(4조), 시작 표시가 있는가(6조). 지적만으로 끝내지 말고 교정본까지 적는 것이 이 문제의 완결이다. ::: **20.** (서술) $\equiv \pmod n$이 등호(=)와 닮은 점 세 가지(C1~C3)와 다른 점 한 가지를 쓰시오. 그리고 "같음의 조건을 느슨하게 바꾼 세계마다 새로운 산술이 생긴다"는 관점에서, mod 12의 세계(시계)에서 $8 + 7$이 무엇이 되는지 계산해 보시오. (36~38주차 예고) ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 세 박자 틀(§2 관찰)과 근거 목록(§1.8)만 펴 놓고, 예제 2.2((C4) 합 보존)를 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다. 이어서 (C5)의 다리 놓기 항등식만 다시 유도해 본다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다: - [ ] 정의 20.1을 "$n \mid (a-b)$"까지 조각 그대로 정확히 썼다. - [ ] 법 $\pmod n$ 표기를 빠뜨리면 무엇이 무너지는지 한 문장으로 설명했다(§1.3). - [ ] (C1)~(C5)를 진술하고, 각각이 2주차의 어느 정리로 증명되는지 짝지었다. - [ ] (C4)와 (C5)를 백지에 처음부터 끝까지 재현했다 — (C5)는 "빼고 더하기" 포함. - [ ] 재현한 증명에서 ① 가정 선언 ② 정의 번역 ③ 조합 ④ 역번역의 네 단계를 손가락으로 짚을 수 있다. - [ ] $3^{100}$의 일의 자리 계산(주기 찾기 $\to$ 지수 축소)을 재현했다. - [ ] 글쓰기 규칙 6조를 백지에 썼다. - [ ] 합동식의 양변을 공통 인수로 나눌 수 없다는 것을 반례와 함께 말할 수 있다(§1.5). **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 증명의 첫 줄이 나오지 않는다 | §2 관찰 — 첫 줄은 언제나 정의 번역 $n \mid (\cdot)$이다 | | 목표의 차를 어떻게 쪼갤지 모르겠다 | 예제 2.2 확인 16 — 목표의 차를 괄호를 풀고 다시 묶어 본다 | | 식에 $(a-b)$가 보이지 않는다 | 예제 2.2 확인 17 — 같은 항을 빼고 더해 덩어리를 만들어 낸다 | | 어느 정리를 인용할지 모르겠다 | §1.8 근거 목록 — 2주차 부품 셋과 (C1)~(C5)뿐이다 | | 나머지 계산이 자꾸 어긋난다 | §1.4 — 나머지는 연습장용이고 답안은 차의 배수 판정으로 쓴다 | | 큰 수의 거듭제곱에서 막힌다 | §1.6 — 1이 나오는 지수를 먼저 찾는다 | | 계산은 맞는데 답안이 감점된다 | §1.7 규칙 6조 — 여섯 조항으로 한 줄씩 대조한다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $(a - b)$ (2) $a - b$ (3) $a - c \equiv b - c \pmod n$ ※ 핵심은 (2)다. $(a-c) - (b-c) = a - c - b + c = a - b$로, 빼는 $c$가 서로 상쇄되어 가정이 붙잡고 있는 덩어리가 그대로 남는다. 문제 9(a)의 합 버전과 같은 구조이고, 거기서는 $(a+c) - (b+c) = a - b$가 된다. ### 빈칸 사다리 — 훈련 2 (1) 가정 (2) 정의 20.1 (3) $b - c$ (4) 2주차 예제 2.2 (5) $a - c$ (6) $a \equiv c \pmod n$ ※ (5)에서 $(a-b) + (b-c) = a - c$로 가운데 $b$가 상쇄된다 — 2주차 예제 2.1 (추이성)에서 다리 $b$를 대입으로 소거한 것과 같은 발상이고, 여기서는 덧셈으로 소거된다. 문제 7이 이 완성본을 백지에서 재현하는 자리다. ### 빈칸 사다리 — 훈련 3 (1) $a \equiv b \pmod n$이고 $n \mid c$라 가정하자. (2) 정의 20.1에 의해 $n \mid (a - b)$이다. (둘째 가정 $n \mid c$는 이미 배수 꼴이므로 번역할 것이 없다.) (3) $(a + c) - b = (a - b) + c$이고 $n \mid (a-b)$, $n \mid c$이므로 2주차 예제 2.2에 의해 $n \mid \big((a+c) - b\big)$이다. 따라서 정의에 의해 $a + c \equiv b \pmod n$이다. $\blacksquare$ ※ 가정 두 개 중 하나가 이미 "$n \mid c$" 꼴이라 번역 단계가 반만 필요했다. $n \mid c$는 $c \equiv 0 \pmod n$과 같은 뜻이므로, 이 명제는 (C4)에 $c \equiv 0$을 넣은 것과 같다 — 부품을 어느 쪽으로 읽어도 같은 결과가 나온다. ### 문제 1 **접근.** 다섯 항목 전부에서 할 일은 같다 — 차 $a - b$를 구하고, 그 차를 $n \times (\text{정수})$ 꼴로 적을 수 있는지 본다. 차가 음수로 나와도 절차는 바뀌지 않는다. 나눗셈으로 나머지를 비교하는 것은 연습장에서만 한다. **풀이.** (a) 참. $17 - 5 = 12$이고 $12 = 6 \times 2$이며 2는 정수이므로 $6 \mid 12$이다. 따라서 $17 \equiv 5 \pmod 6$이다. (b) 참. $8 - (-1) = 9$이고 $9 = 3 \times 3$이므로 $3 \mid 9$이다. 따라서 $8 \equiv -1 \pmod 3$이다. 빼는 수가 음수일 때 부호에 주의한다 — $8 - 1 = 7$이 아니다. (c) 거짓. $21 - 7 = 14$인데 $14 = 8c$인 정수 $c$는 없다($8 \times 1 = 8$, $8 \times 2 = 16$). 따라서 $8 \nmid 14$이고 $21 \not\equiv 7 \pmod 8$이다. (d) 참. $-3 - 7 = -10$이고 $-10 = 5 \times (-2)$이며 $-2$는 정수이므로 $5 \mid (-10)$이다. 따라서 $-3 \equiv 7 \pmod 5$이다. (e) 참. $100 - 2 = 98$이고 $98 = 7 \times 14$이므로 $7 \mid 98$이다. 따라서 $100 \equiv 2 \pmod 7$이다. **복기.** 판정의 두 얼굴 — 탐색은 나눗셈으로 해도 되지만, 답안의 근거는 곱 등식과 정수 확인(근거 ①)이다. (b)와 (d)에서 보듯 음수는 정의 앞에서 아무런 특별 취급도 받지 않는다. (e)의 결과는 예제 2.3의 요일 계산과 같은 사실이다. ### 문제 2 **접근.** 정의를 겹겹이 푸는 문제다. $\equiv$는 정의 20.1로 $\mid$가 되고, $\mid$는 2주차 정의 2.1로 $\exists$ 문장이 된다. (c)는 반대로, 말로 된 조건을 합동식으로 압축한다. **풀이.** (a) $n \mid (a - b)$. 정의 20.1을 그대로 옮긴 것이다. (b) $\exists k \in \mathbb{Z},\ a - b = nk$. (a)에 2주차 정의 2.1을 한 겹 더 적용했다. 말로 적으면 "$a - b = nk$인 정수 $k$가 존재한다"이고, 이 문장이 증명에서 실제로 쓰는 꼴이다. (c) $a \equiv b \pmod{10}$. 일의 자리는 10으로 나눈 나머지이므로 법이 10이고, "나머지가 같다"가 곧 합동이다(§1.4). **복기.** 정의의 사슬 $\equiv \to \mid \to \exists$ 가운데 어디까지 풀지는 목적이 정한다. 판정만 할 때는 $\mid$까지, 문자로 계산할 때는 $\exists$까지 푼다. (c)처럼 반대 방향으로 압축하는 것도 같은 사슬을 거꾸로 읽는 일이다. ### 문제 3 **접근.** 각 수에서 5의 배수를 더하거나 빼서 $0$ 이상 $5$ 미만의 수로 옮긴다. 옮긴 결과가 답이고, 근거는 "차가 5의 배수"라는 확인이다. 음수는 5를 몇 번 더해야 범위 안에 들어오는지 본다. **풀이.** $17 \equiv 2 \pmod 5$ — $17 - 2 = 15 = 5 \times 3$이므로 $5 \mid 15$이다. $23 \equiv 3 \pmod 5$ — $23 - 3 = 20 = 5 \times 4$이므로 $5 \mid 20$이다. $-4 \equiv 1 \pmod 5$ — $-4 - 1 = -5 = 5 \times (-1)$이므로 $5 \mid (-5)$이다. $40 \equiv 0 \pmod 5$ — $40 - 0 = 40 = 5 \times 8$이므로 $5 \mid 40$이다. **복기.** $-4$에서 $-4$나 $4$라고 답하는 경우가 많다. 원인은 나눗셈의 몫을 0 쪽으로 반올림하는 계산기의 관습을 그대로 쓰기 때문이다. 요구되는 범위는 $0 \le r < 5$이므로 몫을 $-1$까지 내려야 하고, 정의로 확인하면 ($-4 - 1 = -5$가 5의 배수) 갈래 없이 결정된다. (검산: $17, 23, -4, 40$을 각각 5로 나눈 나머지가 $2, 3, 1, 0$ ✓.) ### 문제 4 **접근.** 정의가 요구하는 것은 $n \mid (a - a)$뿐이다. $a - a = 0$이므로 물음은 "$n$이 0을 나누는가"로 바뀌고, 이것은 2주차 문제 2(a)에서 이미 판정했다. 짧은 증명이지만 세 박자(번역-조합-역번역)는 그대로 들어간다. **풀이.** $a$를 임의의 정수, $n$을 자연수라 하자. $a - a = 0$이고, $0 = n \times 0$이며 0은 정수이므로 정의 2.1에 의해 $n \mid 0$이다. 곧 $n \mid (a - a)$이다. 따라서 정의 20.1에 의해 $a \equiv a \pmod n$이다. $a$는 임의였으므로 모든 정수 $a$에 대해 성립한다. $\blacksquare$ **복기.** 결론이 뻔해 보여도 근거의 사슬은 똑같이 요구된다 — 여기서 실제로 쓰인 사실은 "$n$은 0을 나눈다"이고, 그 근거는 $0 = n \times 0$이라는 곱 등식이다. 이 한 줄이 빠지면 (C1)은 인용할 수 없는 명제로 남고, 문제 9(a)의 둘째 풀이가 무너진다. ### 문제 5 **접근.** 가정이 주는 것은 $n \mid (a - b)$, 목표가 요구하는 것은 $n \mid (b-a)$다. 두 수는 부호만 다르므로, 배수의 부호를 뒤집어도 배수라는 2주차 문제 8이 그대로 다리가 된다. **풀이.** $a \equiv b \pmod n$이라 가정하자. 정의 20.1에 의해 $n \mid (a - b)$이다. 2주차 문제 8($a \mid b$이면 $a \mid (-b)$)에 의해 $n \mid -(a-b)$이고, $-(a - b) = b - a$이므로 $n \mid (b - a)$이다. 따라서 정의 20.1에 의해 $b \equiv a \pmod n$이다. $\blacksquare$ **복기.** 정의 20.1이 $a - b$라는 **순서 있는** 차로 적혀 있는데도 실제로는 순서가 무관하다는 것이, 바로 이 (C2)가 보장해 주는 내용이다. §1.3 해부 표의 셋째 조각에서 "대칭성이 증명되고 나서야 순서가 무관해진다"고 한 빚을 여기서 갚았다. 이후로는 $n \mid (b-a)$를 보아도 $a \equiv b$라 적을 수 있다. ### 문제 6 **접근.** 양방향 모두 정의 번역만으로 끝난다. $n \equiv 1 \pmod 2$를 두 겹 풀면 $n - 1 = 2k$가 나오고, 이 등식을 $n$에 대해 정리하면 홀수의 정의 $n = 2k+1$과 같은 식이 된다. 곧 두 문장은 같은 등식의 다른 배열이다. **풀이.** ($\Rightarrow$) $n$이 홀수라 가정하자. 정의 1.2에 의해 $n = 2k + 1$인 정수 $k$가 존재한다. 양변에서 1을 빼면 $n - 1 = 2k$이고 $k$는 정수이므로 $2 \mid (n-1)$이다. 따라서 정의 20.1에 의해 $n \equiv 1 \pmod 2$이다. ($\Leftarrow$) $n \equiv 1 \pmod 2$라 가정하자. 정의 20.1에 의해 $2 \mid (n-1)$이고, 정의 2.1에 의해 $n - 1 = 2k$인 정수 $k$가 존재한다. 양변에 1을 더하면 $n = 2k + 1$이므로, 정의 1.2에 의해 $n$은 홀수이다. 양방향이 모두 성립하므로 두 명제는 동치이다. $\blacksquare$ **복기.** 1주차의 짝$\cdot$홀 세계 전체가 법 2의 합동으로 흡수된다 — 짝수는 $n \equiv 0 \pmod 2$, 홀수는 $n \equiv 1 \pmod 2$이다. 그래서 17주차의 짝$\cdot$홀 분할은 법 2의 나머지 분할과 같은 것이었고, 같은 방식으로 법 3, 법 4의 분할이 얻어진다. ### 문제 7 **접근.** 훈련 2의 완성본이다. 세 박자 그대로 — 정의로 두 배수를 받고, 목표의 차 $a - c$를 그 두 배수의 합으로 다시 쓰고, 정의로 되돌린다. 가운데 $b$가 상쇄되는 것이 이 증명의 전부다. **풀이.** $a \equiv b \pmod n$이고 $b \equiv c \pmod n$이라 가정하자. 정의 20.1에 의해 $n \mid (a - b)$이고 $n \mid (b - c)$이다. 2주차 예제 2.2(배수 두 개의 합은 배수)에 의해 $$ n \mid \big((a - b) + (b - c)\big) $$ 이고, $(a-b) + (b-c) = a - c$이므로 $n \mid (a - c)$이다. 따라서 정의 20.1에 의해 $a \equiv c \pmod n$이다. $\blacksquare$ **복기.** 2주차 예제 2.1(나누어떨어짐의 추이성)에서는 다리 $b$를 **대입**으로 소거했고, 여기서는 **덧셈**으로 소거했다. 두 경우 모두 "가운데 것을 없애는 변형"이 증명의 몸통이고, 이 발상은 36주차에서 추이성을 관계의 성질로 다룰 때 다시 나온다. (검산: $n = 6$, $a = 17$, $b = 5$, $c = 29$이면 $6 \mid 12$, $6 \mid (-24)$이고 $6 \mid (-12)$ ✓.) ### 문제 8 **접근.** 예제 2.2의 네 문장 재현이다. 목표의 차 $(a+c) - (b+d)$를 괄호를 풀어 다시 묶으면 가정이 붙잡고 있는 $(a-b)$와 $(c-d)$가 드러난다. 그 재배열이 보이면 나머지는 인용이다. **풀이.** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이라 가정하자. 정의 20.1에 의해 $n \mid (a - b)$이고 $n \mid (c - d)$이다. 2주차 예제 2.2에 의해 $$ n \mid \big((a - b) + (c - d)\big) $$ 이고, 덧셈의 교환$\cdot$결합법칙으로 $(a-b) + (c-d) = (a+c) - (b+d)$이므로 $n \mid \big((a+c) - (b+d)\big)$이다. 따라서 정의 20.1에 의해 $a + c \equiv b + d \pmod n$이다. $\blacksquare$ **복기.** 이 증명이 끝나는 순간 (C4)가 근거 ④에 등록되고, 이후 문제 9(a), 14, 15, 18이 전부 이 한 정리를 인용한다. 증명의 순서가 곧 인용 가능 시점의 순서라는 것을 답안에서 지키는 것도 채점 대상이다. (검산: $n = 6$에서 $17 \equiv 5$, $8 \equiv 2$이면 $25 \equiv 7$ — $6 \mid 18$ ✓.) ### 문제 9 **접근.** (a)는 두 길이 있다. 정의로 직접 계산하면 $(a+c) - (b+c) = a - b$로 $c$가 상쇄되고, 부품으로 가면 (C4)에 $c \equiv c$(반사성, 문제 4)를 끼워 넣는다. (b)는 $ka - kb = k(a-b)$로 묶은 뒤 2주차 훈련 1을 인용한다. **풀이.** (a) **풀이 1 (정의로 직접).** $a \equiv b \pmod n$이라 가정하고 $c$를 임의의 정수라 하자. 정의에 의해 $n \mid (a-b)$이다. 그런데 $(a + c) - (b + c) = a - b$이므로 $n \mid \big((a+c) - (b+c)\big)$이고, 정의에 의해 $a + c \equiv b + c \pmod n$이다. $\blacksquare$ **풀이 2 (부품 재사용).** 문제 4(반사성)에 의해 $c \equiv c \pmod n$이다. (C4)를 $a \equiv b$와 $c \equiv c$에 적용하면 $a + c \equiv b + c \pmod n$이다. $\blacksquare$ (b) $a \equiv b \pmod n$이라 가정하고 $k$를 임의의 정수라 하자. 정의에 의해 $n \mid (a - b)$이다. 2주차 훈련 1($a \mid b$이면 임의의 정수 $c$에 대해 $a \mid bc$)에 의해 $n \mid k(a - b)$이고, $k(a-b) = ka - kb$이므로 $n \mid (ka - kb)$이다. 따라서 정의에 의해 $ka \equiv kb \pmod n$이다. $\blacksquare$ **복기.** (a)의 풀이 2에서 반사성이 "당연한 성질"이 아니라 **부품**으로 쓰였다 — (C1)~(C5)를 한 세트로 증명해 두는 이유가 이것이다. 한편 (b)의 역은 성립하지 않는다: §1.5 확인 7에서 본 대로 $2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}$이지만 $3 \not\equiv 8 \pmod{10}$이다. 곱하는 것은 자유이고 나누는 것은 자유가 아니다. ### 문제 10 **접근.** (C5)는 서로 다른 두 합동식을 요구하지만, 같은 합동식을 두 번 넣어도 된다. $a \equiv b$와 $a \equiv b$를 넣으면 결론이 $a \cdot a \equiv b \cdot b$가 된다. 정의까지 내려가지 않고 부품 하나로 끝나는 문제다. **풀이.** $a \equiv b \pmod n$이라 가정하자. (C5)를 두 합동식 $a \equiv b \pmod n$과 $a \equiv b \pmod n$에 적용하면 $a \cdot a \equiv b \cdot b \pmod n$, 곧 $a^2 \equiv b^2 \pmod n$이다. $\blacksquare$ 여기서 인용한 (C5)의 답안 형태는 문제 17이지만, 그 증명은 §2 예제 2.2 말미에서 이미 조립되었으므로 근거 ④로 쓸 수 있다. **복기.** 같은 정리에 같은 가정을 두 번 대입하는 것은 근거 ④의 정당한 사용이다. 이 조작을 반복하면 $a^3 \equiv b^3$, $a^4 \equiv b^4$로 이어지고, 그 반복의 일반형이 §1.6에서 인정하고 쓴 거듭제곱 보존이다(엄밀한 증명은 31주차 문제 13). (검산: $n = 6$에서 $17 \equiv 5$이면 $289 \equiv 25$ — $289 - 25 = 264 = 6 \times 44$ ✓.) ### 문제 11 **접근.** 일의 자리는 법 10이다. §1.6의 절차 그대로 $7^k$를 법 10에서 줄여 1이 나오는 지수를 찾고, 42를 그 주기로 나눈 나머지로 위치를 정한다. 큰 수를 직접 계산하지 않는 것이 이 방법의 요점이다. **풀이.** 법 10에서 $7$의 거듭제곱을 차례로 줄인다. $$ 7^1 \equiv 7, \quad 7^2 = 49 \equiv 9, \quad 7^3 \equiv 7 \cdot 9 = 63 \equiv 3, \quad 7^4 \equiv 7 \cdot 3 = 21 \equiv 1 \pmod{10} $$ (각 단계는 (C5)를 앞 결과와 $7 \equiv 7$에 적용한 것이다. 예를 들어 $63 \equiv 3$은 $63 - 3 = 60$이 10의 배수이므로 성립한다.) $7^4 \equiv 1$이 나왔으므로 주기는 4다. $42 = 4 \times 10 + 2$이므로 $$ 7^{42} = (7^4)^{10} \cdot 7^2 \equiv 1^{10} \cdot 9 = 9 \pmod{10} $$ 이다. 거듭제곱 보존(§1.6에서 인정하고 쓰기로 한 사실, 엄밀한 증명은 31주차 문제 13)에 의해 $(7^4)^{10} \equiv 1^{10} \pmod{10}$이고, 여기에 (C5)로 $7^2 \equiv 9$를 곱하면 위와 같다. 따라서 $7^{42}$의 일의 자리는 9이다. **복기.** 절차를 세 단계로 고정해 두면 밑이 3, 7처럼 1로 되돌아오는 경우에는 그대로 쓸 수 있다 — ① 법을 정한다 ② 1이 나오는 지수(주기)를 찾는다 ③ 지수를 주기로 나눈 나머지만 남긴다. 1이 돌아오지 않는 밑도 있다 — 법 10에서 2의 거듭제곱은 2, 4, 8, 6이 반복될 뿐 1이 나오지 않고, 5의 거듭제곱은 언제나 5다. 그때는 1 대신 앞서 나온 값이 다시 나오는 지점을 주기로 잡는다. 38주차 문제 12에서 이 계산을 $\mathbb{Z}_{10}$의 언어로 다시 쓴다. ### 문제 12 **접근.** 요일은 법 7이다(예제 2.3). 365를 7로 나눈 나머지를 구해 큰 수를 작은 수로 갈아 끼운 뒤, 화요일에서 그만큼 진행한다. **풀이.** $365 = 7 \times 52 + 1$이고 $365 - 1 = 364 = 7 \times 52$이므로 $7 \mid 364$, 곧 $365 \equiv 1 \pmod 7$이다. 따라서 365일 후의 요일은 1일 후의 요일과 같다. 화요일의 하루 뒤는 수요일이므로 답은 수요일이다. **복기.** 이 계산이 "1년 뒤 같은 날짜의 요일이 하루 밀린다"는 현상의 근거다. 윤년이면 $366 = 7 \times 52 + 2$이므로 $366 \equiv 2 \pmod 7$이 되어 이틀 밀린다. 달력의 규칙성은 대부분 법 7의 합동으로 설명된다. ### 문제 13 **접근.** 두 가정 중 더 강한 정보인 $3 \mid x$부터 쓴다 — $x = 3k$로 놓으면 목표 $6 \mid x$까지 남은 것은 $k$가 짝수라는 사실 하나다. 그 사실은 $x$가 짝수라는 다른 가정에서 나오고, 다리는 "홀수 $\times$ 홀수 = 홀수"(1주차 문제 8)의 대우다. **풀이.** $2 \mid x$이고 $3 \mid x$라 가정하자. 정의 2.1에 의해 $x = 3k$인 정수 $k$가 존재한다. 또 $2 \mid x$이므로 $x$는 짝수이고, 따라서 $3k$는 짝수이다. 여기서 $k$가 홀수라면, 3도 홀수이므로 1주차 문제 8(홀수와 홀수의 곱은 홀수)에 의해 $3k$가 홀수가 되어 $3k$가 짝수라는 것과 어긋난다. 그러므로 $k$는 짝수이고, 정의 1.1에 의해 $k = 2m$인 정수 $m$이 존재한다. 그러면 $$ x = 3k = 3(2m) = 6m $$ 이고 $m$은 정수이므로, 정의 2.1에 의해 $6 \mid x$이다. $\blacksquare$ **복기.** 5주차 문제 9에서 나열 관찰로만 인정하고 쓰던 "2와 3의 공배수는 6의 배수"가 여기서 증명됐다. 7주차 문제 9, 25주차 문제 12, 30주차 문제 17이 이 결과를 그대로 인용한다. 8주차 문제 11(d)와 14주차 훈련 1이 쓰는 "공배수 = 최소공배수의 배수"의 일반형은 이번 주가 증명한 2와 3의 경우를 넘어서므로, 여전히 인정하고 쓰는 사실로 남는다. 몸통에 쓰인 "만약 ~라면 어긋나므로 ~이다"라는 서술은 다음 주 귀류법의 축소판이다. (검산: $x = 24$이면 $2 \mid 24$, $3 \mid 24$이고 $24 = 6 \times 4$ ✓.) ### 문제 14 **접근.** 존재하지 않음을 보이는 방법은 가능한 값을 전부 훑는 것이다. 17주차 문제 9가 $n^2$의 법 4 값을 0과 1 두 개로 줄여 주므로, 각각에 (C4)로 1을 더해 $n^2 + 1$의 후보를 만들고 그 목록에 0이 없음을 확인한다. **풀이.** $n$을 임의의 정수라 하자. 17주차 문제 9에 의해 $n^2$을 4로 나눈 나머지는 0 또는 1이므로, $n^2 \equiv 0 \pmod 4$ 또는 $n^2 \equiv 1 \pmod 4$이다. 문제 4(반사성)에 의해 $1 \equiv 1 \pmod 4$이므로, (C4)를 적용하면 - $n^2 \equiv 0$인 경우: $n^2 + 1 \equiv 0 + 1 = 1 \pmod 4$ - $n^2 \equiv 1$인 경우: $n^2 + 1 \equiv 1 + 1 = 2 \pmod 4$ 이다. 두 경우가 모든 정수 $n$을 빠짐없이 덮고, 어느 경우에도 $n^2 + 1 \equiv 0 \pmod 4$가 아니다. 따라서 $n^2 + 1 \equiv 0 \pmod 4$인 정수 $n$은 존재하지 않는다. $\blacksquare$ **복기.** "가능한 값의 목록을 만들고 목표가 그 목록에 없음을 보인다" — 존재하지 않음을 증명하는 표준 수법이고, 17주차 문제 17($n^2+2$는 4의 배수가 아니다)을 합동 언어로 옮긴 것이다. 목록을 만드는 도구가 이번 주에는 (C4)와 (C5)다. (검산: $n = 0, 1, 2, 3$에서 $n^2 + 1 = 1, 2, 5, 10$이고 4로 나눈 나머지는 $1, 2, 1, 2$ — 0이 없다 ✓.) ### 문제 15 **접근.** 출발점은 $10 - 1 = 9$라는 사실 하나다. 여기서 $10 \equiv 1 \pmod 9$이 나오고, (C5)로 $100 \equiv 1$을 얻는다. 그다음 문제 9(b)로 계수 $a, b$를 붙이고 (C4)로 세 조각을 더하면 목표에 닿는다. 마지막 문장은 합동을 정의 20.1로 되돌린 뒤 2주차의 배수 정리 두 개로 잇는 자리다 — "나머지가 같다"는 §1.4에서 정한 대로 근거 목록에 없다. **풀이.** $10 - 1 = 9 = 9 \times 1$이므로 $9 \mid (10 - 1)$, 곧 $10 \equiv 1 \pmod 9$이다. (C5)를 $10 \equiv 1$과 $10 \equiv 1$에 적용하면 $100 \equiv 1 \pmod 9$이다. 문제 9(b)에 의해 양변에 정수를 곱해도 합동이 유지되므로 $$ 100a \equiv a \pmod 9, \qquad 10b \equiv b \pmod 9 $$ 이고, 문제 4(반사성)에 의해 $c \equiv c \pmod 9$이다. (C4)를 앞의 두 식에 적용하면 $100a + 10b \equiv a + b \pmod 9$이고, 여기에 다시 (C4)로 $c \equiv c$를 더하면 $$ N = 100a + 10b + c \equiv a + b + c \pmod 9 $$ 이다. $\blacksquare$ (여기서 쓴 (C5)의 증명은 §2 예제 2.2 말미에서 조립되었고, 답안 형태로 적는 것이 문제 17이다.) 판정법이 되는 이유: $N \equiv a+b+c \pmod 9$이므로 정의 20.1에 의해 $9 \mid \big(N - (a+b+c)\big)$이다. 자릿수 합이 9의 배수이면 $N = \big(N - (a+b+c)\big) + (a+b+c)$가 두 배수의 합이므로 2주차 예제 2.2에 의해 $9 \mid N$이고, 거꾸로 $9 \mid N$이면 $a+b+c = N - \big(N - (a+b+c)\big)$가 두 배수의 차이므로 2주차 문제 7에 의해 $9 \mid (a+b+c)$이다. 곧 한쪽이 9의 배수인 것과 다른 쪽이 9의 배수인 것이 서로 같다. **복기.** 이 증명이 쓴 것은 $10 \equiv 1 \pmod 9$ 단 하나이고, 나머지는 (C4)와 (C5)로 그 사실을 자릿수만큼 퍼뜨린 것이다. 같은 논증이 임의 자릿수로 확장되며 ($10^k \equiv 1^k = 1$), 그 일반화의 엄밀한 처리가 31주차 문제 15다. 또 $10 - 1 = 9$는 3의 배수이기도 하므로 $10 \equiv 1 \pmod 3$이고, 똑같은 논증이 3의 배수 판정법을 준다. (검산: $N = 342$이면 $3+4+2 = 9$이고 $342 = 9 \times 38$ ✓.) ### 문제 16 **접근.** 등식이 참이라면 양변을 법 9로 줄인 값도 같아야 한다. 그러므로 좌변과 우변을 각각 법 9에서 줄여 비교하고, 값이 다르면 등식은 성립할 수 없다. 좌변을 줄이는 도구는 문제 15(자릿수 합)와 (C5)이고, 우변은 세 자리가 아니므로 정의로 직접 판정한다. **풀이.** 좌변의 두 수는 세 자리이므로 문제 15가 그대로 적용된다 — 각 수는 자릿수 합과 법 9에서 합동이다. $437 \equiv 4 + 3 + 7 = 14 \pmod 9$이고, 다시 $14 \equiv 1 + 4 = 5 \pmod 9$이다 ($14 - 5 = 9$). 또 $254 \equiv 2 + 5 + 4 = 11 \equiv 2 \pmod 9$이다 ($11 - 2 = 9$). (C5)를 두 합동식에 적용하면 $$ 437 \times 254 \equiv 5 \times 2 = 10 \equiv 1 \pmod 9 $$ 이다. 한편 주장된 값 $110{,}898$은 여섯 자리이므로 문제 15(세 자리 한정)가 닿지 않는다. 정의로 직접 판정한다 — $110{,}898 - 0 = 110{,}898 = 9 \times 12322$이므로 $9 \mid 110{,}898$, 곧 $110{,}898 \equiv 0 \pmod 9$이다. (자릿수 합 $1+1+0+8+9+8 = 27$도 같은 값을 주지만, 임의 자릿수의 자릿수 합 규칙은 31주차 문제 15의 몫이므로 여기서는 검산으로만 쓴다.) 만약 $437 \times 254 = 110{,}898$이 참이라면 같은 수가 법 9에서 1과도 0과도 합동이어야 하는데, $1 \not\equiv 0 \pmod 9$이므로 그럴 수 없다. 따라서 이 계산은 틀렸다. $\blacksquare$ **복기.** 이 검산법은 "법 9의 나머지가 맞는가"만 확인하므로 **틀림은 확정하고 맞음은 보장하지 않는다** — 필요조건 검사다. 실제 값은 $110{,}998$이고 $110{,}998 - 1 = 110{,}997 = 9 \times 12333$이므로 법 9에서 1 — 앞의 계산과 맞는다(자릿수 합 $28$로도 같은 값이 나온다). 옳은 답이 아닌데도 통과하는 값이 9의 배수만큼 떨어진 곳마다 있으므로, 통과했다고 옳다고 결론지을 수는 없다. ### 문제 17 **접근.** 예제 2.2의 확인 17에서 만든 항등식 $ac - bd = c(a-b) + b(c-d)$가 몸통이다. 그 앞에 정의 번역, 뒤에 역번역을 붙이고, 두 덩어리가 각각 배수임을 2주차 훈련 1로, 합이 배수임을 2주차 예제 2.2로 근거 붙인다. **풀이.** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이라 가정하자. 정의 20.1에 의해 $n \mid (a - b)$이고 $n \mid (c - d)$이다. 여기서 $ac - bd$에 $-bc + bc$를 더해 보면(값은 변하지 않는다) $$ ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) $$ 이다. 2주차 훈련 1(배수에 임의의 정수를 곱해도 배수)에 의해 $n \mid c(a - b)$이고 $n \mid b(c - d)$이다. 2주차 예제 2.2(배수 두 개의 합은 배수)에 의해 $n \mid \big(c(a-b) + b(c-d)\big)$, 곧 $n \mid (ac - bd)$이다. 따라서 정의 20.1에 의해 $ac \equiv bd \pmod n$이다. $\blacksquare$ **복기.** "빼고 더하기"는 목표에 필요한 덩어리가 식에 없을 때 그 덩어리가 나타나도록 항을 쪼개는 수법이다. 17주차 문제 16에서 $x = (x-y)+y$로 쓴 것과 같은 발상이고, 32주차의 귀납 단계에서 $f(k+1)$을 "$f(k)$의 배수 항 + 나머지"로 재배열할 때 다시 쓴다. 어느 항을 삽입할지는 도착점이 정한다 — 여기서는 $bc$를 넣었지만 $ad$를 넣어도 된다. $ac - bd = ac - ad + ad - bd = a(c-d) + d(a-b)$로 쪼개지며 결론은 같다. 삽입할 항은 두 덩어리가 인수로 남게 하는 것이면 되고, 그런 항이 유일할 필요는 없다. (검산: $n = 6$에서 $17 \equiv 5$, $8 \equiv 2$이면 $136 \equiv 10$ — $136 - 10 = 126 = 6 \times 21$ ✓.) ### 문제 18 **접근.** 재진술은 정의 번역이다 — $n^2 = 8m + 1$은 $n^2 - 1 = 8m$, 곧 $8 \mid (n^2 - 1)$이고 이는 $n^2 \equiv 1 \pmod 8$이다. 재진술을 끝내면 두 홀수에 각각 적용하고 (C4)로 더하기만 하면 된다. **풀이.** **재진술.** 17주차 문제 15는 "$n$이 홀수이면 $n^2 = 8m + 1$인 정수 $m$이 존재한다"이다. 이 등식을 정리하면 $n^2 - 1 = 8m$이므로 정의 2.1에 의해 $8 \mid (n^2 - 1)$이고, 정의 20.1에 의해 이는 다음과 같다. $$ n\text{이 홀수이면 } n^2 \equiv 1 \pmod 8 $$ **증명.** $a$와 $b$가 홀수라 가정하자. 위의 재진술을 $a$와 $b$에 각각 적용하면 $a^2 \equiv 1 \pmod 8$이고 $b^2 \equiv 1 \pmod 8$이다. (C4)를 이 두 합동식에 적용하면 $$ a^2 + b^2 \equiv 1 + 1 = 2 \pmod 8 $$ 이다. $\blacksquare$ **복기.** 따름정리 하나가 바로 나온다 — 홀수 제곱 두 개의 합은 4의 배수가 될 수 없다. 법 8에서 나머지가 2이면 $a^2 + b^2 = 8k + 2 = 4(2k) + 2$로 법 4에서도 나머지가 2이기 때문이다. 이것이 19주차 문제 18에서 얻은 결과이고, 합동 언어로 쓰니 계산이 두 줄로 줄었다. 38주차에서는 같은 사실이 $\mathbb{Z}_8$의 홀수 대표원 제곱이 전부 $[1]$이라는 형태로 다시 나온다. (검산: $a = 3$, $b = 5$이면 $9 + 25 = 34 = 8 \times 4 + 2$ ✓.) ### 문제 19 **접근.** 여섯 조항을 차례로 대조하며 위반을 세고, 지적으로 끝내지 말고 교정본까지 적는다. 계산 자체는 옳으므로 고칠 것은 서술뿐이다 — 어떤 문장이 어떤 근거로 다음 문장을 낳는지가 드러나게 다시 쓴다. **풀이.** 위반은 다섯 곳이다. ① **1조 위반.** 첫 문장이 수식 "$n = 2k+1$"로 시작한다. 말로 시작해야 한다. ② **2조 위반.** $n$과 $k$가 소개 없이 등장한다. $n$이 임의의 홀수인지 특정 수인지, $k$의 존재가 보장된 것인지 아무 선언이 없다. ③ **3조 위반.** "$2(2k^2+2k)+1 = $ 홀수"에서 수와 성질을 등호로 이었다. "홀수"는 수가 아니므로 등호의 오른쪽에 올 수 없다. ④ **4조 위반.** $\Rightarrow$가 문장 사이의 접속사로 쓰였다. 산문에서는 "그러면", "따라서"를 쓴다. ⑤ **6조 위반.** "증명."이라는 개시 표시가 없다. ($\blacksquare$는 있으므로 종료 표시만 갖춰져 있다.) **교정본.** "**증명.** $n$을 홀수라 하자. 홀수의 정의에 의해 $n = 2k+1$인 정수 $k$가 존재한다. 그러면 $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$이고, $2k^2 + 2k$는 정수이므로 $n^2$은 홀수이다. $\blacksquare$" **복기.** 교정본과 원본의 계산은 한 글자도 다르지 않다 — 달라진 것은 각 줄이 어느 근거로 나왔는지를 읽는 사람이 복원할 수 있게 된 점뿐이다. 15주차 §1.8의 답안 A에서 시작한 글쓰기 훈련이 여기서 여섯 조항으로 완성되고, 24주차와 50주차의 시험에서 이 여섯 조항이 채점 대상이 된다. ### 문제 20 **접근.** 닮은 점은 (C1)~(C3)을 등호의 세 성질과 짝지으면 되고, 다른 점은 "$=$가 묶는 것"과 "$\equiv$가 묶는 것"의 범위를 비교한다. 시계 계산은 법 12의 합동으로 번역한 뒤 (C4)로 정당화한다. **풀이.** (예시 답안) **닮은 점 세 가지.** 등호가 가진 반사성($a = a$), 대칭성($a = b$이면 $b = a$), 추이성($a = b$이고 $b = c$이면 $a = c$)을 $\equiv \pmod n$도 그대로 가진다 — 각각 (C1), (C2), (C3)이다. 그래서 합동식은 등식처럼 좌우를 바꾸거나 사슬로 이어 쓸 수 있고, (C4)(C5)에 의해 변끼리 더하고 곱할 수도 있다. **다른 점.** $=$는 완전히 같은 대상만 묶지만, $\equiv \pmod n$은 17과 5처럼 서로 다른 수들을 "나머지가 같다"는 기준으로 같은 취급한다 — 같음의 기준이 느슨해진 것이다. (같음의 기준이 느슨해진 대가로 잃는 것도 있다: §1.5 확인 7에서 본 대로 양변을 공통 인수로 나누는 조작이 허용되지 않는다. 이 점을 다른 점으로 써도 된다.) **시계 계산.** $8 + 7 = 15$이고 $15 - 3 = 12 = 12 \times 1$이므로 $15 \equiv 3 \pmod{12}$이다. 따라서 법 12의 세계에서 $8 + 7$은 3이 된다 — 8시에서 7시간 뒤가 3시인 것이 이 계산이다. "12를 넘으면 되감는" 산술이 (C4)로 정당화된다. **복기.** 같음의 기준을 바꾸면 산술이 바뀐다는 관찰은 이 과정의 뒷부분 전체를 관통한다. 어떤 관계가 이런 "느슨한 같음"의 자격을 갖는지가 36~37주차 동치관계의 주제이고, 그렇게 묶어 만든 세계 $\mathbb{Z}_n$의 산술이 잘 정의되는지가 38주차의 주제다. 이번 주에 증명한 (C4)(C5)가 그때 연산의 자격 심사에 그대로 쓰인다. --- **다음 주 예고:** 귀류법(proof by contradiction) — 결론을 부정한 채로 논리를 밀고 나가 어긋남에 도달하는 증명법을 다룬다. 이번 주 문제 13의 몸통에서 "만약 $k$가 홀수라면 어긋나므로"라고 쓴 대목이 그 축소판이다. 2500년 묵은 두 결과 "$\sqrt{2}$는 무리수"와 "소수는 무한히 많다"를 직접 증명하며, 11주차 문제 20에서 적어 둔 두 줄이 그때 완성된다.