# C6주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 다섯 무대를 한 절차로 완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 나눗셈: 선형결합 성질 **Result.** 정수 $a, b, c$에 대해, $a \mid b$이고 $a \mid c$이면 임의의 정수 $x, y$에 대해 $a \mid (bx + cy)$. **설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 정한다. 둘 다 정의 6.1로 번역해서 얻는다 — 걸음 ②와 ③이다. | | **말** | **수식 번역** | |---|---|---| | 가정 (출발점) | $a \mid b$, $a \mid c$ | $b = ak$, $c = al$인 정수 $k, l$이 존재 | | 목표 (도착점) | $a \mid (bx + cy)$ | $bx + cy = \underline{\quad(?)\quad}$ 꼴을 만든다 | :::{container} quotebox **확인 11.** 목표 칸의 빈칸을 채워 보자. "$a \mid (bx+cy)$를 보인다"를 정의 6.1로 번역하면 무엇을 만들어야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown $bx + cy = a \times (\text{정수})$ 꼴. 정의 6.1의 "존재한다"가 목표 쪽에 있으므로, 그런 정수를 직접 구성해 제시하는 것이 이 증명의 일이다. 출발점(등식 두 개)과 도착점(만들 꼴)이 정해졌으니 그 사이는 걸음 ④의 계산이다. ::: **1단계 — 대상을 문자로 잡고 가정을 쓴다.** 명제는 "모든 정수 $a, b, c, x, y$"에 대한 주장이므로 특정 숫자가 아니라 문자를 올린다. :::{container} quotebox **확인 12.** 첫 문장을 완성해 보자: "정수 $a, b, c$에 대해 $\underline{\qquad}$이고 $\underline{\qquad}$라 하자. 또 $x, y$를 $\underline{\qquad}$라 하자." ::: :::{admonition} 답 :class: quotebox dropdown "정수 $a, b, c$에 대해 $a \mid b$이고 $a \mid c$라 하자. 또 $x, y$를 임의의 정수라 하자." $x, y$에는 가정이 붙어 있지 않으므로 풀 정의가 없다 — 정수라는 자격만 선언하고 그대로 둔다. ::: **2단계 — 정의를 풀어 쓴다(걸음 ②).** "나눈다"는 아직 말이다. 등식으로 바꾼다. :::{container} quotebox **확인 13.** 둘째 문장을 완성해 보자: "정의 6.1에 의해 $b = \underline{\quad}$인 정수 $k$가 존재하고, $c = \underline{\quad}$인 정수 $\underline{\quad}$이 존재한다." 왜 문자를 둘 쓰는가. ::: :::{admonition} 답 :class: quotebox dropdown $b = ak$, $c = al$인 정수 $l$. 문자를 같은 $k$로 쓰면 $b = c$라고 몰래 가정한 셈이 된다 — 약수는 같은 $a$지만 몫은 각각이므로 서로 다른 문자를 쓴다 (1권 2주차 예제 2.2와 같은 자리다). ::: **3단계 — 도착점의 꼴로 조립한다(걸음 ④).** 재료 $ak$, $al$을 목표 꼴 $a \times (\text{정수})$에 맞춰 조립한다. :::{container} quotebox **확인 14.** 셋째 문장을 완성해 보자: "그러면 $bx + cy = \underline{\qquad} = a(\underline{\qquad})$이다." ::: :::{admonition} 답 :class: quotebox dropdown $bx + cy = (ak)x + (al)y = akx + aly = a(kx + ly)$. 분배법칙으로 $a$를 묶었다 — 근거 ③. 목표 꼴이 "$a \times$ 무엇"이므로 묶을 대상이 처음부터 정해져 있었다. ::: **4단계 — 괄호 안의 자격을 확인한다(걸음 ⑤ 전반).** $a(kx+ly)$가 정의 6.1의 꼴이려면 괄호 안이 **정수**여야 한다. 이 확인이 빠지면 §1.3의 삭제 실험이 재연된다. :::{container} quotebox **확인 15.** 넷째 문장을 완성해 보자: "$k, l, x, y$가 전부 정수이고 $\underline{\qquad}$이므로 $kx + ly$는 정수이다." ::: :::{admonition} 답 :class: quotebox dropdown "정수의 곱과 합은 정수이므로" — 근거 ②. 곱 두 번과 합 한 번이 쓰였다. ::: **5단계 — 결론을 선언한다(걸음 ⑤ 후반).** 도착점 꼴이 완성되었음을 정의를 인용해 선언한다. :::{container} quotebox **확인 16.** 마지막 문장을 완성해 보자: "따라서 $bx + cy = a(kx+ly)$는 $\underline{\qquad}$의 꼴을 만족하므로 $\underline{\qquad}$이다. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown "따라서 $bx + cy = a(kx+ly)$는 정의 6.1의 꼴을 만족하므로 $a \mid (bx + cy)$이다. $\blacksquare$" 이 다섯 문장이 완성된 증명이고, (D2)가 증명되었으므로 이제부터 근거 ④로 인용할 수 있다. ::: **완성본.** 방금 만든 다섯 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 정수 $a, b, c$에 대해 $a \mid b$이고 $a \mid c$라 하자. 또 $x, y$를 임의의 정수라 하자. | 걸음 ① — 무대는 나눗셈이고 대상을 문자로 올린다. $x, y$에는 가정이 없으므로 자격만 선언한다. | | 정의 6.1에 의해 $b = ak$인 정수 $k$가 존재하고 $c = al$인 정수 $l$이 존재한다. | 걸음 ② 전진면 — 이름을 등식으로 바꾼다(근거 ①). 몫이 각각이므로 문자를 다르게 쓴다. | | 목표는 $bx + cy$를 "$a \times (\text{정수})$" 꼴로 만드는 것이다. | 걸음 ③ 후진면 — 도착점을 먼저 적어 두어야 어느 변형이 진전인지 판정된다(§1.4의 걸음 삭제 실험). | | 그러면 $bx + cy = akx + aly = a(kx + ly)$이다. | 걸음 ④ — 대입하고 분배법칙으로 $a$를 묶는다(근거 ③). 묶을 대상은 도착점이 지정했다. | | $kx + ly$는 정수이므로(정수의 곱과 합은 정수), 정의 6.1에 의해 $a \mid (bx + cy)$이다. $\blacksquare$ | 걸음 ⑤ — 자격 확인(근거 ②) 후 정의를 인용해 닫는다. | **[주의] 자주 하는 실수: 도착점 없이 전개하기.** $bx + cy$에 $b = ak$, $c = al$을 대입한 뒤 $akx + aly$에서 멈추는 경우가 많다. 식은 옳지만 정의 6.1의 꼴이 아니다. 걸음 ③을 적어 두지 않으면 "$a$로 묶어야 한다"는 판단이 나오지 않는다. **이 성질이 뒤에서 쓰이는 자리.** $x = y = 1$이면 (D2)는 "$a \mid (b+c)$"가 되고 $x = 1, y = -1$이면 "$a \mid (b-c)$"가 된다. 문제 16에서 "$9 \mid n$과 $9 \mid \sum d_i$가 서로를 결정한다"를 보일 때 쓰는 것이 바로 이 두 특수 경우다. 선형결합 성질은 C15주차 유클리드 호제법의 씨앗이기도 하다. ### 예제 2.2 — 합동: 곱 보존 (C5) **Result (곱 보존).** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이면 $ac \equiv bd \pmod n$. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 17.** 번역표를 채워 보자. 가정: $a \equiv b$, $c \equiv d \pmod n$ $\to$ 정의 6.2와 6.1을 연이어 풀면 $a - b = \underline{\quad}$, $c - d = \underline{\quad}$인 정수 $s, t$가 존재. 목표: $ac \equiv bd \pmod n$ $\to$ $\underline{\qquad}$가 "$n \times (\text{정수})$" 꼴임을 보인다. ::: :::{admonition} 답 :class: quotebox dropdown 가정: $a - b = ns$, $c - d = nt$. 합동은 정의가 두 겹이므로 정의 6.2로 $n \mid (a-b)$를 얻고 정의 6.1로 등식까지 내려가야 계산이 시작된다. 목표: $ac - bd$가 "$n \times (\text{정수})$" 꼴임을 보인다. 도착점이 $ac - bd$라는 **차**라는 것이 이 예제의 전부다 — 손에 있는 재료는 $a - b$와 $c - d$이므로, 걸음 ④의 과제는 "$ac - bd$를 이 두 차로 표현하는 것"이 된다. ::: :::{container} quotebox **확인 18.** $ac - bd$를 $a - b$와 $c - d$로 표현해 보자. 두 재료를 동시에 쓰려면 항 하나를 더하고 빼는 조작이 필요하다. 무엇을 더하고 빼는가. ::: :::{admonition} 답 :class: quotebox dropdown $bc$를 더하고 뺀다. $$ ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) $$ 앞 묶음에서 $a - b$가, 뒤 묶음에서 $c - d$가 각각 나온다. $bc$ 대신 $ad$를 더하고 빼도 된다 — $ac - ad + ad - bd = a(c-d) + d(a-b)$. 어느 쪽이든 두 재료를 한 번씩 쓰는 것이 목적이고, 그 목적은 걸음 ③이 도착점을 $ac - bd$로 못 박아 두었기에 나온다. ::: | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이라 하자. | 걸음 ① — 무대는 합동이고 대상을 문자로 올린다. | | 정의 6.2에 의해 $n \mid (a-b)$이고 $n \mid (c-d)$이며, 정의 6.1에 의해 $a - b = ns$, $c - d = nt$인 정수 $s, t$가 존재한다. | 걸음 ② — 정의가 두 겹이므로 두 번 푼다. 등식이 나와야 근거 ③이 작동한다. | | 목표는 $ac - bd$를 "$n \times (\text{정수})$" 꼴로 만드는 것이다. | 걸음 ③ — 도착점이 차 $ac - bd$임을 못 박는다. 이 한 줄이 다음 줄의 조작을 지시한다. | | $ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d)$이다. | 걸음 ④ 전반 — $bc$를 더하고 빼서 두 재료가 각각 나타나도록 항을 쪼갠다(근거 ③). | | $= c(ns) + b(nt) = n(cs + bt)$이다. | 걸음 ④ 후반 — 대입 후 $n$을 묶는다. 도착점이 지정한 묶음이다. | | $cs + bt$는 정수이므로 $n \mid (ac - bd)$이고, 정의 6.2에 의해 $ac \equiv bd \pmod n$이다. $\blacksquare$ | 걸음 ⑤ — 자격 확인(근거 ②) 후 정의 두 겹을 거슬러 올라가 닫는다. | **활용.** (C5)가 손에 들어오면 §1.1의 과제가 두 줄로 끝난다. $7 \equiv -1 \pmod 4$이고 (확인 7), 거듭제곱 보존에 의해 $7^{100} \equiv (-1)^{100} = 1 \pmod 4$이다. $7^{100}$을 한 번도 계산하지 않았다. **감상.** 이 증명의 값은 "$bc$를 더하고 빼기"라는 기교에 있지 않다. 그 기교는 재료 $a - b$와 $c - d$를 각각 한 번씩 쓰는 경로를 택했을 때 걸음 ③이 지정한 도착점이 불러낸 계산이다. §1.4에서 본 대입-전개 경로도 같은 도착점에 이르므로, 걸음 ③이 고르는 것은 유일한 기교가 아니라 **어느 변형이 진전인지의 판정 기준**이다. 그리고 (C4)(C5)가 증명된 덕분에 합동식을 등식처럼 더하고 곱할 수 있게 되며, 이것이 C11주차에서 "잘 정의된 연산"이라는 이름으로 다시 다뤄진다. ### 예제 2.3 — 집합·곱: 원소 추적 **Result.** $A \times (B \cap C) = (A \times B) \cap (A \times C)$. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 19.** 이 무대의 설계를 세 줄로 적어 보자. ① 양변의 원소는 어떤 자료형인가. ② 목표가 집합의 상등일 때 증명은 몇 파트인가. 각 파트의 첫 문장은 무엇인가. ③ 좌변과 우변을 각각 논리식으로 번역하면 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown ① 순서쌍 $(x, y)$다. 곱의 원소이므로 좌표가 둘이다(정의 6.3). ② 두 파트다(1권 27주차 §1.4). ($\subseteq$) "$(x,y) \in A \times (B \cap C)$라 하자." ($\supseteq$) "$(x,y) \in (A \times B) \cap (A \times C)$라 하자." ③ 좌변: $x \in A$ 이고 ($y \in B$ 이고 $y \in C$). 우변: ($x \in A$ 이고 $y \in B$) 이고 ($x \in A$ 이고 $y \in C$). 두 논리식은 "이고"의 괄호 배치와 $x \in A$의 중복만 다르다 — 이 관찰이 증명 전체를 미리 보여 준다. ::: **증명.** ($\subseteq$) $(x, y) \in A \times (B \cap C)$라 하자. 정의 6.3에 의해 $x \in A$이고 $y \in B \cap C$이다. 교집합의 정의에 의해 $y \in B$이고 $y \in C$이다. 그러면 $x \in A$이고 $y \in B$이므로 정의 6.3에 의해 $(x, y) \in A \times B$이고, $x \in A$이고 $y \in C$이므로 $(x, y) \in A \times C$이다. 따라서 교집합의 정의에 의해 $(x, y) \in (A \times B) \cap (A \times C)$이다. ($\supseteq$) $(x, y) \in (A \times B) \cap (A \times C)$라 하자. 교집합의 정의에 의해 $(x, y) \in A \times B$이고 $(x, y) \in A \times C$이다. 앞쪽에서 정의 6.3에 의해 $x \in A$이고 $y \in B$를 얻고, 뒤쪽에서 $y \in C$를 얻는다. 그러면 $y \in B$이고 $y \in C$이므로 $y \in B \cap C$이고, $x \in A$이므로 정의 6.3에 의해 $(x, y) \in A \times (B \cap C)$이다. 양방향 포함이 성립하므로 $A \times (B \cap C) = (A \times B) \cap (A \times C)$이다. $\blacksquare$ 이번 증명은 표 없이 **산문**으로 적었다. 표는 연습 단계의 장치이고 실전의 증명은 처음부터 끝까지 이런 산문이다. 이 명제는 1권 28주차 예제 2.1과 같은 명제이지만, 그때는 논리식 번역을 앞세워 증명했고 여기서는 걸음 ②③④⑤를 따라 적었다. 같은 결과에 이르는 길이 두 개인 것이 아니라, 1권의 서식이 이번 주 절차의 집합 무대 사례였음이 드러난 것이다. ### 관찰 — 세 예제의 같은 뼈대 예제 2.1, 2.2, 2.3은 무대가 전부 다르지만 걸음의 배치가 같다. 대응표의 빈칸을 채워 보자. | **걸음** | **예제 2.1 (나눗셈)** | **예제 2.2 (합동)** | **예제 2.3 (곱)** | |---|---|---|---| | ② 전진면 | $b = ak$, $c = al$ | $a - b = ns$, $c - d = nt$ | $\underline{\quad(1)\quad}$ | | ③ 후진면 | $bx+cy$를 $a \times (\text{정수})$ 꼴로 | $\underline{\quad(2)\quad}$ | $(x,y)$가 우변의 두 좌표 조건을 갖췄음을 보이기 | | ④ 대수 | $a$로 묶기 | $bc$ 더하고 빼기 + $n$으로 묶기 | $\underline{\quad(3)\quad}$ | | ⑤ 자격 확인 | $kx + ly$가 정수 | $cs + bt$가 정수 | 두 좌표가 각각 해당 집합의 원소 | :::{container} quotebox **확인 20.** 빈칸 (1)~(3)을 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $(x, y)$에서 $x \in A$, $y \in B$, $y \in C$를 꺼낸다. (2) $ac - bd$를 $n \times (\text{정수})$ 꼴로 만든다. (3) "이고"의 묶음을 다시 배치한다 — $x \in A \wedge (y \in B \wedge y \in C)$를 $(x \in A \wedge y \in B) \wedge (x \in A \wedge y \in C)$로 재조립한다. 세 무대에서 걸음 ④의 도구만 다르다 — 대수의 묶기, 항의 쪼개기, 논리 연결의 재배치. ::: :::{container} quotebox **확인 21.** 세 예제에서 공통으로 반복된 순서를 다섯 걸음으로 적어 보자. 걸음 ③을 건너뛰면 세 예제 각각에서 무엇이 무너지는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 무대 확인 $\to$ ② 전진면 $\to$ ③ 후진면 $\to$ ④ 무대의 대수 $\to$ ⑤ 자격 확인과 선언. ③을 건너뛰면 예제 2.1에서는 $akx + aly$에서 멈춰 $a$로 묶을 이유를 찾지 못하고, 예제 2.2에서는 전개를 해 놓고도 그것이 도착점에 닿았는지 판정하지 못한 채 멈추며, 예제 2.3에서는 어느 방향의 포함을 증명 중인지 놓쳐 두 파트가 뒤섞인다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **무대 이동 절차** ① 무대 확인 — 명제의 이름이 어느 정의의 소관인지 지목한다 $\to$ ② 전진면 — 가정의 이름을 정의로 풀어 재료를 받는다 $\to$ ③ 후진면 — 목표의 이름을 정의로 풀어 만들어야 할 꼴을 먼저 적는다 $\to$ ④ 무대의 대수 — 재료를 그 꼴에 맞춰 조립한다 $\to$ ⑤ 자격 확인과 선언 — 요구된 자격을 밝히고 정의를 인용해 닫는다. ::: 무대가 바뀌어도 엔진은 같다. 바뀌는 것은 ①에서 지목하는 정의와 ④에서 쓰는 대수의 종류뿐이다. 이 절차는 C7주차의 반례$\cdot$귀류$\cdot$존재 증명에서도 뼈대로 남고, 거기서는 걸음 ③의 도착점이 "모순"이나 "증인"으로 갈릴 뿐이다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 베끼지 말고 빈칸만 스스로 채운다. 훈련이 진행될수록 빈칸이 커진다. 답은 §6에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식과 절차 빈칸 **Result.** 정수 $a$에 대해, $a \equiv 3 \pmod 5$이면 $a^2 \equiv 4 \pmod 5$이다. - $a \equiv 3 \pmod 5$라 하자. 합동의 $\underline{\quad(1)\quad}$ 보존을 반복 적용한 결과(거듭제곱 보존)에 의해 $a^2 \equiv 3^2 \pmod 5$이다. - $3^2 = 9$이고 $9 - 4 = 5$이므로 $9 \equiv \underline{\quad(2)\quad} \pmod 5$이다. - 두 합동식을 잇는 데 쓰는 성질은 (C1)~(C5) 중 $\underline{\quad(3)\quad}$이고, 그 결과 $a^2 \equiv 4 \pmod 5$이다. $\blacksquare$ - 이 계산의 핵심: 큰 수 $a^2$을 작은 대표 $3^2 = 9$로 갈아 끼운 뒤 그 대표를 다시 줄였다 — 합동을 $\underline{\quad(4)\quad}$처럼 다룰 수 있게 해 주는 것이 (C4)(C5)다. - 검산: $a = 8$은 $8 - 3 = 5$이므로 $a \equiv 3 \pmod 5$이다. $a^2 = 64$이고 $64 - 4 = 60 = 5 \times 12$이므로 $64 \equiv \underline{\quad(5)\quad} \pmod 5$ ✓. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 각 걸음의 근거 이름과 걸음 번호도 빈칸이다. **Result.** 정수 $a, b$와 양의 정수 $n$에 대해, $a \equiv b \pmod n$이면 $a^2 \equiv b^2 \pmod n$이다. - $a \equiv b \pmod n$이라 하자. 정의 6.2에 의해 $\underline{\quad(1)\quad}$이고, 정의 6.1에 의해 $a - b = ns$인 정수 $s$가 존재한다. 이 두 줄이 무대 이동 절차의 걸음 $\underline{\quad(2)\quad}$이고, 대는 근거는 $\underline{\quad(3)\quad}$이다. - 목표를 정의로 풀면 "$a^2 - b^2$이 $n \times (\text{정수})$ 꼴"이다. 이 줄이 걸음 ③이다. - $a^2 - b^2 = (a - b)(a + b) = \underline{\quad(4)\quad}$이다. - $s(a+b)$는 정수이므로(근거 $\underline{\quad(5)\quad}$) $n \mid (a^2 - b^2)$이고, 정의 6.2에 의해 $a^2 \equiv b^2 \pmod n$이다. $\blacksquare$ - 같은 결론을 (C5)에 $c = a$, $d = b$를 대입해 한 줄로 얻을 수도 있다. 이때 대는 근거는 $\underline{\quad(6)\quad}$이고, 인용 조건은 (C5)가 $\underline{\quad(7)\quad}$이다. ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 절차의 각 칸을 통째로 채운다. 무대는 곱과 차집합이 섞여 있다. **Result.** $A \times (B - C) = (A \times B) - (A \times C)$. - ① 무대 확인과 자료형, 양변의 논리식 번역: $\underline{\quad(1)\quad}$ - ② ($\subseteq$) 파트 — 첫 문장부터 마지막 문장까지: $\underline{\quad(2)\quad}$ - ③ ($\supseteq$) 파트 — 첫 문장부터 마지막 문장까지 (한 군데에서 "$x \notin A$ 또는 $y \notin C$" 중 하나를 배제하는 걸음이 필요하다): $\underline{\quad(3)\quad}$ - ④ 마무리 선언: $\underline{\quad(4)\quad}$ 이 훈련은 차집합이 붙는 좌표가 왼쪽이 아니라 오른쪽일 뿐 문제 17과 같은 뼈대다 — 좌표 위치만 바꾸면 문제 17이 된다. ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 이 순서가 답지 암기 습관을 끊는 장치다. 나눗셈$\cdot$합동 문제는 정의 전개를, 집합$\cdot$곱 문제는 원소 추적을 각 줄에 명시한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 근거가 점수다. 이번 주의 근거는 세 형태로 제출된다. ① 나눗셈$\cdot$합동 문제에서는 **정의를 몇 겹 풀었는지**가 점수다 — 합동은 정의 6.2와 6.1을 연이어 풀어야 등식이 나오고, "합동이므로 $a - b = ns$"라고 한 겹을 건너뛴 답안은 근거가 한 줄 비어 있다. ② 합동식을 변형한 줄에서는 **인용한 성질의 번호**가 점수다 — "양변에 곱하면"은 등식의 성질이 아니라 (C5)이고, 나누기는 어느 번호로도 인용할 수 없다(확인 8). ③ 집합$\cdot$곱 문제에서는 **몇 파트인지와 각 파트의 첫 문장**이 점수다 — 상등은 두 파트이고 각 파트는 자기 첫 문장으로 시작한다. 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 나눗셈 정의$\cdot$세 성질, 합동 정의$\cdot$대수 보존(덧셈$\cdot$곱셈$\cdot$거듭제곱), 데카르트 곱 정의를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 다섯 항목을 한 줄씩 순서대로 떠올리면 중간에서 끊긴다. 두 묶음으로 나눈다 — 무대를 여는 정의(6.1$\cdot$6.2$\cdot$6.3)와 그 무대에서 인용 가능한 정리((D1)~(D3), (C1)~(C5), 거듭제곱 보존)다. 묶음 이름이 서면 그 안의 항목이 따라 나온다. ::: **2.** 계산하시오 (합동 활용). (a) $3^{50} \pmod 4$ (b) $2^{10} \pmod 3$ (c) $123 \times 456 \pmod{10}$ (일의 자리) :::{admonition} 힌트 :class: quotebox dropdown 세 문제 모두 걸음은 같다 — 큰 수를 합동인 작은 대표로 갈아 끼운 뒤 (C5)나 거듭제곱 보존을 인용한다. (a)(b)는 대표를 $-1$로 잡으면 거듭제곱이 부호 계산으로 끝난다. (c)는 일의 자리가 법 10의 나머지라는 번역부터 한다. ::: **3.** 예제 2.1(선형결합)을 백지 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 다섯 걸음의 이름부터 세로로 적고 칸을 채운다. 걸음 ③("$a \times (\text{정수})$ 꼴을 만든다")을 적지 않으면 걸음 ④에서 무엇으로 묶을지가 나오지 않는다. ::: **4.** 빈칸 훈련을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 3이 막히면 ①만 먼저 적는다. 양변을 논리식으로 옮겨 나란히 두면 두 파트에서 각각 무엇을 도출해야 하는지가 보인다. ($\supseteq$) 방향에서 "또는" 하나를 배제하는 걸음은, 이미 손에 있는 사실 $x \in A$와 충돌하는 쪽을 지우는 일이다. ::: **5.** 예제 2.2(곱셈 보존)를 백지 재현하고 $7^{100} \pmod 4$를 계산하시오. :::{admonition} 힌트 :class: quotebox dropdown 재현에서 막히는 곳은 언제나 "$bc$를 더하고 빼기"다. 그 조작을 외우지 말고 도착점 $ac - bd$와 재료 $a-b$, $c-d$를 나란히 적어 보면, 두 재료를 한 번씩 쓰려면 중간에 무엇이 필요한지가 계산으로 나온다. ::: **6.** "$a \mid b$이고 $b \mid c$이면 $a \mid c$"(추이성)를 직접 증명하시오 (S3주차 문제 7의 재방문). :::{admonition} 힌트 :class: quotebox dropdown 정의를 두 번 푼다. 두 번째 등식의 좌변이 첫 번째 등식의 좌변과 다르다는 것이 열쇠다 — $b = ak$이고 $c = bl$이므로, $c$의 식에 $b$를 대입할 자리가 있다. ::: ### 표준 ●●○ **7.** 합동 덧셈 보존("$a \equiv b, c \equiv d \pmod n$이면 $a + c \equiv b + d$")을 증명하시오 (예제 2.2의 덧셈판). :::{admonition} 힌트 :class: quotebox dropdown 도착점은 $(a+c) - (b+d)$가 $n \times (\text{정수})$ 꼴임을 보이는 것이다. 이번에는 예제 2.2와 달리 항을 더하고 뺄 필요가 없다 — 도착점의 차를 재배열하면 재료 둘이 그대로 나온다. 왜 곱셈 쪽에서만 다리가 필요했는지도 함께 생각해 본다. ::: **8.** "정수 $a$에 대해, $a$가 홀수이면 $a^2 \equiv 1 \pmod 8$"을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 전개 후 $4k^2 + 4k$에서 4를 묶으면 $4k(k+1)$이 나온다. 남은 일은 $k(k+1)$이 짝수임을 대는 것이고, 그 사실은 1권 1주차 문제 16에서 경우 나누기로 증명되었다. ::: **9.** "$A \subseteq B$이면 $A \times C \subseteq B \times C$"를 증명하시오 (순서쌍 분해 + 선택법). :::{admonition} 힌트 :class: quotebox dropdown 목표가 포함이므로 파트는 하나이고 첫 문장은 "$(x, y) \in A \times C$라 하자"다. 가정 $A \subseteq B$는 원소 하나에 발동하는 재료다 — $x \in A$를 얻은 줄 바로 다음에 쓴다 (S7주차의 특수화). ::: **10.** 다음 제시된 증명을 평가하시오 (C5주차의 증명 평가 절차). :::{container} quotebox **Result.** 정수 $a, b$와 양의 정수 $n$에 대해, $a \equiv b \pmod n$이면 $a^2 \equiv b^2 \pmod n$. **제시된 증명.** $a \equiv b$이므로 $a = b$이다. 따라서 $a^2 = b^2$이라 $a^2 \equiv b^2$. ::: :::{admonition} 힌트 :class: quotebox dropdown C5주차의 평가 절차를 순서대로 돌린다. ① 명제 자체는 참인가 거짓인가를 먼저 판정한다 — 이 판정 결과에 따라 뒤의 지적이 "논증 결함"인지 "명제 자체가 거짓"인지 갈린다. 판정이 끝나면 결함이 있는 줄을 지목하고 반례로 뒷받침한다. ::: **11.** 정수 $a, b$에 대해 "$a \mid b$이고 $b \neq 0$이면 $\lvert a \rvert \le \lvert b \rvert$"를 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 이 문제의 진짜 걸음은 "$k \neq 0$"을 확보하는 자리다. $b \neq 0$에서 어떻게 $k \neq 0$이 나오는지 한 줄로 적는다. 그다음 "0이 아닌 정수의 절댓값은 1 이상"이 정수라는 자격에서 오는 사실임을 밝힌다. ::: **12.** 페르마 소정리 맛보기: $a^5 \equiv a \pmod 5$를 모든 $a \in \{0,1,2,3,4\}$에서 직접 확인하시오. 이것은 "$a^p \equiv a \pmod p$"의 $p = 5$ 사례다(C15주차 예고). :::{admonition} 힌트 :class: quotebox dropdown 다섯 값을 각각 계산하되, 계산마다 "몇에서 몇을 빼면 5의 배수인가"를 함께 적는다. 그것이 정의 6.2를 실제로 확인하는 줄이다. $4^5$은 $4 \equiv -1 \pmod 5$로 갈아 끼우면 값을 구하지 않고도 답이 나온다. ::: **13.** 데카르트 곱과 합집합: $A \times (B \cup C) = (A \times B) \cup (A \times C)$를 증명하시오 (예제 2.3의 합집합판 — 원소 추적, $\lor$ 처리). :::{admonition} 힌트 :class: quotebox dropdown 예제 2.3과 같은 두 파트 구조이고 다른 것은 "이고"가 "또는"으로 바뀐 것뿐이다. "또는"이 가정 쪽에 나타나면 경우로 쪼갠다(S15주차). 두 경우 각각에서 도착점에 이르는지 확인하고, 경우들이 전체를 덮는지도 한 줄로 밝힌다. ::: **14.** 나눗셈 무대의 대우 증명: "정수 $n$에 대해, $3 \nmid n^2$이면 $3 \nmid n$"을 증명하시오. 그 기법을 고른 이유도 함께 적으시오. :::{admonition} 힌트 :class: quotebox dropdown 원명제를 직접 시도하면 걸음 ②에서 막힌다 — "$3 \nmid n^2$"은 부정형이라 꺼낼 등식이 없다. 대우를 적으면 가정이 긍정형이 되어 정의가 즉시 풀린다. S12주차의 판정 신호("가정과 결론이 모두 부정형이면 대우")를 인용해 기법 선택의 이유까지 쓴다. ::: ### 도전 ●●● :::{admonition} 이 문제들이 빌려 쓰는 사실 :class: quotebox 문제 15는 "정수 $x$에 대해 $2 \mid x$이고 $3 \mid x$이면 $6 \mid x$"를 쓴다. 이 명제는 1권 20주차 문제 13에서 증명되었으므로 근거 ④로 인용한다. 일반적으로 "$m \mid x$이고 $n \mid x$이면 $mn \mid x$"는 **거짓**이다($m = n = 2$, $x = 2$가 반례다). 2와 3이 서로소라는 조건이 필요하고, 그 일반형은 C15주차의 몫이다. ::: **15.** (합동 대작) $n$이 양의 정수일 때 $n^3 \equiv n \pmod 6$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 도착점은 $6 \mid (n^3 - n)$이다. $n^3 - n$을 인수분해해 연속 세 정수의 곱으로 만든 뒤, 2의 배수임과 3의 배수임을 따로 확보한다. 3의 배수 쪽은 나눗셈 정리로 $n$을 세 경우로 나누면 매 경우 셋 중 누가 3의 배수인지 지목할 수 있다 (S15주차 문제 19). ::: :::{admonition} 십진 전개 표기 — 문제 16을 위한 도입 :class: quotebox 자연수 $n$의 십진 표기가 $d_m d_{m-1} \cdots d_1 d_0$이라는 것은 $n = \sum_{i=0}^{m} d_i 10^i$이라는 뜻이고, 각 $d_i$는 0 이상 9 이하의 정수다. 예를 들어 $n = 4703$이면 $4703 = 4 \cdot 10^3 + 7 \cdot 10^2 + 0 \cdot 10^1 + 3 \cdot 10^0$이다. 유한 개의 합에 (C4)를 반복 적용하는 것은 항의 개수에 대한 귀납이 필요하고, 그 형태의 반복은 1권 31주차에서 정당화되었으므로 여기서는 인용해 쓴다. ::: **16.** (자리합 판정 일반화) "정수 $n = \sum_{i} d_i 10^i$ (십진 전개)에 대해 $n \equiv \sum_i d_i \pmod 9$"를 증명하시오. 이어서 "$n$이 9의 배수인 것과 자리합이 9의 배수인 것은 동치이다"를 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 겹이다. 먼저 $10 \equiv 1 \pmod 9$을 정의로 확인하고, 거듭제곱 보존으로 $10^i \equiv 1$을 얻고, (C5)로 $d_i 10^i \equiv d_i$를 얻은 뒤 (C4)로 합친다. 마지막 "따라서" 문장은 별도의 논증이 필요하다 — $n$과 자리합의 차가 9의 배수라는 사실에서 두 배수 판정이 서로를 결정한다는 것은 예제 2.1의 (D2)로 나온다. ::: **17.** (집합 대수 종합) $(A - B) \times C = (A \times C) - (B \times C)$를 증명하시오 (차집합$\cdot$곱의 상호작용 — 원소 추적에서 "$x \in A$ $\land$ $x \notin B$"와 순서쌍 결합). :::{admonition} 힌트 :class: quotebox dropdown ($\supseteq$) 방향이 이 문제의 전부다. $(x,y) \notin B \times C$를 정의 6.3으로 풀면 "$x \notin B$ 또는 $y \notin C$"가 나온다(1권 11주차의 부정 규칙). 그런데 같은 줄에서 이미 $y \in C$를 확보했으므로 "또는"의 한쪽이 지워진다. ::: **18.** (진단 종합) 다음 제시된 증명을 평가하시오. :::{container} quotebox **Result.** 정수 $a, b, c$에 대해, $a \mid bc$이면 $a \mid b$ 또는 $a \mid c$. **제시된 증명.** $a \mid bc$이므로 $bc = ak$. 따라서 $a$가 $b$나 $c$ 중 하나를 나눈다. ::: :::{admonition} 힌트 :class: quotebox dropdown 증명의 줄을 검사하기 전에 평가 절차 ①을 먼저 돌린다. 명제가 거짓이면 어떤 논증도 옳을 수 없으므로, 반례 하나가 평가를 끝낸다. 반례를 찾을 때는 $bc$가 $a$의 배수가 되면서 $b$와 $c$ 각각은 $a$보다 작은 경우를 노린다. ::: **19.** (설계) "정수 $a$에 대해 $a^2 \equiv 0$ 또는 $1 \pmod 4$"를 합동으로 증명하시오. 이를 이용해 "$x^2 + y^2 = 3$인 정수 해가 없음"을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 앞부분은 네 경우를 나눈 뒤 각 경우에 거듭제곱 보존을 쓰면 끝난다. 경우가 전체를 덮는 근거는 나눗셈 정리다. 뒷부분은 등식 $x^2 + y^2 = 3$의 양변을 법 4에서 읽는 것이 전부다 — 같은 수는 어느 법에서도 자기 자신과 합동이므로((C1)), 좌변이 가질 수 있는 값의 집합과 우변의 값을 비교한다. ::: **20.** (서술) (a) 합동이 "등식처럼" 다뤄질 수 있는 이유(대수 보존 법칙)를 예제 2.2로 뒷받침하고, 그 덕에 큰 수 계산이 작은 대표로 환원됨을 세 문장 이내로. (b) "무대가 바뀌어도 엔진은 같다"(직접$\cdot$대우 + 정의 전개)를 나눗셈$\cdot$합동$\cdot$곱 세 무대로 두 문장 이내 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown (a)는 "무엇이 보존되고 무엇이 보존되지 않는가"를 함께 적어야 완결이다 — 확인 8이 그 경계다. (b)는 §1.6의 대조표에서 어느 칸이 무대마다 달라지고 어느 칸이 같은지를 한 문장으로 압축하면 나온다. ::: ## 백지 재현 — 복습 프로토콜 **이번 주의 5일 루틴.** 원서와 교안을 번갈아 쓰는 순서다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Chartrand 4장 통독 (모르는 문장은 표시만 하고 통과) | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다 | | 3일차 | 원서 재독 — 1일차에 표시한 문장을 해결하고, 원서 4장의 연습문제 몇 개를 직접 시도 | | 4일차 | 교안 §3 빈칸 사다리 + §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | 원서 4장은 절이 여럿이고 소재가 무대별로 흩어져 있다. 3일차 재독에서는 각 절의 Result마다 "이것은 §1.6 대조표의 어느 행인가"를 여백에 표시하며 읽는다. 표시가 끝나면 장 전체가 다섯 무대의 목록으로 정리된다. **1차 시도 — 틀 카드 허용.** 다음 세 상자만 옮겨 적은 카드를 펴 놓는다: 정의 6.1, 정의 6.2, 무대 이동 절차 다섯 걸음. 그 상태에서 예제 2.1과 예제 2.2를 처음부터 끝까지 적는다. 예제 본문과 확인 상자는 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 정의 6.1$\cdot$6.2$\cdot$6.3을 조각 그대로 백지에 썼다 ("정수 $k$가 존재한다"와 "양의 정수 $n$"까지). - [ ] (D1)~(D3)과 (C1)~(C5)를 쓰고, 각각이 이번 주 어디에서 증명되는지 표시했다. - [ ] 무대 이동 절차 다섯 걸음을 쓰고, 걸음 ③을 뺐을 때 무엇을 판정할 수 없게 되는지 한 사례로 적었다. - [ ] 예제 2.1(선형결합)$\cdot$2.2(곱 보존)$\cdot$2.3(곱의 분배)을 처음부터 끝까지 재현했다. - [ ] $7^{100} \pmod 4$를 계산하고, 어느 줄에서 (C5)나 거듭제곱 보존을 인용했는지 밝혔다. - [ ] 합동식에서 허용되는 조작과 허용되지 않는 조작을 각각 한 예로 들었다 (확인 8). - [ ] §1.6의 다섯 무대 대조표를 빈칸 없이 재현했다. - [ ] 원서 4장을 완독했고, 1일차에 표시한 문장이 전부 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 합동 문제에서 첫 줄 다음이 나오지 않는다 | §1.3 해부 표 — 정의가 두 겹이다. 6.2로 한 겹, 6.1로 한 겹 더 푼다 | | 식은 변형했는데 끝났는지 알 수 없다 | §1.4 걸음 ③ — 도착점을 먼저 적었는지 확인한다 | | 예제 2.2의 "더하고 빼기"가 떠오르지 않는다 | 확인 18 — 도착점과 재료를 나란히 적으면 무엇이 부족한지가 계산으로 나온다 | | 합동식을 나누거나 약분하게 된다 | 확인 8 — (C4)(C5)가 보장하는 것은 더하기와 곱하기뿐이다 | | 집합 상등 증명에서 두 파트가 뒤섞인다 | 예제 2.3과 1권 27주차 §1.4의 서식 표 — 파트마다 자기 첫 문장으로 연다 | | 곱 무대에서 무엇을 추적할지 모르겠다 | 정의 6.3 — 추적 대상은 원소이고, 이 무대의 원소는 순서쌍이다 | | 대우로 갈지 직접으로 갈지 판단이 안 된다 | 문제 14의 힌트와 S12주차의 판정 신호 — 가정이 부정형이면 꺼낼 등식이 없다 | 하나라도 실패하면 그 항목만 다시 적고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) 곱셈 (2) $4$ (3) (C3) 추이 (4) 등식 (5) $4$ ※ (3)이 이 훈련의 핵심이다. $a^2 \equiv 9$와 $9 \equiv 4$라는 두 합동식을 이어 $a^2 \equiv 4$를 얻는 일은 자동이 아니라 (C3)의 인용이다. 등식이라면 아무 말 없이 이었을 자리에서, 합동은 인용할 번호가 정해져 있다. (1)에서 "거듭제곱"이라고만 적었다면 절반이다 — 거듭제곱 보존은 (C5) 곱셈 보존을 반복 적용해 얻은 것이고, 그 출처(1권 31주차 문제 13)까지 대는 것이 완결이다. ### 빈칸 사다리 — 훈련 2 (1) $n \mid (a - b)$ (2) ② (3) ① 정의 (4) $ns(a+b)$ (5) ② 닫힘성 (6) ④ 이미 증명한 명제 (7) 이미 증명되어 있을 것 (1권 20주차 문제 17과 이 주차 예제 2.2) ※ (4)에서 인수분해 $a^2 - b^2 = (a-b)(a+b)$를 떠올리는 것이 걸음 ④의 전부다. 도착점이 "$a^2 - b^2$이 $n$의 배수"이고 재료가 "$a - b = ns$"이므로, $a^2 - b^2$ 안에서 $a - b$를 만들어 내는 변형을 찾게 된다. (6)(7)이 이 훈련에서 새로 요구되는 판정이다 — 같은 명제를 두 경로로 증명할 수 있을 때, 어느 경로를 택하든 인용하는 정리가 증명 완료 상태인지 확인하는 책임은 사라지지 않는다. ### 빈칸 사다리 — 훈련 3 (1) 무대는 데카르트 곱과 차집합이고, 원소의 자료형은 순서쌍 $(x, y)$다. 좌변 $(x,y) \in A \times (B - C)$는 "$x \in A$ 이고 ($y \in B$ 이고 $y \notin C$)"로, 우변 $(x,y) \in (A \times B) - (A \times C)$는 "($x \in A$ 이고 $y \in B$) 이고 ($x \notin A$ 또는 $y \notin C$)"로 번역된다. 우변의 뒷부분이 "또는"인 것은 $(x,y) \notin A \times C$를 부정 규칙으로 푼 결과다. (2) ($\subseteq$) $(x, y) \in A \times (B - C)$라 하자. 정의 6.3에 의해 $x \in A$이고 $y \in B - C$이다. 차집합의 정의에 의해 $y \in B$이고 $y \notin C$이다. $x \in A$이고 $y \in B$이므로 정의 6.3에 의해 $(x,y) \in A \times B$이다. 또 $y \notin C$이므로 $(x, y) \in A \times C$일 수 없다 — 만약 그렇다면 정의 6.3에 의해 $y \in C$가 되어 모순이다. 따라서 $(x,y) \in (A \times B) - (A \times C)$이다. (3) ($\supseteq$) $(x, y) \in (A \times B) - (A \times C)$라 하자. 차집합의 정의에 의해 $(x,y) \in A \times B$이고 $(x,y) \notin A \times C$이다. 앞쪽에서 정의 6.3에 의해 $x \in A$이고 $y \in B$이다. 뒤쪽을 정의 6.3과 부정 규칙으로 풀면 "$x \notin A$ 또는 $y \notin C$"인데, 이미 $x \in A$를 확보했으므로 앞쪽 선택지는 성립할 수 없고 $y \notin C$가 남는다. 그러면 $y \in B$이고 $y \notin C$이므로 $y \in B - C$이고, $x \in A$이므로 정의 6.3에 의해 $(x,y) \in A \times (B - C)$이다. (4) 양방향 포함이 성립하므로 $A \times (B - C) = (A \times B) - (A \times C)$이다. $\blacksquare$ ※ 이 훈련의 값은 (3)의 "또는 하나를 지우는" 걸음에 있다. 이미 손에 든 사실 $x \in A$가 선택지 하나와 충돌하므로 남은 하나가 확정된다. 걸음을 두 줄로 적으면 이렇다 — 경우 1: $x \notin A$ — 이미 확보한 $x \in A$와 모순이므로 이 경우는 일어나지 않는다. 경우 2: $y \notin C$ — 목표에 도달한다. 이 걸음의 이름은 **선언 삼단논법**이고, S15주차의 분류로는 한 케이스가 모순으로 배제되는 경우법이다. 소거법은 **결론**의 $\lor$에 붙는 도구이므로(S15주차 정의 15.2) 여기에는 쓰지 않는다 — 여기의 $\lor$는 결론이 아니라 이미 손에 든 사실, 곧 가정 쪽에 있다. ### 문제 1 **접근.** 다섯 항목을 순서대로 떠올리면 중간에서 끊긴다. 두 묶음으로 나눈다. 무대를 여는 **정의**(6.1 나눗셈, 6.2 합동, 6.3 곱)와 그 무대에서 인용 가능한 **정리**((D1)~(D3), (C1)~(C5), 거듭제곱 보존)다. 정의는 약속이라 외우고, 정리는 증명이 끝난 것만 인용한다는 구분까지가 이 문제의 답이다. **풀이.** 정의 6.1: 정수 $a, b$에 대해 $a \mid b$란 $b = ak$인 정수 $k$가 존재한다는 뜻이다. 성질 (D1) 추이 — $a \mid b$, $b \mid c$이면 $a \mid c$. (D2) 선형결합 — $a \mid b$, $a \mid c$이면 임의의 정수 $x, y$에 대해 $a \mid (bx+cy)$. (D3) 크기 — $a \mid b$, $b \neq 0$이면 $\lvert a \rvert \le \lvert b \rvert$. 정의 6.2: 정수 $a, b$와 양의 정수 $n$에 대해 $a \equiv b \pmod n$이란 $n \mid (a - b)$라는 뜻이다. 대수 (C1) 반사, (C2) 대칭, (C3) 추이, (C4) 합 보존 ($a \equiv b$, $c \equiv d$이면 $a + c \equiv b + d$), (C5) 곱 보존 (같은 가정에서 $ac \equiv bd$), 그리고 거듭제곱 보존 ($a \equiv b$이면 모든 자연수 $m$에 대해 $a^m \equiv b^m$). 정의 6.3: $A \times B = \{(x,y) : x \in A \text{ 이고 } y \in B\}$. **복기.** 백지 재현에서 빠지기 쉬운 조각은 정의 6.1의 "정수 $k$"와 정의 6.2의 "양의 정수 $n$"이다. 앞의 것은 빠지면 정의가 무너지고(확인 4), 뒤의 것은 빠지면 정의가 퇴화하거나 중복된다(§1.3의 삭제 실험 (가)~(다)). 조각이 하는 일을 이유와 함께 외우면 백지에서 복구가 가능하다. ### 문제 2 **접근.** 세 문제 모두 절차가 같다. 큰 수를 합동인 **작은 대표**로 갈아 끼운 뒤 (C5)나 거듭제곱 보존을 인용한다. 대표는 나머지일 필요가 없고 계산이 쉬운 쪽을 고른다 — 거듭제곱에서는 $-1$이 가장 쉽다. (c)의 "일의 자리"는 법 10의 나머지라는 번역부터 해야 합동 문제가 된다. **풀이.** (a) $3 - (-1) = 4$이고 $4 \mid 4$이므로 $3 \equiv -1 \pmod 4$이다. 거듭제곱 보존에 의해 $3^{50} \equiv (-1)^{50} \pmod 4$이고 $(-1)^{50} = 1$이므로 $3^{50} \equiv 1 \pmod 4$이다. 검산: $3^2 = 9 = 4 \times 2 + 1$이므로 $3^2 \equiv 1$이고, $3^{50} = (3^2)^{25} \equiv 1^{25} = 1 \pmod 4$ ✓. (b) $2 - (-1) = 3$이고 $3 \mid 3$이므로 $2 \equiv -1 \pmod 3$이다. 거듭제곱 보존에 의해 $2^{10} \equiv (-1)^{10} = 1 \pmod 3$이다. 검산: $2^{10} = 1024$이고 $1024 = 3 \times 341 + 1$이므로 나머지 1 ✓. (c) 일의 자리는 법 10의 나머지다. $123 - 3 = 120 = 10 \times 12$이므로 $123 \equiv 3 \pmod{10}$이고, $456 - 6 = 450 = 10 \times 45$이므로 $456 \equiv 6 \pmod{10}$이다. (C5)에 의해 $123 \times 456 \equiv 3 \times 6 = 18 \pmod{10}$ 이고, $18 - 8 = 10$이므로 (C3)에 의해 $123 \times 456 \equiv 8 \pmod{10}$이다. 곧 일의 자리는 8이다. 검산: $123 \times 456 = 56088$ ✓. **복기.** 세 계산 모두 "큰 수 $\to$ 작은 대표 $\to$ 계산 $\to$ 다시 줄이기"의 네 박자다. 마지막 "다시 줄이기"에서 (C3)을 인용하는 것을 빠뜨리기 쉽다. ### 문제 3 **접근.** 다섯 걸음의 이름을 세로로 적고 칸을 채우는 것부터 한다. 재현이 막히는 자리는 대개 걸음 ③이다 — 도착점 "$bx + cy = a \times (\text{정수})$"를 적어 두지 않으면 걸음 ④에서 무엇으로 묶을지가 나오지 않는다. **풀이.** 정수 $a, b, c$에 대해 $a \mid b$이고 $a \mid c$라 하자. 또 $x, y$를 임의의 정수라 하자. 정의 6.1에 의해 $b = ak$인 정수 $k$가 존재하고 $c = al$인 정수 $l$이 존재한다. 목표는 $bx + cy$를 "$a \times (\text{정수})$" 꼴로 만드는 것이다. 그러면 $$ bx + cy = (ak)x + (al)y = akx + aly = a(kx + ly) $$ 이고, $k, l, x, y$가 정수이므로 정수의 곱과 합인 $kx + ly$도 정수이다. 따라서 정의 6.1에 의해 $a \mid (bx + cy)$이다. $\blacksquare$ **복기.** 몫에 서로 다른 문자 $k, l$을 쓴 것이 이 증명의 설정 단계다. 같은 문자를 쓰면 $b = c$를 몰래 가정한 것이 되어 명제보다 좁은 것만 증명하게 된다. 검산: $a = 3$, $b = 6$, $c = 9$, $x = 2$, $y = -1$이면 $bx + cy = 12 - 9 = 3$이고 $3 \mid 3$ ✓. ### 문제 4 **접근.** 세 훈련은 지지대의 크기만 다르고 같은 절차를 돌린다. 훈련 1은 인용할 성질의 **번호**를 묻고, 훈련 2는 걸음 번호와 근거 번호를 함께 묻고, 훈련 3은 절차 전체를 통째로 요구한다. 훈련 3에서 막히면 ①만 먼저 적는다 — 양변을 논리식으로 옮겨 나란히 두면 두 파트에서 각각 무엇을 도출해야 하는지가 보인다. **풀이.** 훈련 1의 답은 (1) 곱셈 (2) $4$ (3) (C3) 추이 (4) 등식 (5) $4$이고, 핵심은 두 합동식을 잇는 자리에 (C3)을 인용해야 한다는 것이다. 훈련 2의 답은 (1) $n \mid (a-b)$ (2) ② (3) ① 정의 (4) $ns(a+b)$ (5) ② 닫힘성 (6) ④ (7) 증명 완료 상태이며, 핵심은 $a^2 - b^2 = (a-b)(a+b)$라는 인수분해가 "재료 $a-b$를 도착점 안에서 만들어 내는" 변형이라는 점이다. 훈련 3의 답은 위 사다리 해설의 (1)~(4)이고, 핵심은 ($\supseteq$) 방향에서 "$x \notin A$ 또는 $y \notin C$" 중 앞쪽을 $x \in A$로 지우는 선언 삼단논법의 걸음이다. **복기.** 세 훈련의 채점은 빈칸의 값이 아니라 **인용한 번호**로 한다. 값이 맞아도 근거 번호가 비어 있으면 백지 재현에서 그 줄이 복구되지 않는다. ### 문제 5 **접근.** 재현에서 막히는 곳은 언제나 "$bc$를 더하고 빼기"다. 그 조작을 외우지 말고, 도착점 $ac - bd$와 재료 $a - b$, $c - d$를 나란히 적어 본다. 두 재료를 한 번씩 쓰려면 $ac$와 $bd$ 사이에 다리가 되는 항이 필요하고, 그 항은 $a$와 $c$ 중 하나를 $b$나 $d$로 바꾼 $bc$(또는 $ad$)다. **풀이.** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이라 하자. 정의 6.2에 의해 $n \mid (a - b)$이고 $n \mid (c - d)$이며, 정의 6.1에 의해 $a - b = ns$, $c - d = nt$인 정수 $s, t$가 존재한다. 목표는 $ac - bd$를 "$n \times (\text{정수})$" 꼴로 만드는 것이다. 그러면 $$ ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = c(ns) + b(nt) = n(cs + bt) $$ 이고, $b, c, s, t$가 정수이므로 $cs + bt$도 정수이다. 따라서 $n \mid (ac - bd)$이고, 정의 6.2에 의해 $ac \equiv bd \pmod n$이다. $\blacksquare$ 계산: $7 - (-1) = 8 = 4 \times 2$이므로 $7 \equiv -1 \pmod 4$이다. 거듭제곱 보존에 의해 $7^{100} \equiv (-1)^{100} = 1 \pmod 4$이다. **복기.** 같은 자리에 $ad$를 더하고 빼도 된다 — $ac - bd = ac - ad + ad - bd = a(c-d) + d(a-b)$이고 결론은 같다. 다리의 선택지가 둘이라는 것은, 그 조작이 기교가 아니라 도착점이 요구한 계산이라는 증거다. 검산: $n = 5$, $a = 7 \equiv 2$, $b = 2$, $c = 8 \equiv 3$, $d = 3$이면 $ac = 56 \equiv 1$, $bd = 6 \equiv 1 \pmod 5$ ✓. ### 문제 6 **접근.** 무대는 나눗셈이고 정의를 두 번 푼다. 열쇠는 두 등식의 좌변이 다르다는 것이다 — $b = ak$이고 $c = bl$이므로 둘째 등식 안의 $b$에 첫째 등식을 대입할 자리가 있다. 도착점은 "$c = a \times (\text{정수})$"이므로 대입 후 $a$로 묶으면 끝난다. **풀이.** 정수 $a, b, c$에 대해 $a \mid b$이고 $b \mid c$라 하자. 정의 6.1에 의해 $b = ak$인 정수 $k$가 존재하고, $c = bl$인 정수 $l$이 존재한다. 목표는 $c$를 "$a \times (\text{정수})$" 꼴로 만드는 것이다. 그러면 $$ c = bl = (ak)l = a(kl) $$ 이고, $k, l$이 정수이므로 $kl$도 정수이다. 따라서 정의 6.1에 의해 $a \mid c$이다. $\blacksquare$ 이로써 (D1)이 증명되었으므로 이후 근거 ④로 인용할 수 있다. **복기.** 이 증명에는 숫자가 하나도 나오지 않는다. 1권 2주차 예제 2.1이 이것을 "첫 추상 증명"이라 부른 이유가 그것이고, S3주차 문제 7은 같은 명제를 전진$\cdot$후진의 만남 지점을 표시하며 분석했다. 검산: $a = 2$, $b = 6$, $c = 18$이면 $2 \mid 6$, $6 \mid 18$, 그리고 $18 = 2 \times 9$이므로 $2 \mid 18$ ✓. ### 문제 7 **접근.** 도착점은 $(a+c) - (b+d)$가 "$n \times (\text{정수})$" 꼴임을 보이는 것이다. 예제 2.2와 달리 항을 더하고 뺄 필요가 없다 — 도착점의 차를 재배열하기만 하면 재료 $a - b$와 $c - d$가 그대로 나온다. 덧셈은 항끼리 자유롭게 모을 수 있지만 곱셈은 그렇지 않다는 것이, 곱 보존에서만 다리가 필요했던 이유다. **풀이.** $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이라 하자. 정의 6.2에 의해 $n \mid (a-b)$이고 $n \mid (c-d)$이며, 정의 6.1에 의해 $a - b = ns$, $c - d = nt$인 정수 $s, t$가 존재한다. 목표는 $(a+c) - (b+d)$를 "$n \times (\text{정수})$" 꼴로 만드는 것이다. 그러면 $$ (a + c) - (b + d) = (a - b) + (c - d) = ns + nt = n(s + t) $$ 이고, $s, t$가 정수이므로 $s + t$도 정수이다. 따라서 $n \mid ((a+c) - (b+d))$이고, 정의 6.2에 의해 $a + c \equiv b + d \pmod n$이다. $\blacksquare$ **복기.** 같은 결론을 (D2)로 얻을 수도 있다 — $n \mid (a-b)$이고 $n \mid (c-d)$이므로 $x = y = 1$인 선형결합에 의해 $n \mid ((a-b) + (c-d))$이다. 나눗셈의 정리 하나가 합동의 정리 하나를 바로 낳는 것은 합동의 정의가 나눗셈으로 되어 있기 때문이다. 검산: $n = 5$, $7 \equiv 2$, $8 \equiv 3$이면 $15 \equiv 5 \equiv 0 \pmod 5$ ✓. ### 문제 8 **접근.** 무대는 합동이지만 가정은 홀수라는 짝수$\cdot$홀수 무대의 이름이다. 그러므로 걸음 ②는 홀수의 정의를 풀고, 걸음 ③은 합동의 정의를 풀어 "$a^2 - 1$이 8의 배수"로 도착점을 옮긴다. 전개 후 4를 묶으면 $4k(k+1)$이 되고, 남은 일은 $k(k+1)$이 짝수임을 대는 것이다. **풀이.** $a$를 홀수라 하자. 정의에 의해 $a = 2k + 1$인 정수 $k$가 존재한다. 목표는 $a^2 - 1$이 "$8 \times (\text{정수})$" 꼴임을 보이는 것이다. 그러면 $$ a^2 - 1 = (2k+1)^2 - 1 = 4k^2 + 4k + 1 - 1 = 4k^2 + 4k = 4k(k+1) $$ 이다. 연속한 두 정수의 곱 $k(k+1)$은 짝수이므로(1권 1주차 문제 16 — 근거 ④), $k(k+1) = 2m$인 정수 $m$이 존재한다. 따라서 $$ a^2 - 1 = 4 \cdot 2m = 8m $$ 이고 $m$은 정수이므로 정의 6.1에 의해 $8 \mid (a^2 - 1)$이다. 곧 정의 6.2에 의해 $a^2 \equiv 1 \pmod 8$이다. $\blacksquare$ **복기.** 4를 묶은 뒤 "$k(k+1)$에서 2가 하나 더 나온다"를 알아채는 것이 이 증명의 전부다. 같은 리듬이 1권 1주차 문제 17(홀수의 제곱에서 1을 뺀 것이 8의 배수)에서 이미 쓰였고, 1권 17주차 문제 15는 같은 결과를 "나머지가 1"이라는 나눗셈의 언어로 적었다 — 이번 문제는 그것을 합동 표기로 옮긴 것이다. 1권 20주차 문제 18은 이 결과를 합동 언어로 재진술해 두 홀수의 제곱합이 법 8에서 2와 합동임을 얻는다. 검산: $a = 5$이면 $a^2 - 1 = 24 = 8 \times 3$ ✓. $a = 7$이면 $48 = 8 \times 6$ ✓. ### 문제 9 **접근.** 목표가 포함 하나이므로 파트는 하나이고, 첫 문장은 "$(x, y) \in A \times C$라 하자"다. 가정 $A \subseteq B$는 명제가 아니라 **원소 하나에 발동하는 재료**다 — $x \in A$를 손에 넣은 줄 바로 다음에 발동한다(S7주차의 특수화). **풀이.** $A \subseteq B$라 하자. $(x, y) \in A \times C$를 임의로 잡자. 정의 6.3에 의해 $x \in A$이고 $y \in C$이다. $A \subseteq B$이므로 $x \in A$에서 $x \in B$를 얻는다. 그러면 $x \in B$이고 $y \in C$이므로, 정의 6.3에 의해 $(x, y) \in B \times C$이다. 임의로 잡은 원소가 $B \times C$에 속했으므로 $A \times C \subseteq B \times C$이다. $\blacksquare$ **복기.** 이 명제의 역("$A \times C \subseteq B \times C$이면 $A \subseteq B$")은 일반적으로 거짓이다 — $C = \emptyset$이면 양변이 모두 공집합이라 포함이 공짜로 성립하지만 $A \subseteq B$일 이유가 없다. 1권 28주차 문제 17이 이 쌍을 다룬다. 곱 무대에서 공집합이 만드는 예외는 이후에도 반복해서 등장한다. ### 문제 10 **접근.** C5주차의 평가 절차를 순서대로 돌린다. ① 명제 자체는 참인가 — 참이다 (훈련 2에서 증명했다). 명제가 참이므로 결함은 논증에 있고, ② 각 줄이 앞 줄에서 따라오는지를 검사하면 첫 줄에서 결함이 발견된다. 판정은 "틀림(어느 줄, 왜)"이며, 반례로 그 줄이 성립하지 않음을 뒷받침한 뒤 올바른 증명을 제시한다. **풀이.** **틀림 — 첫 줄이 오류다.** "$a \equiv b \pmod n$이므로 $a = b$이다"는 근거 없는 비약이다. 합동은 상등이 아니라 "차가 $n$의 배수"라는 관계이므로 $a \neq b$인 합동 쌍이 얼마든지 있다 — $3 \equiv 8 \pmod 5$이지만 $3 \neq 8$이다. 이 줄이 성립한다면 법 $n$의 합동은 상등과 같아지고 §1.2의 나머지 계산도 무의미해진다. 명제 자체는 참이므로 판정은 "명제는 참이나 제시된 증명은 틀림"이다. 올바른 증명: $a, b$를 정수, $n$을 양의 정수라 하고 $a \equiv b \pmod n$이라 하자. 정의 6.2와 6.1에 의해 $a - b = ns$인 정수 $s$가 존재한다. 그러면 $$ a^2 - b^2 = (a - b)(a + b) = ns(a+b) $$ 이고 $s(a+b)$는 정수이므로 $n \mid (a^2 - b^2)$, 곧 $a^2 \equiv b^2 \pmod n$이다. $\blacksquare$ (또는 (C5)에 $c = a$, $d = b$를 대입해 한 줄로 얻는다.) **복기.** 결론이 참인 증명에도 틀린 줄이 있을 수 있다. 평가 절차 ①에서 "명제가 참"이 나왔다고 평가가 끝나는 것이 아니라, 거기서부터 줄 검사가 시작된다. ### 문제 11 **접근.** 정의를 풀면 $b = ak$가 나오고 절댓값을 씌우면 $\lvert b \rvert = \lvert a \rvert \lvert k \rvert$이다. 이 문제의 진짜 걸음은 "$k \neq 0$"을 확보하는 자리다 — $b \neq 0$이라는 가정이 여기서 소비된다. 그리고 "0이 아닌 정수의 절댓값은 1 이상"이라는 사실은 $k$가 **정수**라는 자격에서 온다. **풀이.** 정수 $a, b$에 대해 $a \mid b$이고 $b \neq 0$이라 하자. 정의 6.1에 의해 $b = ak$인 정수 $k$가 존재한다. 만약 $k = 0$이면 $b = a \cdot 0 = 0$이 되어 가정 $b \neq 0$에 어긋나므로 $k \neq 0$이다. $k$는 0이 아닌 정수이므로 $\lvert k \rvert \ge 1$이다. 여기서 쓰는 절댓값의 곱셈 성질 $\lvert xy \rvert = \lvert x \rvert \lvert y \rvert$는 §1.7의 네 칸 어디에도 없는 실수의 기본 성질이므로, 근거 목록을 늘리지 않고 이 한 줄에서 인정하고 쓴다. 그러면 $$ \lvert b \rvert = \lvert ak \rvert = \lvert a \rvert \lvert k \rvert \ge \lvert a \rvert \cdot 1 = \lvert a \rvert $$ 이다. 따라서 $\lvert a \rvert \le \lvert b \rvert$이다. $\blacksquare$ **복기.** 부등식으로 넘어가는 마지막 줄에서 $\lvert a \rvert \ge 0$이 필요하다 — $\lvert a \rvert \lvert k \rvert \ge \lvert a \rvert \cdot 1$은 음이 아닌 수를 곱할 때만 방향이 보존되기 때문이다. 이 성질은 (D3)이 되었으므로 이후 인용할 수 있다. 쓸모: 어떤 수의 약수를 찾을 때 그 수보다 큰 후보를 검사할 필요가 없다는 보장이 여기서 나온다. 검산: $3 \mid 12$이고 $3 \le 12$ ✓. $-4 \mid 8$이고 $4 \le 8$ ✓. ### 문제 12 **접근.** 다섯 값을 각각 계산하되, 계산마다 "몇에서 몇을 빼면 5의 배수인가"를 함께 적는다. 그것이 정의 6.2를 실제로 확인하는 줄이다. $4^5$은 값이 크므로 $4 \equiv -1 \pmod 5$로 갈아 끼우면 값을 구하지 않고 답이 나온다. **풀이.** $a = 0$: $0^5 = 0$이고 $0 - 0 = 0 = 5 \times 0$이므로 $0^5 \equiv 0 \pmod 5$. $a = 1$: $1^5 = 1$이고 $1 - 1 = 0$이므로 $1^5 \equiv 1 \pmod 5$. $a = 2$: $2^5 = 32$이고 $32 - 2 = 30 = 5 \times 6$이므로 $2^5 \equiv 2 \pmod 5$. $a = 3$: $3^5 = 243$이고 $243 - 3 = 240 = 5 \times 48$이므로 $3^5 \equiv 3 \pmod 5$. $a = 4$: $4 - (-1) = 5$이므로 $4 \equiv -1 \pmod 5$이고, 거듭제곱 보존에 의해 $4^5 \equiv (-1)^5 = -1 \equiv 4 \pmod 5$이다. 값으로 확인하면 $4^5 = 1024$이고 $1024 - 4 = 1020 = 5 \times 204$이다. 다섯 나머지 전부에서 $a^5 \equiv a \pmod 5$가 성립한다. $\blacksquare$ **복기.** 임의의 정수 $a$는 법 5에서 이 다섯 값 중 하나와 합동이므로(나눗셈 정리), 다섯 경우의 확인이 곧 모든 정수에 대한 확인이 된다 — 유한 개의 경우로 무한 개를 덮는 것이 합동 계산의 실제 이득이다. 다만 그 이월에도 인용할 번호가 있다: $a \equiv r \pmod 5$이면 거듭제곱 보존에 의해 $a^5 \equiv r^5$이고, 위에서 확인한 $r^5 \equiv r$과 (C3)으로 이어 $a^5 \equiv r$을 얻으며, (C2)로 $r \equiv a$를 붙인 뒤 다시 (C3)을 쓰면 $a^5 \equiv a$가 된다. 일반형 "$a^p \equiv a \pmod p$"(페르마의 소정리)는 C15주차의 몫이다. $a = 4$의 처리가 보여 주듯, 대표를 음수로 잡으면 거듭제곱이 부호 계산으로 줄어든다. ### 문제 13 **접근.** 예제 2.3과 두 파트 구조가 같고 다른 것은 "이고"가 "또는"으로 바뀐 것뿐이다. "또는"이 가정 쪽에 나타나면 경우로 쪼갠다(S15주차의 경우법). 두 경우 각각에서 도착점에 이르는지 확인하고, 경우들이 전체를 덮는지도 한 줄로 밝힌다. **풀이.** ($\subseteq$) $(x, y) \in A \times (B \cup C)$라 하자. 정의 6.3에 의해 $x \in A$이고 $y \in B \cup C$이므로, 합집합의 정의에 의해 $y \in B$ 또는 $y \in C$이다. 경우 1: $y \in B$. 그러면 $x \in A$이고 $y \in B$이므로 정의 6.3에 의해 $(x,y) \in A \times B$이다. 경우 2: $y \in C$. 그러면 $x \in A$이고 $y \in C$이므로 정의 6.3에 의해 $(x,y) \in A \times C$이다. 두 경우가 전체를 덮고 어느 경우든 $(x,y)$가 두 집합 중 하나에 속하므로 $(x,y) \in (A \times B) \cup (A \times C)$이다. ($\supseteq$) $(x, y) \in (A \times B) \cup (A \times C)$라 하자. 합집합의 정의에 의해 $(x,y) \in A \times B$ 또는 $(x,y) \in A \times C$이다. 앞의 경우 정의 6.3에 의해 $x \in A$이고 $y \in B$이므로 $y \in B \cup C$이고, 뒤의 경우 $x \in A$이고 $y \in C$이므로 역시 $y \in B \cup C$이다. 어느 경우든 $x \in A$이고 $y \in B \cup C$이므로 정의 6.3에 의해 $(x,y) \in A \times (B \cup C)$이다. 양방향 포함이 성립하므로 $A \times (B \cup C) = (A \times B) \cup (A \times C)$이다. $\blacksquare$ **복기.** 경우 나누기의 채점 기준은 두 가지다 — ① 경우들이 전체를 빠짐없이 덮는가 ② 각 경우가 각각 완결되는가. 여기서는 합집합의 정의가 "또는"을 그대로 주므로 ①이 공짜이고, ②만 확인하면 된다. 예제 2.3에서 "이고"였던 자리가 "또는"이 되자 파트마다 경우가 둘로 늘었을 뿐 걸음의 배치는 그대로다. ### 문제 14 **접근.** 원명제를 직접 시도하면 걸음 ②에서 막힌다 — "$3 \nmid n^2$"은 부정형이라 꺼낼 등식이 없다. S12주차의 판정 신호에 따라 대우로 돌린다. 대우 "$3 \mid n$이면 $3 \mid n^2$"은 가정이 긍정형이라 정의가 즉시 풀린다. **풀이.** 원명제의 대우는 "$3 \mid n$이면 $3 \mid n^2$"이다. 이것을 직접 증명한다. $3 \mid n$이라 하자. 정의 6.1에 의해 $n = 3k$인 정수 $k$가 존재한다. 목표는 $n^2$을 "$3 \times (\text{정수})$" 꼴로 만드는 것이다. 그러면 $$ n^2 = (3k)^2 = 9k^2 = 3(3k^2) $$ 이고 $3k^2$은 정수이므로 정의 6.1에 의해 $3 \mid n^2$이다. 대우가 증명되었고 조건문은 대우와 논리적으로 동치이므로(C3주차), 원명제 "$3 \nmid n^2$이면 $3 \nmid n$"이 성립한다. $\blacksquare$ **복기.** 기법 선택의 이유를 답안에 적는 것까지가 이 문제의 요구다. 가정이 부정형이면 걸음 ②의 공급처가 비어 있고, 대우를 취하면 부정이 결론 쪽으로 옮겨 가면서 가정 자리에 긍정형이 들어온다. 같은 신호가 1권 19주차와 S12주차에서 반복해서 쓰였다. ### 문제 15 **접근.** 도착점은 $6 \mid (n^3 - n)$이다. $n^3 - n$을 인수분해해 연속 세 정수의 곱으로 만든 뒤, 2의 배수임과 3의 배수임을 따로 확보하고 마지막에 합친다. 3의 배수 쪽은 나눗셈 정리로 $n$을 세 경우로 나누면 매 경우 셋 중 누가 3의 배수인지 지목할 수 있다. **풀이.** $n$을 양의 정수라 하자. 목표는 $n^3 - n$이 "$6 \times (\text{정수})$" 꼴임을 보이는 것이다. 먼저 인수분해하면 $$ n^3 - n = n(n^2 - 1) = (n-1)n(n+1) $$ 이다. **2의 배수임.** $n(n+1)$은 연속한 두 정수의 곱이므로 짝수이고(1권 1주차 문제 16), $n(n+1) = 2u$인 정수 $u$가 존재한다. 그러면 $(n-1)n(n+1) = (n-1) \cdot 2u = 2\big((n-1)u\big)$ 이고 $(n-1)u$는 정수이므로 $2 \mid (n^3 - n)$이다. **3의 배수임.** 나눗셈 정리에 의해 $n = 3q$, $n = 3q+1$, $n = 3q+2$ 중 하나인 정수 $q$가 존재한다. $n = 3q$이면 $n$ 자신이 3의 배수이고, $n = 3q+1$이면 $n - 1 = 3q$가 3의 배수이며, $n = 3q+2$이면 $n + 1 = 3q + 3 = 3(q+1)$이 3의 배수다 (S15주차 문제 19). 어느 경우든 세 인수 중 하나가 $3 \times (\text{정수})$ 꼴이므로, 그 인수를 대입해 나머지 두 인수와 묶으면 $(n-1)n(n+1) = 3 \times (\text{정수})$가 되어 $3 \mid (n^3 - n)$이다. **합치기.** $2 \mid (n^3-n)$이고 $3 \mid (n^3-n)$이므로, 1권 20주차 문제 13에 의해 $6 \mid (n^3 - n)$이다. 따라서 정의 6.2에 의해 $n^3 \equiv n \pmod 6$이다. $\blacksquare$ **복기.** S17주차 문제 13이 같은 명제를 "$n^3 - n$이 6의 배수"라는 나눗셈의 언어로 다뤘고, 이번 문제는 그것을 합동으로 재서술한 것이다. "2의 배수이고 3의 배수이면 6의 배수"는 2와 3이 서로소이기에 성립하는 것이지 일반 법칙이 아니다(§4 도입 상자). 이 문제의 뼈대 — 큰 법을 서로소인 작은 법들로 쪼개 각각에서 확인하고 합치기 — 는 C15주차에서 중국인 나머지 정리라는 이름을 얻는다. 검산: $n = 4$이면 $n^3 - n = 60 = 6 \times 10$ ✓. $n = 5$이면 $120 = 6 \times 20$ ✓. ### 문제 16 **접근.** 세 겹이다. 먼저 $10 \equiv 1 \pmod 9$을 정의로 확인하고, $i \ge 1$에서는 거듭제곱 보존으로 $10^i \equiv 1$을 얻고($i = 0$은 (C1)로 따로 처리한다), (C5)로 $d_i 10^i \equiv d_i$를 얻은 뒤 (C4)로 항을 합친다. 마지막 "따라서 9의 배수 판정" 문장은 별도의 논증이 필요하다 — 합동식 하나에서 두 배수 판정이 서로를 결정한다는 것은 (D2)로 나온다. **풀이.** $n = \sum_{i=0}^{m} d_i 10^i$이라 하자. ① $10 - 1 = 9$이고 $9 \mid 9$이므로 정의 6.2에 의해 $10 \equiv 1 \pmod 9$이다. ② $i = 0$일 때는 $10^0 = 1$이므로 (C1)에 의해 $10^0 \equiv 1 \pmod 9$이다. $i \ge 1$일 때는 거듭제곱 보존에 의해 $10^i \equiv 1^i = 1 \pmod 9$이다. 두 경우를 나누는 이유는 §1.5의 거듭제곱 보존이 자연수 지수에 대한 진술이고 이 과정의 자연수는 0을 제외하기 때문이다(1권 3주차의 기호 표). 십진 전개에는 $d_0 \cdot 10^0$ 항이 반드시 있으므로 $i = 0$은 실제로 쓰이는 경우다. ③ (C1)에 의해 $d_i \equiv d_i \pmod 9$이므로, ②와 함께 (C5)를 적용하면 $d_i 10^i \equiv d_i \cdot 1 = d_i \pmod 9$이다. ④ ③의 합동식 $m+1$개에 (C4)를 반복 적용하면 $$ n = \sum_{i=0}^{m} d_i 10^i \equiv \sum_{i=0}^{m} d_i \pmod 9 $$ 이다. 곧 $9 \mid \left(n - \sum_i d_i\right)$이다. ⑤ 자리합을 $S = \sum_i d_i$라 두자. $9 \mid (n - S)$이다. $9 \mid n$이면 $9 \mid n$과 $9 \mid (n-S)$에 (D2)를 $x = 1$, $y = -1$로 적용해 $9 \mid \big(n - (n - S)\big) = S$를 얻는다. 거꾸로 $9 \mid S$이면 $9 \mid S$와 $9 \mid (n-S)$에 (D2)를 $x = y = 1$로 적용해 $9 \mid n$을 얻는다. 따라서 $n$이 9의 배수인 것과 자리합이 9의 배수인 것은 서로 동치이다. $\blacksquare$ **복기.** 판정법의 엔진은 $10 \equiv 1 \pmod 9$ 한 줄이다. 법 3에서도 $10 \equiv 1$이 성립하므로 같은 논증이 3의 배수 판정법을 준다 — C4주차 문제 19가 두 자리 수에서 증명한 특성화의 일반형이 이것이다. 법 11에서는 $10 \equiv -1$이므로 자리합 대신 교대합 판정법이 나온다. 검산: $n = 4703$이면 자리합은 $4+7+0+3 = 14$이고 둘 다 9의 배수가 아니다. $n = 4707$이면 자리합 18이 9의 배수이고 $4707 = 9 \times 523$ ✓. ### 문제 17 **접근.** ($\supseteq$) 방향이 이 문제의 전부다. $(x,y) \notin B \times C$를 정의 6.3으로 풀면 "$x \in B$이고 $y \in C$"의 부정이므로, 부정 규칙에 의해 "$x \notin B$ 또는 $y \notin C$"가 나온다. 그런데 같은 줄에서 이미 $y \in C$를 확보했으므로 "또는"의 뒤쪽이 지워지고 $x \notin B$가 확정된다. **풀이.** ($\subseteq$) $(x, y) \in (A - B) \times C$라 하자. 정의 6.3에 의해 $x \in A - B$이고 $y \in C$이며, 차집합의 정의에 의해 $x \in A$이고 $x \notin B$이다. $x \in A$이고 $y \in C$이므로 정의 6.3에 의해 $(x,y) \in A \times C$이다. 또 $(x,y) \in B \times C$라면 정의 6.3에 의해 $x \in B$가 되어 $x \notin B$에 어긋나므로 $(x,y) \notin B \times C$이다. 따라서 차집합의 정의에 의해 $(x,y) \in (A \times C) - (B \times C)$이다. ($\supseteq$) $(x, y) \in (A \times C) - (B \times C)$라 하자. 차집합의 정의에 의해 $(x,y) \in A \times C$이고 $(x,y) \notin B \times C$이다. 앞쪽에서 정의 6.3에 의해 $x \in A$이고 $y \in C$이다. 뒤쪽을 정의 6.3과 부정 규칙으로 풀면 "$x \notin B$ 또는 $y \notin C$"인데, 이미 $y \in C$이므로 뒤쪽 선택지는 성립할 수 없고 $x \notin B$가 남는다. 그러면 $x \in A$이고 $x \notin B$이므로 $x \in A - B$이고, $y \in C$이므로 정의 6.3에 의해 $(x,y) \in (A - B) \times C$이다. 양방향 포함이 성립하므로 $(A - B) \times C = (A \times C) - (B \times C)$이다. $\blacksquare$ **복기.** "또는"에서 한쪽을 지워 다른 쪽을 확정하는 걸음의 이름은 **선언 삼단논법**이고, S15주차의 분류로는 한 케이스가 모순으로 배제되는 경우법이다. 걸음을 두 줄로 적으면 이렇다 — 경우 1: $x \notin B$ — 목표에 도달한다. 경우 2: $y \notin C$ — 이미 확보한 $y \in C$와 모순이므로 이 경우는 일어나지 않는다. S15주차의 소거법은 **결론**의 $\lor$에 붙는 도구이므로 여기에는 쓰지 않는다(정의 15.2) — 여기의 $\lor$는 결론이 아니라 이미 손에 든 사실이다. 집합 무대에서 부정이 등장하면 거의 언제나 이 걸음이 따라온다. 검산: $A = \{1,2\}$, $B = \{2\}$, $C = \{9\}$이면 좌변은 $\{(1,9)\}$이고, 우변은 $\{(1,9),(2,9)\} - \{(2,9)\} = \{(1,9)\}$ ✓. ### 문제 18 **접근.** 증명의 줄을 검사하기 전에 평가 절차 ①을 먼저 돌린다. 명제가 거짓이면 어떤 논증도 옳을 수 없으므로 반례 하나가 평가를 끝낸다. 반례는 $bc$가 $a$의 배수가 되면서 $b$와 $c$ 각각은 $a$보다 작은 경우를 노리면 나온다 — (D3)에 의해 $a$보다 작은 0이 아닌 수는 $a$로 나누어지지 않기 때문이다. **풀이.** **틀림 — 명제 자체가 거짓이다.** 평가 절차 ①에서 이미 탈락한다. 반례: $a = 4$, $b = 2$, $c = 2$. 이때 $bc = 4$이고 $4 = 4 \times 1$이므로 $4 \mid bc$가 성립한다. 그러나 $2 = 4k$인 정수 $k$는 없으므로($k = 0.5$는 정수가 아니다) $4 \nmid 2$이고, $b$와 $c$ 어느 쪽도 4로 나누어지지 않는다. 따라서 명제는 거짓이다. 제시된 증명의 결함도 지적할 수 있다. 첫 줄 "$a \mid bc$이므로 $bc = ak$"는 정의 6.1의 정확한 적용이라 옳다. 둘째 줄 "따라서 $a$가 $b$나 $c$ 중 하나를 나눈다"가 근거 없는 비약이다 — $bc = ak$라는 등식은 $a$의 인수가 $b$와 $c$에 어떻게 흩어져 있는지에 대해 아무것도 말하지 않는다. 반례에서는 $a = 4$의 인수 2가 $b$와 $c$에 하나씩 나뉘어 들어가 있어 어느 쪽도 4를 채우지 못한다. 이 성질은 $a$가 **소수**일 때만 참이고, 그것이 유클리드 보조정리다 (S15주차 문제 10). 제시된 명제는 그 조건이 누락된 형태다. **복기.** 조건이 하나 빠진 거짓 명제는 참인 정리와 겉모습이 거의 같아서 반례를 찾기 전에는 그럴듯해 보인다. 평가 절차 ①이 맨 앞에 있는 이유가 이것이다 — 줄 검사에 들어가기 전에 작은 수 몇 개로 명제를 두들겨 보는 것이 가장 싸다. ### 문제 19 **접근.** 앞부분은 네 경우를 나눈 뒤 각 경우에 거듭제곱 보존을 쓰면 끝난다. 경우가 전체를 덮는 근거는 나눗셈 정리다. 뒷부분은 등식 $x^2 + y^2 = 3$의 양변을 법 4에서 읽는 것이 전부다 — 같은 수는 어느 법에서도 자기 자신과 합동이므로((C1)), 좌변이 가질 수 있는 값의 집합과 우변의 값을 비교하면 충돌이 드러난다. **풀이.** **앞부분.** $a$를 정수라 하자. 나눗셈 정리에 의해 $a = 4q + r$이고 $r \in \{0,1,2,3\}$인 정수 $q, r$이 존재하므로, $a \equiv 0, 1, 2, 3 \pmod 4$ 중 하나가 성립한다. 각 경우에 거듭제곱 보존을 적용한다. $a \equiv 0$이면 $a^2 \equiv 0^2 = 0 \pmod 4$. $a \equiv 1$이면 $a^2 \equiv 1^2 = 1 \pmod 4$. $a \equiv 2$이면 $a^2 \equiv 2^2 = 4 \equiv 0 \pmod 4$. $a \equiv 3$이면 $a^2 \equiv 3^2 = 9 \equiv 1 \pmod 4$. 네 경우가 전체를 덮고 어느 경우든 $a^2 \equiv 0$ 또는 $a^2 \equiv 1 \pmod 4$이다. $\blacksquare$ **뒷부분.** $x^2 + y^2 = 3$인 정수 $x, y$가 존재한다고 하자. 앞부분에 의해 $x^2 \equiv 0$ 또는 $1$이고 $y^2 \equiv 0$ 또는 $1 \pmod 4$이다. (C4)에 의해 $x^2 + y^2$은 법 4에서 $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, $1 + 1 = 2$ 중 하나와 합동이므로, $x^2 + y^2 \equiv 0$, $1$, 또는 $2 \pmod 4$이다. 한편 $x^2 + y^2 = 3$이고 (C1)에 의해 $3 \equiv 3 \pmod 4$이므로 $x^2 + y^2 \equiv 3 \pmod 4$여야 한다. 그런데 $3$은 $0, 1, 2$ 중 어느 것과도 법 4에서 합동이 아니다($3-0=3$, $3-1=2$, $3-2=1$ 중 어느 것도 4의 배수가 아니다). 이는 모순이므로 그런 정수 $x, y$는 존재하지 않는다. $\blacksquare$ **복기.** 부재를 보이는 표준 수법이다 — 해가 있다고 가정한 뒤 적당한 법에서 양변을 읽어 가능한 값의 집합을 충돌시킨다. 법을 무엇으로 잡는지가 전부이고, 제곱이 등장하면 법 4나 법 8이 첫 후보다(제곱이 법 4에서 두 값, 법 8에서 세 값만 갖기 때문이다). S11주차 예제 2.2가 같은 종류의 부재 증명을 다른 소재로 다뤘고, 그때 경우 나누기로 처리한 자리를 여기서는 합동 한 줄이 대신한다. ### 문제 20 **접근.** (a)는 "무엇이 보존되고 무엇이 보존되지 않는가"를 함께 적어야 완결이다 — 확인 8이 그 경계다. 예제 2.2가 증명한 것이 정확히 무엇인지부터 적고, 그 결과로 가능해진 계산을 하나 들면 세 문장이 채워진다. (b)는 §1.6의 대조표에서 어느 칸이 무대마다 달라지고 어느 칸이 같은지를 압축한다. **풀이.** (예시 답안) (a) 예제 2.2에서 곱 보존 (C5)를, 문제 7에서 합 보존 (C4)를 증명했고, 이 둘 덕분에 합동식은 등식처럼 양변에 더하고 곱할 수 있다 — $a \equiv b$이면 계산의 어느 자리에서든 $a$를 $b$로 갈아 끼워도 법 $n$에서의 결과가 바뀌지 않는다. 그래서 $7^{100} \pmod 4$ 같은 계산은 $7$을 그와 합동인 작은 대표 $-1$로 바꿔 $(-1)^{100} = 1$로 즉시 끝나고, 85자리 수를 한 번도 적지 않는다. 다만 보존되는 것은 덧셈과 곱셈뿐이며 나눗셈은 보존되지 않으므로($6 \equiv 2 \pmod 4$의 양변을 2로 나누면 거짓이 된다), 합동을 등식처럼 다룰 권리는 (C4)(C5)가 증명해 둔 만큼만 주어진다. (b) 나눗셈에서는 "$b = ak$ 꼴"을, 합동에서는 "$a - b = ns$ 꼴"을, 곱에서는 "순서쌍을 두 좌표로 분해"를 각각 걸음 ②에서 받고 걸음 ③에서 만들어야 할 꼴로 적는데, 이 두 칸의 내용만 무대마다 다르고 걸음의 배치 자체는 다섯 걸음 그대로다. 곧 무대를 옮길 때 갈아 끼우는 것은 ①에서 지목하는 정의와 ④에서 쓰는 대수의 종류뿐이며, 가정을 정의로 풀어 재료를 얻고 목표를 정의 꼴로 제작한다는 엔진은 다섯 무대에서 같다. **복기.** (a)와 (b)는 같은 물음의 두 층이다 — (a)는 한 무대 안에서 무엇이 보존되는지를 묻고, (b)는 무대를 옮길 때 무엇이 보존되는지를 묻는다. 서술 문제의 채점은 주장의 수가 아니라 그 주장을 떠받치는 자리(예제 2.2, 확인 8, §1.6의 대조표)를 지목했는지로 한다. --- **다음 주 예고 (C7주차):** Chartrand 5장 — 반례$\cdot$귀류$\cdot$존재. 이번 주 문제 18에서 반례 하나로 명제를 무너뜨린 작업과 문제 19에서 부재를 보인 작업이 각각 정식 기법으로 승격된다. 1권 21$\cdot$26$\cdot$29주차와 1학기 S5주차(구성법)$\cdot$S11주차(귀류)를 Chartrand의 언어로 재조직하고, prove-or-disprove의 전주곡으로 반례 만들기를 익힌 뒤, 존재 증명(구성적$\cdot$비구성적)과 유일성을 다룬다. 무대 이동 절차는 그대로 남고 걸음 ③의 도착점이 "모순"이나 "증인"으로 갈릴 뿐이다. 원서 5장을 통독하고 온다.