# 33주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 세 가지 빚을 함께 청산하기 완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께, 예제 2.3은 설계부터 스스로 한다. ### 예제 2.1 — 소인수분해의 존재 (빚 청산 1) **명제.** 2 이상의 모든 정수는 소수이거나 소수들의 곱이다. **설계 — 쓰기 전에 정하는 세 가지.** 귀납형 증명에서 먼저 정할 것은 무대, 기초, 가정의 크기다. 셋을 표로 옮긴다. | | **말** | **서식 번역** | |---|---|---| | 무대 | $n \ge 2$인 정수 | 기초를 $n = \underline{\quad(?)\quad}$에 둔다 | | 가정 (출발점) | 과거 전부가 성립 | $2 \le j \le k$인 모든 $j$에서 명제가 참 | | 목표 (도착점) | $k+1$도 성립 | $k+1$이 소수이거나, 소수들의 곱으로 적힌다 | :::{container} quotebox **확인 8.** 무대 칸의 빈칸을 채워 보자. 기초를 $n = 1$에 두면 무엇이 어긋나는가. ::: :::{admonition} 답 :class: quotebox dropdown $n = 2$다. 명제의 무대가 "$n \ge 2$"이므로 1은 주장의 대상이 아니고, 실제로 1은 소수도 아니고 소수들의 곱도 아니다(정의 15.2에서 1은 소수에서 제외된다). 무대 밖의 수를 기초로 삼으면 확인할 수 없는 것을 확인하려다 막힌다. ::: **1단계 — 기초를 확인한다.** $n = 2$: 2의 **양의** 약수는 1과 2뿐이므로 2는 소수다(정의 15.2). ✓ **2단계 — 강한 가정을 선언한다.** 필요한 과거의 위치를 지정할 수 없으므로 구간 전체를 가정한다(§1.2). :::{container} quotebox **확인 9.** 귀납 단계의 첫 문장을 완성해 보자: "$k \ge 2$에 대해, $\underline{\quad}$부터 $\underline{\quad}$까지의 모든 정수가 소수이거나 소수들의 곱이라고 가정하자." ::: :::{admonition} 답 :class: quotebox dropdown "$2$부터 $k$까지". 보통 귀납이라면 "$k$가 소수이거나 소수들의 곱이라고 가정하자"로 적었을 자리다. 이 한 줄의 차이가 §1.1의 막힘을 푼다. ::: **3단계 — 경우를 나눈다.** 손에 있는 정보는 "$k+1 \ge 3$인 정수"뿐이다. 2 이상의 정수는 소수이거나 합성수이므로, 이 둘로 나누면 전체가 빠짐없이 덮인다(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④). 정의 15.2는 양의 약수 쪽 말이고 15.3은 분해 쪽 말이라 두 정의만으로는 이분법이 곧바로 나오지 않는다 — 둘이 같은 경계를 긋는다는 것을 15주차 문제 4 해설이 세워 두었다(17주차의 빠짐없음 확인). :::{container} quotebox **확인 10.** $k+1$이 합성수인 경우, 정의 15.3을 풀면 무엇을 얻는가. $a, b$의 범위를 부등식으로도 적어 보자. "$k+1 = \underline{\quad}$인 정수 $a, b$가 존재하고, $\underline{\quad} \le a, b \le \underline{\quad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown $k+1 = ab$인 정수 $a, b$ ($1 < a, b < k+1$)가 존재한다. 정수에서 $1 < a$는 $2 \le a$와 같고 $a < k+1$은 $a \le k$와 같으므로 $2 \le a, b \le k$이다. 정확한 값은 모르지만 **구간은 안다** — 그 구간이 정확히 강한 가정의 범위다. 보통 귀납이 쥔 유일한 참 $P(k)$는 여기서 쓸 데가 없다 — $k+1 = 12$이면 $k = 11$이 분해 어디에도 등장하지 않기 때문이다. ::: **4단계 — 강한 가정을 소비하고 결론을 조립한다.** 얻은 구간이 가정 범위와 일치하므로 $a$와 $b$에 각각 가정을 적용한다. 둘 다 소수이거나 소수들의 곱이면 그 곱도 그렇다. :::{container} quotebox **확인 11.** 마지막 문장을 완성해 보자: "따라서 $k+1 = ab$는 $\underline{\qquad}$이다. 강한 귀납법에 의해 $\underline{\qquad}$에서 명제가 성립한다. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown "소수들의 곱" / "모든 $n \ge 2$". $a$가 소수 하나이거나 소수들의 곱이고 $b$도 그러하므로 두 목록을 이어 붙이면 $k+1$의 소수 목록이 된다(소수 하나짜리 곱도 곱으로 센다). ::: **완성본.** 방금 만든 네 단계를 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 강한 귀납법으로 증명한다. **[기초]** $n = 2$: 2의 **양의** 약수는 1과 2뿐이므로 2는 소수다(정의 15.2). ✓ | 시작점은 2다 — 명제의 무대가 $n \ge 2$이므로(확인 8). | | **[귀납]** $k \ge 2$에 대해, $2$부터 $k$까지의 모든 정수가 소수이거나 소수들의 곱이라고 가정하자. $k+1$을 생각한다. | **강한** 가정 — 직전 하나가 아니라 구간 전부. 이유는 넷째 줄에서 드러난다. | | **경우 1: $k+1$이 소수.** 그 자체로 명제가 성립한다. | 2 이상의 정수는 소수이거나 합성수이므로 두 경우가 전체를 덮는다(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④). | | **경우 2: $k+1$이 합성수.** 정의 15.3에 의해 $k+1 = ab$인 정수 $a, b$ ($1 < a, b < k+1$)가 존재한다. 곧 $2 \le a \le k$이고 $2 \le b \le k$이다. | 정의 풀어쓰기(근거 ①). 범위는 알지만 **정확한 값은 모른다** — 이것이 다음 줄의 조건이다. | | $2 \le a \le k$이고 $2 \le b \le k$이므로, 강한 귀납 가정에 의해 $a$와 $b$는 각각 소수이거나 소수들의 곱이다. | 어느 과거인지 모르는 자리를 인용하는 순간 — 강한 귀납법이 필요한 이유가 이 한 줄이다. | | 따라서 $k+1 = ab$는 소수들의 곱이다. 강한 귀납법에 의해 모든 $n \ge 2$에서 명제가 성립한다. $\blacksquare$ | 두 목록을 이어 붙이면 소수들의 곱이 된다. 결론 선언으로 마무리. | **대입 시뮬레이션.** $k + 1 = 24$는 합성수이므로 $24 = 4 \times 6$으로 쪼개지고, 강한 가정에 의해 $4 = 2 \times 2$, $6 = 2 \times 3$이 각각 소수들의 곱이므로 $24 = 2 \cdot 2 \cdot 2 \cdot 3$이다. 소비된 것은 $P(4)$와 $P(6)$뿐이고, 보통 귀납이 주는 유일한 참 $P(23)$은 한 줄에서도 쓰이지 않는다. :::{admonition} 따름정리 (빚 청산 1의 회수분) :class: quotebox 2 이상의 모든 정수는 소수인 약수를 가진다. ::: 위 분해에 등장하는 소수 아무거나 하나가 그 약수다(유도는 문제 6). 이 따름정리가 21주차 소수 무한 증명이 첫 줄에서 빌려 쓴 사실이며, 이제 그 증명이 자립한다. ### 예제 2.2 — 나눗셈 정리의 존재성 (빚 청산 2) **명제.** 정수 $a \ge 0$과 자연수 $n$에 대해, $a = nq + r$이고 $0 \le r < n$인 정수 $q, r$이 존재한다. 이번에는 설계만 함께 한다. 최소원리를 쓰려면 **어떤 집합에 적용할지**부터 정해야 한다. :::{container} quotebox **확인 12.** "나머지"란 말로 하면 "$a$에서 $n$을 뺄 만큼 뺀 잔여"다. 그 잔여들을 모은 집합을 $q$를 써서 적고, 그 집합이 공집합이 아님을 보이려면 $q$에 무엇을 넣으면 되는지도 적어 보자. $S = \{\,\underline{\qquad} : q \in \mathbb{Z},\ \underline{\qquad}\,\}$ ::: :::{admonition} 답 :class: quotebox dropdown $S = \{a - nq : q \in \mathbb{Z},\ a - nq \ge 0\}$. 두 조각이 모두 필요하다 — 앞쪽은 잔여의 꼴이고, 뒤쪽 조건은 무대를 "음이 아닌 정수"로 제한한다(이 제한이 없으면 $q$를 키우는 만큼 값이 작아져 최소원소가 없다). 비공 확인은 $q = 0$: $a \ge 0$이므로 $a \in S$다. ::: **완성본.** | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 집합 $S = \{a - nq : q \in \mathbb{Z},\ a - nq \ge 0\}$을 생각하자. | 최소원리를 적용할 대상을 먼저 만든다. 나머지 후보들의 집합이다. | | $q = 0$일 때 $a - 0 = a \ge 0$이므로 $a \in S$이다 — $S$는 공집합이 아닌, 음이 아닌 정수들의 집합이다. | 최소원리의 첫째 조각("공집합이 아닌")을 실제로 확인한다. 빠뜨리면 인용 자격이 없다. | | 최소원리에 의해 $S$는 최소원소를 가진다. 그것을 $r = a - nq_0$이라 하자 ($q_0 \in \mathbb{Z}$, $r \ge 0$). | 최소원리 인용. $r \in S$이므로 음이 아니다 — 목표의 왼쪽 부등식 $0 \le r$이 여기서 확보된다. | | $r < n$을 귀류로 보인다. 만약 $r \ge n$이면 $r - n = a - n(q_0 + 1) \ge 0$이다. | 남은 것은 오른쪽 부등식뿐이다. $r - n$을 $S$의 꼴로 다시 적는 것이 관건 — $q$ 자리에 $q_0 + 1$이 들어간다(근거 ③). | | 곧 $r - n \in S$인데 $n \ge 1$이므로 $r - n < r$이다. 이는 $r$의 최소성과 모순이다. | 최소원소보다 작은 원소를 실제로 만들어 충돌시킨다 — §1.6의 첫째 갈래(뒤의 ④-a) 그대로. | | 따라서 $0 \le r < n$이고 $a = nq_0 + r$이다. $\blacksquare$ | 두 부등식과 등식이 모두 확보됐으므로 존재가 증명됐다. | **확장 — $a < 0$인 경우.** 위 증명에서 $a \ge 0$을 쓴 곳은 단 하나, $S \neq \varnothing$을 확인한 줄($q = 0$에서 $a \in S$)이다. 그 한 줄만 다시 세우면 나머지는 글자 그대로 같다. $a < 0$이면 $q = a$로 둔다. $n \ge 1$이므로 $1 - n \le 0$이고 $a < 0$이므로, $a(1 - n)$은 0 이하인 두 수의 곱이어서 0 이상이다(근거 ③). 곧 $$ a - na = a(1 - n) \ge 0 $$ 이므로 $a - na \in S$이고 $S \neq \varnothing$이다. 이후 최소원소를 잡고 $r < n$을 보이는 논증은 위와 한 줄도 다르지 않다. 따라서 **모든 정수 $a$와 자연수 $n$**에 대해 $a = nq + r$, $0 \le r < n$인 정수 $q, r$이 존재한다 — 17주차가 인정하고 쓴 진술이 정확히 이 범위였다. **복기.** "나머지"의 정체가 여기서 드러난다 — **$a$에서 $n$을 뺄 만큼 뺀 잔여 중 가장 작은 음 아닌 것**이다. 유일성은 문제 10에서 따로 증명한다(존재와 유일은 별개 의무 — 26주차). 확장 단계를 따로 붙인 이유도 같은 자리에 있다 — 무대를 넓히려면 넓힌 만큼의 증명이 필요하고, "같은 논법이 선다"는 한 줄은 증명이 아니다. :::{admonition} 따름정리 (1주차 문제 16의 빚 청산) :class: quotebox 모든 정수는 짝수이거나 홀수이다. ::: 나눗셈 정리를 $n = 2$에 적용하면 $a = 2q + r$, $0 \le r < 2$인 정수 $q, r$이 존재한다. $r$는 $0 \le r < 2$인 정수이므로 $r = 0$ 또는 $r = 1$이다(그 사이에 정수가 없다는 것이 보조 명제 33.A다). 각각 $a = 2q$(짝수)와 $a = 2q + 1$(홀수)이다. 확장 단계가 붙었으므로 이 따름정리의 무대도 **모든 정수**다. 1주차 문제 16, 9주차 예제 2.3, 11주차 문제 2, 17주차의 경우 나누기가 전부 이 한 줄에 기대고 있었다. ### 예제 2.3 — 기약분수의 존재 (빚 청산 3) **명제.** 모든 양의 유리수는 기약분수로 나타낼 수 있다. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 13.** 최소원리를 어느 집합에 적용해야 하는가. 그 집합이 공집합이 아님은 무엇이 보장하는가. ::: :::{admonition} 답 :class: quotebox dropdown $S = \{b \in \mathbb{N} : r = \frac{a}{b}$인 $a \in \mathbb{N}$가 존재$\}$ — 같은 유리수 $r$을 나타내는 표현들의 **분모**를 모은 집합이다. 비공의 근거는 유리수의 정의(정의 15.1)이되 한 걸음이 더 필요하다. 정의 15.1이 주는 것은 $r = \frac{a}{b}$인 **정수** $a, b$ ($b \neq 0$) 이지 자연수 $a, b$가 아니기 때문이다. $r > 0$이므로 $a \neq 0$이고 $a$와 $b$는 같은 부호이며, 둘 다 음수이면 $(a, b)$를 $(-a, -b)$로 바꿔도 값이 같으므로 처음부터 $a, b \in \mathbb{N}$인 표현을 잡을 수 있다. 그 $b$가 $S$의 원소다. 최소 분모를 잡으면 "더는 약분할 수 없다"가 따라 나온다. ::: **증명.** $r$를 양의 유리수라 하자. 집합 $$ S = \Big\{ b \in \mathbb{N} : r = \tfrac{a}{b} \text{인 } a \in \mathbb{N} \text{가 존재} \Big\} $$ 를 생각하자. 정의 15.1에 의해 $r = \frac{a}{b}$인 정수 $a, b$ ($b \neq 0$)가 존재한다. $r > 0$이므로 $a \neq 0$이고 $a$와 $b$는 같은 부호이며, 둘 다 음수이면 $(a, b)$를 $(-a, -b)$로 바꿔도 값이 같으므로 처음부터 $a, b \in \mathbb{N}$인 표현을 잡을 수 있다. 그 $b$가 $S$의 원소이므로 $S \neq \varnothing$이다. 최소원리에 의해 $S$는 최소원소 $b_0$을 가지며, $r = \frac{a_0}{b_0}$인 자연수 $a_0$을 하나 잡는다. 이 표현이 기약임을 귀류로 보인다. $a_0$과 $b_0$이 $1$보다 큰 공통 약수 $d$를 가진다고 가정하면, $a_0 = d a_1$, $b_0 = d b_1$인 자연수 $a_1, b_1$이 존재하고 $$ r = \frac{a_0}{b_0} = \frac{d a_1}{d b_1} = \frac{a_1}{b_1} $$ 이다. 곧 $b_1 \in S$이다. 그런데 $d > 1$이므로 $b_1 = \frac{b_0}{d} < b_0$이고, 이는 $b_0$의 최소성과 모순이다. 따라서 $a_0$과 $b_0$의 공통 약수는 $\pm 1$뿐이고, $\frac{a_0}{b_0}$은 기약분수다(정의 21.2). $\blacksquare$ **확장 — $r \le 0$인 경우.** 21주차가 인정하고 쓴 것은 "**모든** 유리수는 기약분수로 나타낼 수 있다"이므로, 0과 음의 유리수까지 덮어야 회수가 끝난다. $r = 0$이면 $\frac{0}{1}$이 기약이다 — 1의 약수는 $\pm 1$뿐이므로(22주차 보조 명제 22.A) 0과 1의 공통 약수도 $\pm 1$뿐이다. $r < 0$이면 $-r$가 양의 유리수이므로 위 증명이 기약 표현 $-r = \frac{a_0}{b_0}$을 주고, $r = \frac{-a_0}{b_0}$이다. $d \mid -a_0$과 $d \mid a_0$은 같은 조건이므로($-a_0 = dc$이면 $a_0 = d(-c)$, 근거 ①) 공통 약수의 집합은 분자의 부호에 무관하고, 따라서 $\frac{-a_0}{b_0}$도 기약이다(정의 21.2). 곧 모든 유리수에서 성립한다. **복기.** 21주차가 직관으로 넘긴 문장 — "약분을 반복하면 언젠가 끝난다" — 의 엄밀한 정체가 이것이다. 약분할 때마다 분모가 작아지는데 **자연수는 무한히 작아질 수 없다**(문제 18에서 일반화). ### 관찰 — 최소원리 증명의 같은 뼈대 예제 2.2와 2.3은 소재가 전혀 다르지만 걸음이 같다. 대응표의 빈칸을 채워 보자. | **단계** | **예제 2.2 (나눗셈 정리)** | **예제 2.3 (기약분수)** | |---|---|---| | ① 후보들의 집합 $S$를 만든다 | 잔여 $a - nq \ge 0$의 집합 | $\underline{\quad(1)\quad}$ | | ② $S \neq \varnothing$을 확인한다 | $q = 0$에서 $a \in S$ | $\underline{\quad(2)\quad}$ | | ③ 최소원소를 잡는다 | 나머지 $r$ | 최소 분모 $b_0$ | | ④ 더 작은 원소를 만들어 최소성과 충돌시킨다 | $r - n \in S$, $r - n < r$ | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 14.** 빈칸 (1)(2)(3)을 채우고, ④단계에서 두 증명이 공통으로 하는 일을 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $r$의 분수 표현들의 분모 집합. (2) 유리수의 정의가 **정수** 표현 하나를 보장하고, $r > 0$이므로 부호를 맞춰 자연수 표현으로 고칠 수 있으니 그 분모가 $S$의 원소. (3) 공통 약수 $d > 1$로 약분해 만든 $b_1 \in S$, $b_1 < b_0$. ④에서 공통으로 하는 일: **최소라고 잡은 것보다 작은 원소를 실제로 만들어 제시한다.** 다만 이 문장은 두 예제에 대한 관찰이다 — 최소 반례법(문제 11, 14)은 ④를 다른 방식으로 한다. 아래 서식의 ④-a와 ④-b가 그 두 갈래다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **최소원리 4단 서식** ① 후보들의 집합 $S$를 정의한다 $\to$ ② $S \neq \varnothing$을 원소 하나로 확인한다 $\to$ ③ 최소원리로 최소원소 $m$을 잡는다 $\to$ ④ 모순을 만든다. ④는 두 갈래다: **(④-a)** $m$보다 작은 원소를 실제로 만들어 **최소성**과 충돌시킨다(예제 2.2, 2.3, 문제 13). **(④-b)** 최소성이 주는 "$m$보다 작은 곳은 전부 참"을 써서 $m$에서도 명제가 참임을 보이고 **$m \in S$**와 충돌시킨다(최소 반례법 — 문제 11, 14). ::: 최소 반례법(§1.6)은 $S$를 "반례들의 집합"으로 잡고 ④-b로 닫는 경우다. 두 갈래는 충돌 상대가 다르다 — ④-a는 최소성과, ④-b는 $m$의 소속과 부딪친다. 문제 11을 ④-a로 쓰려 하면 $S$의 더 작은 원소를 만들 길이 없어 막히므로, 어느 갈래인지를 먼저 정하고 시작한다. 예제 2.1의 강한 귀납법은 아예 다른 뼈대를 쓴다 — 기초 $\to$ 강한 가정 선언 $\to$ 경우 나누기 $\to$ 위치를 모르는 과거 인용 $\to$ 조립. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** 모든 자연수 $n$은 $n = 2^a m$ ($a \ge 0$은 정수, $m$은 홀수) 꼴로 나타낼 수 있다. **증명.** 강한 귀납법으로 증명한다. **[기초]** $n = 1$: $1 = 2^0 \cdot 1$이고 1은 홀수다. ✓ **[귀납]** 1부터 $k$까지 성립한다고 가정하자. $k+1$에 대해: **경우 1: $k+1$이 홀수.** $k + 1 = 2^{\underline{\quad(1)\quad}} \cdot (k+1)$ — 완료. **경우 2: $k+1$이 짝수.** $k+1 = 2j$인 자연수 $j$가 존재하고, $j \le k$이므로 $\underline{\quad(2)\quad}$ 가정에 의해 $j = 2^a m$ ($m$은 홀수) 꼴이다. 그러면 $k + 1 = 2j = 2^{\underline{\quad(3)\quad}} m$ — 완료. $\blacksquare$ (경우 2에서 $j$는 대개 $k$가 아니라 **약 절반 지점**이다 — $k = 1$일 때만 $j = k$이고, 그 밖에는 직전 가정으로 닿지 않는 과거다.) ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 최소 반례법의 서식 낱말과 근거 문장도 빈칸이다. **명제.** 모든 자연수 $n$에 대해 $n^3 - n$은 3의 배수이다. **증명.** 모순을 위해 명제가 거짓인 자연수가 있다고 가정하자. 반례들의 집합은 $\underline{\quad(1)\quad}$이 아니므로 $\underline{\quad(2)\quad}$에 의해 최소원소 $m$이 존재한다. $n = 1$일 때 $1^3 - 1 = 0 = 3 \cdot 0$이므로 명제가 성립한다. 따라서 $m \ge \underline{\quad(3)\quad}$이고 $m - 1$은 자연수다. $m$의 $\underline{\quad(4)\quad}$에 의해 $m-1$은 반례가 아니므로 $(m-1)^3 - (m-1) = 3s$인 정수 $s$가 존재한다. 그러면 $$ m^3 - m = \big[(m-1)^3 - (m-1)\big] + \underline{\quad(5)\quad} = 3s + 3(m^2 - m) = 3\big(\underline{\quad(6)\quad}\big) $$ 이고, $\underline{\quad(7)\quad}$이므로 괄호 안은 정수다. 따라서 $m$에서도 명제가 성립하여 $m$이 반례라는 것과 모순이다. 그러므로 반례는 존재하지 않는다. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 최소원리 4단 서식의 각 칸을 통째로 채운다. 예제 2.1의 따름정리를 **분해 없이** 최소원리만으로 다시 증명하는 훈련이다. **명제.** 2 이상의 모든 정수 $n$은 소수인 약수를 가진다. **증명의 뼈대.** - ① 후보들의 집합: $S = \underline{\quad(1)\quad}$ - ② 비공 확인: $\underline{\quad(2)\quad}$ - ③ 최소원소 잡기: $\underline{\quad(3)\quad}$ - ④ 그 최소원소가 소수임을 귀류로 보이기: $\underline{\quad(4)\quad}$ (④에서 쓸 부품은 2주차 예제 2.1의 추이성이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 귀납형 문제는 반드시 "무대 / 기초 / 가정의 크기"를 먼저 적고 시작한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "강한 귀납법으로 하면 된다(맞음)"는 0점이고, "$a, b$의 위치를 지정할 수 없으므로 구간 전체를 가정한다"가 만점이다. 최소원리를 인용한 줄에는 $S \neq \varnothing$의 확인이, 보폭 $d$짜리 강한 귀납에는 기초 $d$개가 반드시 함께 있어야 한다. 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 강한 귀납법의 원리를 쓰고, 보통 귀납과의 차이(가정의 크기)와 "언제 필요한가"의 신호 두 가지(분해형$\cdot$고정 보폭)를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 채점 항목이 셋이다 — 기초$\cdot$귀납 두 조각의 진술, 차이 한 문장, 신호 두 개. 신호는 §1.4의 표에서 왼쪽 열 두 낱말과 각각의 생김새를 함께 적는다. ::: **2.** [백지] 최소원리를 진술하고, 실수 구간 $(0,1)$이 반례가 되는 이유(22주차 문제 10)를 한 줄로 덧붙이시오. :::{admonition} 힌트 :class: quotebox dropdown 진술에는 조각이 셋 있다(§1.5의 해부 표). 반례 쪽은 후보 $m$을 잡은 뒤 더 작은 원소를 실제로 만들어 보이면 한 줄로 끝난다. ::: **3.** 다음 각 상황에 알맞은 도구(보통 귀납 / 강한 귀납 / 최소원리)를 고르고 이유를 한 줄씩 쓰시오. (a) $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ — 합의 마지막 항 분리 (b) "모든 $n \ge 2$는 소수들의 곱" — $k+1 = ab$ 분해 (c) "반례가 있다면 가장 작은 반례를 잡아 모순" — 논법 자체 (d) $F_{k+1}$의 성질이 $F_k$와 $F_{k-1}$ 둘에서 오는 경우 :::{admonition} 힌트 :class: quotebox dropdown 각 항목에서 물을 것은 하나다 — "$k+1$의 성질이 어느 자리에서 오는가". 직전 하나면 보통 귀납, 위치를 모르거나 두 칸 이상 뒤면 강한 귀납이다. ::: **4.** 예제 2.1(소인수분해 존재)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 여섯 줄이다: 기초 $\to$ 강한 가정 선언 $\to$ 경우 1(소수) $\to$ 경우 2의 정의 풀기 $\to$ 강한 가정 소비 $\to$ 조립. 가장 자주 비는 곳은 "$2 \le a, b \le k$"의 부등식이다. ::: **5.** 예제 2.3(기약분수 존재)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 최소원리 4단 서식의 칸을 차례로 채운다. ②(비공 확인)와 ④(더 작은 분모 제작)가 빠지기 쉽다 — 특히 $b_1 < b_0$의 근거로 $d > 1$을 명시했는지 확인한다. ::: **6.** "2 이상의 모든 정수는 소수인 약수를 가진다"를 예제 2.1의 따름정리로 유도하시오 (세 줄 이내). 이 사실이 21주차 어느 증명의 부품이었는지도 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.1이 주는 두 경우를 그대로 받는다. 소수인 경우에는 자기 자신이 답이고, 곱인 경우에는 그 곱에 등장하는 소수 하나를 꺼내 정의 2.1로 약수임을 확인한다. ::: ### 표준 ●●○ **7.** 빈칸 훈련($n = 2^a m$)을 백지에서 완성하시오. **8.** (우표 문제, 강귀납 버전) $n \ge 8$인 모든 정수는 $3a + 5b$ ($a, b \ge 0$) 꼴임을 **강한 귀납법**으로 증명하시오 (기초 $n = 8, 9, 10$ 세 개를 확인하고, $k + 1 \ge 11$에서 $P(k - 2)$를 사용한다). 32주차 문제 15(교체 논법)와 어느 쪽이 깔끔한지 한 줄 논평하시오. :::{admonition} 힌트 :class: quotebox dropdown 보폭이 3이므로 기초가 세 개다(§1.4). 귀납 단계에서 확인할 것은 하나 — $k+1-3$이 가정 범위($8$ 이상)에 들어오는가. $k+1 \ge 11$이 정확히 그것을 준다. ::: **9.** 예제 2.2(나눗셈 정리 존재성)를 백지에 재현하시오. **10.** (나눗셈 정리의 유일성) $a = nq + r = nq' + r'$이고 $0 \le r, r' < n$이면 $q = q'$이고 $r = r'$임을 증명하시오. (힌트: $r - r' = n(q' - q)$이고 $|r - r'| < n$ — 25주차 예제 2.2의 보조정리) :::{admonition} 힌트 :class: quotebox dropdown 유일성의 표준 서식(26주차)은 "두 개를 잡고 같음을 보인다"이다. 두 표현을 하나의 등식에 놓고 $r$ 쪽과 $q$ 쪽을 분리하면 "$n$의 배수인데 절댓값이 $n$ 미만"이 된다. ::: **11.** (최소 반례법 재증명) $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$을 최소 반례법으로 다시 증명하시오. (최소 반례 $m$을 잡고: $m = 1$인가? $m - 1$은 반례가 아님을 이용해 모순) :::{admonition} 힌트 :class: quotebox dropdown §1.6의 서식을 그대로 따른다. $m = 1$을 배제하는 근거는 $n = 1$에서의 직접 확인이고, $m-1$에서 공식이 성립한다는 근거는 $m$의 최소성이다. ::: **12.** $n \ge 12$인 모든 정수는 $4a + 5b$ ($a, b \ge 0$) 꼴임을 강한 귀납법으로 증명하시오 (기초 4개: $12, 13, 14, 15$). **13.** (√2 무리수 — 최소원리 버전) 다음 하강 논법을 완성하시오: $\sqrt2 = \frac{a}{b}$인 자연수 표현이 존재한다고 가정하고, 분모가 최소인 표현 $\frac{a_0}{b_0}$을 잡는다. (a) $1 < \frac{a_0}{b_0} < 2$에서 $b_0 < a_0 < 2b_0$임을 확인하시오. (b) $a_1 = 2b_0 - a_0$, $b_1 = a_0 - b_0$이 자연수이고 $\frac{a_1}{b_1}$도 $\sqrt2$와 같음을 계산으로 보이시오 ($a_1^2 = 2b_1^2$ 확인). (c) $b_1 < b_0$으로 최소성과 모순임을 선언하시오. :::{admonition} 이 문제가 쓰는 도구 — 최소 분모 하강 :class: quotebox 21주차의 √2 증명은 "기약분수 표현을 잡는다"로 시작했다. 이번에는 기약을 요구하지 않고 **분모가 최소인 표현**을 잡는다 — 예제 2.3의 그 집합에 최소원리를 적용하는 것이며, 두 출발점이 같은 장치임을 확인하는 문제다. 하강으로 모순을 만드는 이 논법을 **무한 강하법**(infinite descent)이라 부르고, 정당성은 문제 18에서 증명한다. ::: :::{admonition} 힌트 :class: quotebox dropdown (b)가 중심이다. $a_1^2$과 $2b_1^2$을 전개한 뒤 $a_0^2 = 2b_0^2$을 대입해 비교한다. $a_1, b_1$이 **자연수**라는 확인을 빠뜨리지 않는다 — (a)가 그 준비다. ::: **14.** (최소원리 $\Rightarrow$ 귀납법) $P(1)$이 참이고 모든 $k$에서 $P(k) \Rightarrow P(k+1)$인데도 어떤 자연수에서 $P$가 거짓이라고 가정하자. 최소원리로 모순을 이끌어내시오. (힌트: 반례 집합의 최소원소 $m$ — $m = 1$일 수 있는가? $m - 1$은?) :::{admonition} 힌트 :class: quotebox dropdown 증명할 대상이 명제가 아니라 **원리**라는 점만 다르고 안쪽은 최소 반례법 그대로다. 재료는 기초($P(1)$ 참)와 전달 장치 둘 — 각각의 소비 지점을 표시하며 쓴다. ::: ### 도전 ●●● :::{admonition} 이 문제군이 인정하고 쓰는 사실 — 유한 집합의 최대원소 :class: quotebox 문제 15는 "$2^j \le k+1$인 최대의 $j$"를 잡는다. 그런 $j$가 존재하는 이유는 후보가 유한하고(2의 거듭제곱은 곧 $k+1$을 넘어선다) 비어 있지 않기 때문이다. "공집합이 아닌 유한한 **음이 아닌 정수** 집합에는 최대원소가 있다"는 최소원리의 짝이다 — 후보 집합이 $j = 0$을 담으므로($2^0 = 1 \le k+1$) 자연수 판으로는 덮이지 않고, 최소원리 진술이 음이 아닌 정수까지 덮는 것과 짝을 맞춰 읽어야 한다. 이 교재에서는 증명 없이 인정한 채로 둔다 — 증명에는 유한 집합의 크기에 대한 귀납이 필요하고, 그것은 이 과정에서 다루지 않는다. 끝까지 미증명으로 남는 항목이다. ::: **15.** (이진 표현의 존재) 모든 자연수는 **서로 다른** 2의 거듭제곱들의 합으로 나타낼 수 있음을 강한 귀납법으로 증명하시오. (힌트: $k+1$ 이하인 최대의 $2^j$를 떼어내고, 잔여 $r = k+1 - 2^j$에 대해 ① $r \le k$ ② $r < 2^j$ (아니면 $2^{j+1} \le k+1$이 되어 최대성 모순)을 확인 — ②가 "서로 다름"을 보장한다) :::{admonition} 힌트 :class: quotebox dropdown 확인할 것이 셋이다: $r$이 자연수인가, $r \le k$인가, $r < 2^j$인가. 셋째는 귀류로 따로 증명한다 — $r \ge 2^j$이면 $k+1$이 얼마 이상이 되는지 계산해 본다. ::: **16.** (서술) 소인수분해의 **유일성**(순서를 빼면 한 가지)은 존재성보다 훨씬 어렵다. 그 증명에 필요한 핵심 보조정리가 "유클리드 보조정리: $p$가 소수이고 $p \mid ab$이면 $p \mid a$ 또는 $p \mid b$"이다. (a) 이 보조정리가 소수가 아닌 수에서는 거짓임을 반례로 보이시오 (2주차 문제 15). (b) 유일성이 왜 자명하지 않은지 — "$6 = 2 \times 3$ 말고 다른 소수 조합이 없다는 걸 무엇이 막아 주는가?" — 를 두 문장 이내로 쓰시오 (증명은 정수론 과목의 몫). :::{admonition} 이 문제가 인정하고 쓰는 사실 — 유클리드 보조정리 :class: quotebox $p$가 소수이고 $p \mid ab$이면 $p \mid a$ 또는 $p \mid b$이다. 이 교재에서는 증명 없이 인정한 채로 둔다 — 증명에는 베주 항등식이나 유클리드 호제법이 필요하고, 그것은 정수론 과목의 출발점이다. 이 항목은 50주차의 "남겨 둔 빚"에 그대로 남으며, 38주차 문제 15가 이 사실 위에 선다. (a)는 인정 범위를 재는 문제다. ::: :::{admonition} 힌트 :class: quotebox dropdown (a) 조건 "소수"가 하는 일을 재는 문제다. 소수가 아닌 $p$는 $p = uv$ ($1 < u, v < p$)로 쪼개지므로, $u$와 $v$를 $a$ 쪽과 $b$ 쪽에 하나씩 나눠 넣으면 $p \mid ab$는 살아 있는데 $p \nmid a$, $p \nmid b$가 된다(2주차 문제 15). 가장 작은 $p$부터 시험한다. (b) 축은 "존재와 유일은 별개 의무"(26주차)다. 존재성 증명이 실제로 무엇을 했고 유일성은 그중 무엇을 하지 않았는지를 한 문장씩 적는다. ::: **17.** (진단 — 기초 부족) 수열을 $c_1 = 1$, $c_2 = 4$, $c_n = c_{n-2} + 2$ ($n \ge 3$)로 정의하자. 다음 '증명'의 결함을 찾고, 실제 $c_2, c_4$ 값으로 반박하시오. :::{container} quotebox "명제: 모든 $n$에 대해 $c_n = n$이다. 증명: 강한 귀납법. [기초] $c_1 = 1$ ✓. [귀납] $1 \sim k$에서 성립 가정. $c_{k+1} = c_{k-1} + 2 = (k-1) + 2 = k+1$ ✓. $\blacksquare$" ::: :::{admonition} 힌트 :class: quotebox dropdown 정의대로 $c_2, c_3, c_4$를 직접 계산해 본다. 결론이 거짓인데 계산이 틀리지 않았다면 오류는 **설정**에 있다 — 이 증명이 참조하는 과거는 몇 칸 뒤인가(§1.4). ::: **18.** (무한 하강 금지) "자연수의 순감소 무한 수열($a_1 > a_2 > a_3 > \cdots$, 모든 $a_i \in \mathbb{N}$)은 존재하지 않는다"를 최소원리로 증명하시오. 그리고 문제 13(√2 하강)이 이 원리의 사례임을 한 문장으로 연결하시오. :::{admonition} 힌트 :class: quotebox dropdown 최소원리는 수열이 아니라 **집합**에 적용된다. 첫 줄에서 할 일은 수열에서 집합을 만드는 것이다 — 항들의 값을 모두 모으면 자연수의 부분집합이 된다. ::: **19.** (자기 설계 — 우표 변형) 4원과 7원 우표로 만들 수 있는 금액을 조사하시오: (a) 17원은 불가능함을 전수 조사로 보이시오. (b) $n \ge 18$인 모든 정수는 가능함을 강한 귀납법(기초 $18, 19, 20, 21$)으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown (a)의 전수 조사는 $b$(7원의 장수)로 나눈다. $7b \le 17$이므로 후보가 유한하고, 각각에서 남은 금액이 4의 배수인지만 확인하면 끝난다. (b)는 보폭 4 — 문제 12와 같다. ::: **20.** (서술) 귀납$\cdot$강한 귀납$\cdot$최소원리의 관계를 정리하시오: (a) 셋이 "한 가족"이라는 말의 뜻 (문제 14 + 최소 반례법의 구조를 근거로). (b) 실전에서 셋 중 무엇을 먼저 꺼낼지 자신의 기준을 세 줄 이내로. :::{admonition} 힌트 :class: quotebox dropdown (a)의 재료는 둘이다 — 문제 14가 "최소원리 $\Rightarrow$ 귀납법" 한 방향을 세우고, 문제 11이 같은 명제를 귀납과 최소 반례법 두 문법으로 증명해 뼈대가 겹침을 보인다. 강한 귀납이 보통 귀납을 포함한다는 §1.4의 한 줄까지 얹으면 세 꼭짓점이 이어진다. (b)는 정답이 하나가 아니다. 다만 근거가 §1.4의 신호 표(분해형$\cdot$고정 보폭)와 §1.6의 쓰임 표(최소 반례$\cdot$최소 잔여$\cdot$최소 후보)에 각각 닿아 있어야 한다. ::: ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 강한 귀납법의 원리$\cdot$최소원리$\cdot$4단 서식만 펴 놓고 예제 2.1과 2.2를 처음부터 끝까지 적는다. 본문의 다른 부분은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다: - [ ] 강한 귀납법의 원리를 진술하고, 보통 귀납과의 차이를 조각 하나로 지목했다. - [ ] "분해형$\cdot$고정 보폭" 두 신호와 "보폭 $d$이면 기초 $d$개" 규칙을 썼다. - [ ] 최소원리를 세 조각(공집합이 아닌 / 자연수의 부분집합 / 최소원소 존재) 그대로 쓰고, "최소"라는 낱말이 하는 일을 설명했다. - [ ] 예제 2.1(소인수분해)$\cdot$2.2(나눗셈 정리)$\cdot$2.3(기약분수)을 재현했다 — 3대 빚 청산. - [ ] 최소원리 4단 서식의 ②(비공 확인)를 빠뜨리지 않았고, ④를 두 갈래로 구분해 썼다 — ④-a 최소성과 충돌(더 작은 원소 제작) / ④-b 소속과 충돌(최소 반례법). - [ ] 귀납 $\Longleftrightarrow$ 최소원리 동치의 한 방향(문제 14)을 재현했다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 보통 귀납과 강한 귀납 중 무엇을 쓸지 모르겠다 | §1.4 신호 표 — $k+1$의 성질이 어느 자리에서 오는지 먼저 적는다 | | 기초를 몇 개 둘지 모르겠다 | §1.4 보폭 규칙 + 문제 17의 진단 | | 최소원리를 어느 집합에 쓸지 모르겠다 | §1.6 쓰임 표와 §2 관찰의 대응표 — 후보를 모으는 것이 ①단계 | | 최소원소를 잡은 다음이 나오지 않는다 | §1.6과 §2의 4단 서식 — 어느 갈래인지부터 정한다. ④-a는 더 작은 원소를 만들고, ④-b는 "$m$보다 작은 곳은 전부 참"을 쓴다 | | 반례 집합이 비지 않음을 왜 확인하는지 모르겠다 | §1.5 조각 삭제 실험 1 | | 강한 가정을 선언만 하고 쓰지 못했다 | 예제 2.1의 4단계 — 가정 범위와 얻은 구간을 대조한다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $0$ (2) 강한 귀납 (또는 강한 귀납법의) (3) $a + 1$ ※ (3)에서 $2 \cdot 2^a = 2^{a+1}$이고 $m$은 그대로 홀수로 남는다. (2)가 핵심 지점이다: $j$의 위치는 $k+1$에 따라 달라지므로 직전 가정으로는 닿지 않는다. ### 빈칸 사다리 — 훈련 2 (1) 공집합 (2) 최소원리 (3) $2$ (4) 최소성 (5) $3(m^2 - m)$ (6) $s + m^2 - m$ (7) 정수의 합$\cdot$차$\cdot$곱은 정수 (근거 ②) ※ (5)의 계산: $(m-1)^3 - (m-1) = m^3 - 3m^2 + 2m$이므로 차는 $3m^2 - 3m$이다. $m-1$을 쓸 수 있는 근거가 (4) 최소성이라는 점을 반드시 표시한다. ### 빈칸 사다리 — 훈련 3 (1) $S = \{d \in \mathbb{N} : d > 1$이고 $d \mid n\}$ (2) $n \mid n$이고 $n > 1$이므로 $n \in S$ — $S$는 공집합이 아니다. (3) 최소원리에 의해 $S$는 최소원소 $p$를 가진다. $p > 1$이고 $p \mid n$이다. (4) $p$가 소수가 아니라고 가정하면 $p$는 합성수이고(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④), 정의 15.3에 의해 $p = ab$인 정수 $a, b$ ($1 < a, b < p$)가 존재한다. $a \mid p$이고 $p \mid n$이므로 추이성 (2주차 예제 2.1)에 의해 $a \mid n$이다. $a > 1$이므로 $a \in S$인데 $a < p$ — $p$의 최소성과 모순이다. 따라서 $p$는 소수이고, $n$은 소수인 약수 $p$를 가진다. $\blacksquare$ ※ 문제 6은 같은 결론을 예제 2.1의 분해에서 꺼냈고, 이 훈련은 분해 없이 도달했다. 얻은 소수도 다르다 — 여기의 $p$는 $n$의 **가장 작은** 1보다 큰 약수다. ### 문제 1 **접근.** 채점 항목이 셋이다: ① 원리의 두 조각을 정확히 진술, ② 보통 귀납과의 차이를 "가정의 크기"라는 조각 하나로 지목, ③ 신호 두 가지를 생김새와 함께 제시. **풀이.** **(원리)** $P(1)$이 참이고(필요하면 $P(1), \dots, P(n_0)$ 여러 개), 모든 $k$에 대해 "$P(1), P(2), \dots, P(k)$가 전부 참이면 $P(k+1)$도 참"이면, 모든 자연수 $n$에서 $P(n)$이 참이다. **(차이)** 보통 귀납의 가정은 직전 하나 $P(k)$이고, 강한 귀납의 가정은 $P(1)$부터 $P(k)$까지 전부다. 다른 조각은 하나도 바뀌지 않는다 — 기초도, 결론도 같다. **(신호 1: 분해형)** $k+1 = ab$처럼 쪼개지는데 $a, b$가 구간 어디에 있는지 미리 지정할 수 없는 경우. 예제 2.1과 훈련 1($n = 2^a m$)이 여기 속한다. **(신호 2: 고정 보폭)** $k+1$의 성질이 $k-1$이나 $k-2$처럼 정해진 칸수 뒤에서 오는 경우. 문제 8(보폭 3), 문제 12(보폭 4)가 여기 속하며, 보폭이 $d$이면 기초를 $d$개 확인해야 한다. ### 문제 2 **접근.** 진술은 세 조각(공집합이 아닌 / 자연수의 부분집합 / 최소원소를 가진다)을 빠짐없이 적는 것이 채점 기준이다. 반례 쪽은 어떤 후보를 잡아도 더 작은 원소를 만들 수 있음을 보여야 한다. **풀이.** **(진술)** 공집합이 아닌 자연수의 부분집합은 반드시 최소원소를 가진다(음이 아닌 정수의 부분집합에 대해서도 같다). $S$의 최소원소란 $m \in S$이면서 모든 $x \in S$에 대해 $m \le x$인 $m$이다. **(반례)** 실수에서는 거짓이다. 구간 $(0,1)$은 비어 있지 않지만, 어떤 후보 $m \in (0,1)$에 대해서도 $\frac{m}{2}$이 다시 $(0,1)$의 원소이면서 $m$보다 작으므로 $m$은 최소가 될 수 없다(22주차 문제 10). 최소원리를 인용할 때 무대가 자연수인지 먼저 확인하는 이유다. ### 문제 3 **접근.** 각 항목에서 물을 것은 하나다 — "$k+1$의 성질이 어느 자리에서 오는가". 직전 하나면 보통 귀납, 위치를 지정할 수 없거나 정해진 칸수 뒤면 강한 귀납이다. **풀이.** **(a) 보통 귀납.** $\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1)$로 마지막 항만 떼어 내면 필요한 과거는 직전 하나 $P(k)$뿐이다. **(b) 강한 귀납.** 분해형 신호다. $k+1 = ab$에서 $a, b$는 $2$ 이상 $k$ 이하의 어딘가지만 위치를 지정할 수 없으므로 구간 전체를 가정해야 한다. **(c) 최소원리.** 도구 선택이 아니라 논법의 이름 자체다 — "가장 작은 반례가 존재한다"를 보장하는 것이 최소원리이고, 그 위에 선 서식이 최소 반례법이다(§1.6). **(d) 강한 귀납.** 고정 보폭 2다. $F_{k+1}$이 $F_k$와 $F_{k-1}$ 둘을 쓰므로 가정에 $P(k-1)$이 들어 있어야 하고, 보폭이 2이므로 기초도 두 개($F_1, F_2$)다. ### 문제 4 **접근.** 뼈대는 기초 $\to$ 강한 가정 선언 $\to$ 경우 나누기 $\to$ 정의 풀기 $\to$ 강한 가정 소비 $\to$ 조립이다. 자주 비는 곳은 둘이다: 경우 나누기가 전체를 덮는다는 근거와, $1 < a, b < k+1$을 $2 \le a, b \le k$로 바꾸는 줄이다. **풀이.** 강한 귀납법으로 증명한다. **[기초]** $n = 2$: 2의 **양의** 약수는 1과 2뿐이므로 2는 소수다(정의 15.2). ✓ **[귀납]** $k \ge 2$에 대해, $2$부터 $k$까지의 모든 정수가 소수이거나 소수들의 곱이라고 가정하자. $k+1 \ge 3$이므로 $k+1$은 소수이거나 합성수다(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④). **경우 1: $k+1$이 소수.** 그 자체로 명제가 성립한다. **경우 2: $k+1$이 합성수.** 정의 15.3에 의해 $k+1 = ab$인 정수 $a, b$ ($1 < a, b < k+1$)가 존재한다. 정수에서 $1 < a$는 $2 \le a$와 같고 $a < k+1$은 $a \le k$와 같으므로 $2 \le a \le k$, 마찬가지로 $2 \le b \le k$이다. 따라서 강한 귀납 가정을 $a$와 $b$에 각각 적용할 수 있고, 둘은 각각 소수이거나 소수들의 곱이므로 두 목록을 이어 붙이면 $k+1 = ab$는 소수들의 곱이다. 강한 귀납법에 의해 $n \ge 2$인 모든 정수에서 성립한다. $\blacksquare$ ### 문제 5 **접근.** 최소원리 4단 서식대로 ① 분모들의 집합 $\to$ ② 유리수의 정의로 비공 확인 $\to$ ③ 최소 분모 $b_0$ $\to$ ④-a 약분해 더 작은 분모를 만들어 모순. ②에서 한 걸음이 자주 빠진다 — 정의 15.1이 주는 것은 정수 표현이므로 부호를 맞춰 자연수 표현으로 고치는 줄이 있어야 $b$가 $S$의 원소가 된다. ④에서는 $b_1 < b_0$의 근거가 $d > 1$이라는 점을 명시해야 한다. **풀이.** $r$를 양의 유리수라 하자. 집합 $S = \{b \in \mathbb{N} : r = \frac{a}{b}$인 $a \in \mathbb{N}$가 존재$\}$를 생각하자. 정의 15.1에 의해 $r = \frac{a}{b}$인 정수 $a, b$ ($b \neq 0$)가 존재한다. $r > 0$이므로 $a \neq 0$이고 $a$와 $b$는 같은 부호이며, 둘 다 음수이면 $(a, b)$를 $(-a, -b)$로 바꿔도 값이 같으므로 처음부터 $a, b \in \mathbb{N}$인 표현을 잡을 수 있다. 그 $b$가 $S$의 원소이므로 $S \neq \varnothing$이다. 최소원리에 의해 $S$는 최소원소 $b_0$을 가지며, $r = \frac{a_0}{b_0}$인 자연수 $a_0$을 하나 잡는다. 이 표현이 기약임을 귀류로 보인다. $a_0$과 $b_0$이 $1$보다 큰 공통 약수 $d$를 가진다고 가정하면 $a_0 = d a_1$, $b_0 = d b_1$인 자연수 $a_1, b_1$이 존재하고 $r = \frac{d a_1}{d b_1} = \frac{a_1}{b_1}$이므로 $b_1 \in S$인데, $d > 1$이므로 $b_1 = \frac{b_0}{d} < b_0$ — $b_0$의 최소성과 모순이다. 따라서 공통 약수는 $\pm 1$뿐이고 $\frac{a_0}{b_0}$은 기약분수다. $\blacksquare$ **복기.** 여기까지가 양의 유리수다. 21주차가 인정하고 쓴 것은 모든 유리수에 대한 진술이므로 $r = 0$($\frac{0}{1}$이 기약)과 $r < 0$($-r$의 기약 표현에 음부호를 옮긴다)의 확장 두 줄까지 적어야 회수가 끝난다 — 예제 2.3의 확장 단락과 같다. ### 문제 6 **접근.** 예제 2.1이 주는 두 경우 각각에서 소수 하나를 지목하고 그것이 약수임을 정의 2.1로 확인한다. "소수들의 곱이면 그 소수가 약수다"를 넘기지 말고 등식으로 적는다. **풀이.** $n \ge 2$인 정수라 하자. 예제 2.1에 의해 $n$은 소수이거나 소수들의 곱이다. $n$이 소수이면 $n = n \times 1$이므로 $n \mid n$이고, $n$ 자신이 소수인 약수다. $n$이 소수들의 곱이면 $n = p_1 p_2 \cdots p_t$ ($t \ge 1$, 각 $p_i$는 소수)로 쓸 수 있고, $n = p_1 \cdot (p_2 \cdots p_t)$이며 $p_2 \cdots p_t$는 정수이므로 정의 2.1에 의해 $p_1 \mid n$이다. 따라서 어느 경우든 $n$은 소수인 약수를 가진다. $\blacksquare$ **소비처.** 21주차 예제 2.3(소수는 무한히 많다)이 이 사실을 첫 걸음으로 쓴다 — 유한한 소수 목록에서 $N = p_1 p_2 \cdots p_t + 1$을 만든 뒤 "$N \ge 2$는 소수인 약수 $p$를 가진다"로 시작한다. 이제 그 한 줄이 근거 ④가 되었으므로 그 증명이 자립한다. ### 문제 7 **접근.** 빈칸을 채우는 것이 아니라 백지에서 전체를 쓴다. 검사할 것은 둘이다 — 경우 나누기가 전체를 덮는가, 경우 2에서 $j \le k$를 명시했는가(강한 가정을 쓸 자격). **풀이.** 강한 귀납법으로 증명한다. **[기초]** $n = 1$: $1 = 2^0 \cdot 1$이고 $1$은 홀수다. ✓ **[귀납]** 1부터 $k$까지의 모든 자연수에서 성립한다고 가정하자. 모든 정수는 짝수이거나 홀수이므로(나눗셈 정리 — 예제 2.2와 문제 10) 두 경우로 나눈다. **경우 1: $k+1$이 홀수.** $k+1 = 2^0 \cdot (k+1)$이고 지수 $0 \ge 0$은 정수, $k+1$은 홀수이므로 꼴이 완성된다. **경우 2: $k+1$이 짝수.** 정의 1.1에 의해 $k+1 = 2j$인 정수 $j$가 존재하고, $k+1 \ge 2$이므로 $j \ge 1$인 자연수이며, $k \ge 1$에서 $k + 1 \le 2k$이므로 $j = \frac{k+1}{2} \le k$이다. 따라서 강한 귀납 가정에 의해 $j = 2^a m$ ($a \ge 0$은 정수, $m$은 홀수)이고, $k+1 = 2j = 2^{a+1} m$이다. 강한 귀납법에 의해 모든 자연수에서 성립한다. $\blacksquare$ **검산.** $n = 40$: $40 = 2 \cdot 20 = 2^2 \cdot 10 = 2^3 \cdot 5$이고 5는 홀수다 ✓. 증명이 하는 일이 이 반복이며, "반복이 끝난다"를 보장하는 것이 강한 귀납 가정이다. ### 문제 8 **접근.** 보폭이 3이므로 기초가 세 개다. 확인할 것은 하나 — $k+1$에서 3을 뺀 $k-2$가 가정 범위에 들어오는가. $k+1 \ge 11$이 정확히 $k - 2 \ge 8$을 주고, 남은 일은 3을 한 장 더 얹는 것뿐이다. **풀이.** 강한 귀납법으로 증명한다. **[기초]** $8 = 3 + 5$, $9 = 3 \cdot 3$, $10 = 5 \cdot 2$ ✓✓✓ (각각 $a, b \ge 0$). **[귀납]** $k \ge 10$에 대해, $8$부터 $k$까지의 모든 정수가 $3a + 5b$ 꼴이라고 가정하자. $k+1 \ge 11$이므로 $k + 1 - 3 = k - 2 \ge 8$이고 $k - 2 \le k$이므로 $k-2$는 가정 범위 안에 있다. 강한 귀납 가정에 의해 $k - 2 = 3a + 5b$인 음이 아닌 정수 $a, b$가 존재한다. 그러면 $$ k + 1 = (k-2) + 3 = 3a + 5b + 3 = 3(a+1) + 5b $$ 이고 $a + 1 \ge 0$, $b \ge 0$이다. 강한 귀납법에 의해 $n \ge 8$인 모든 정수에서 성립한다. $\blacksquare$ **논평 (예시).** 강한 귀납 버전은 "3을 한 장 얹는다"는 한 수로 끝나 경우 나누기가 없다 — 32주차 문제 15의 교체 논법보다 짧다. 대신 기초를 세 개 확인해야 한다. **보폭 $d$짜리 강한 귀납에는 기초가 $d$개** — 잊으면 문제 17의 참사가 재연된다. ### 문제 9 **접근.** 4단 서식으로 재현한다. ① 잔여들의 집합 $\to$ ② $q = 0$으로 비공 확인 $\to$ ③ 최소원소를 $r$로 명명 $\to$ ④ $r \ge n$을 가정해 $r - n \in S$로 모순. $r \ge 0$은 ③에서, $r < n$은 ④에서 나온다. **풀이.** 집합 $S = \{a - nq : q \in \mathbb{Z},\ a - nq \ge 0\}$을 생각하자. $q = 0$일 때 $a - n \cdot 0 = a$이고 가정에 의해 $a \ge 0$이므로 $a \in S$이고, 따라서 $S$는 공집합이 아닌 음이 아닌 정수들의 집합이다. 최소원리에 의해 $S$는 최소원소를 가지며, 그것을 $r = a - nq_0$ ($q_0 \in \mathbb{Z}$)이라 하자. $r \in S$이므로 $r \ge 0$이다. $r < n$을 귀류로 보인다. 만약 $r \ge n$이면 $$ r - n = (a - nq_0) - n = a - n(q_0 + 1) \ge 0 $$ 이므로 $r - n \in S$이다. 그런데 $n \ge 1$이므로 $r - n < r$이고, 이는 $r$가 $S$의 최소원소라는 것과 모순이다. 따라서 $r < n$이다. 그러므로 $q = q_0$, $r = a - nq_0$으로 두면 $a = nq + r$이고 $0 \le r < n$이다. $\blacksquare$ **확장까지 재현한다.** $a \ge 0$은 $S \neq \varnothing$을 확인한 줄에서만 쓰였으므로, $a < 0$일 때 $q = a$로 두면 $n \ge 1$에서 $1 - n \le 0$이고 $a < 0$이므로 $a - na = a(1-n) \ge 0$, 곧 $a - na \in S$이다. 이후는 위와 같다. 이 두 줄이 있어야 "모든 정수 $a$"라는 17주차의 인정 범위가 실제로 회수된다. ### 문제 10 **접근.** 두 표현을 하나의 등식에 놓고 분리하면 $r - r' = n(q' - q)$, 곧 $n \mid (r - r')$이다. 한편 두 나머지가 $[0, n)$ 안이므로 차의 절댓값은 $n$ 미만이다 — "배수인데 크기가 모자란다"는 상황에서 결론은 0뿐이다. **풀이.** $a = nq + r = nq' + r'$이고 $0 \le r, r' < n$이라 하자. 두 표현을 같게 놓으면 $nq + r = nq' + r'$이고, 정리하면 $$ r - r' = n(q' - q) $$ 이다. $q' - q$는 정수이므로 정의 2.1에 의해 $n \mid (r - r')$이다. 한편 $0 \le r < n$이고 $0 \le r' < n$이므로 $-n < r - r' < n$, 곧 $|r - r'| < n$이다. "자연수 $n$과 정수 $m$에 대해 $n \mid m$이고 $|m| < n$이면 $m = 0$"이라는 보조정리 (25주차 예제 2.2)에 의해 $r - r' = 0$, 즉 $r = r'$이다. 이를 위 등식에 대입하면 $n(q' - q) = 0$이고 $n \ge 1 \neq 0$이므로 $q' - q = 0$, 즉 $q = q'$이다. $\blacksquare$ ### 문제 11 **접근.** §1.6의 서식을 그대로 따른다. 최소 반례 $m$을 잡고 $n = 1$의 직접 확인으로 $m \ge 2$를 얻으면, $m - 1$은 최소성에 의해 반례가 아니다. 남은 것은 양변에 $m$을 더하는 한 걸음이다. **풀이.** 모순을 위해 공식이 성립하지 않는 자연수가 있다고 가정하자. 반례들의 집합 $S = \{n \in \mathbb{N} : 1 + 2 + \cdots + n \neq \frac{n(n+1)}{2}\}$은 공집합이 아니므로, 최소원리에 의해 최소원소 $m$이 존재한다. $n = 1$일 때 좌변은 $1$, 우변은 $\frac{1 \cdot 2}{2} = 1$로 공식이 성립하므로 $1 \notin S$이고, 따라서 $m \ge 2$이다. 그러면 $m - 1$은 자연수이고 $m - 1 < m$이므로 $m$의 최소성에 의해 $m - 1 \notin S$이다. 곧 $$ 1 + 2 + \cdots + (m-1) = \frac{(m-1)m}{2} $$ 이다. 양변에 $m$을 더하면 $$ 1 + 2 + \cdots + m = \frac{(m-1)m}{2} + m = \frac{(m-1)m + 2m}{2} = \frac{m(m+1)}{2} $$ 이므로 $m$에서도 공식이 성립한다. 이는 $m \in S$라는 것과 모순이다. 따라서 $S = \varnothing$이고, 모든 자연수에서 공식이 성립한다. $\blacksquare$ **복기.** 31주차의 귀납 증명과 나란히 놓아 보면 자리만 바뀌었다 — 기초 확인이 "$m \ge 2$"를 만드는 데 쓰이고 귀납 단계가 "$m-1 \to m$"으로 방향을 바꿨을 뿐 계산은 같다(문제 20(a)의 근거). 이 증명의 ④는 **④-b** 갈래다 — $S$의 더 작은 원소를 만든 것이 아니라, 최소성이 준 "$m-1$은 반례가 아니다"로 $m$도 반례가 아님을 보여 $m \in S$와 충돌시켰다. 예제 2.2$\cdot$2.3의 ④-a와 충돌 상대가 다르다(§2의 4단 서식). ### 문제 12 **접근.** 문제 8과 같은 구조이고 숫자만 다르다. 보폭이 4이므로 기초가 네 개이고, 확인할 것은 $k + 1 - 4 \ge 12$인가이다 — $k \ge 15$에서 $k - 3 \ge 12$가 나온다. **풀이.** 강한 귀납법으로 증명한다. **[기초]** $12 = 4 \cdot 3$, $13 = 4 \cdot 2 + 5$, $14 = 4 + 5 \cdot 2$, $15 = 5 \cdot 3$ ✓✓✓✓ (각각 $a, b \ge 0$). **[귀납]** $k \ge 15$에 대해, $12$부터 $k$까지의 모든 정수가 $4a + 5b$ 꼴이라고 가정하자. $k + 1 \ge 16$이므로 $k + 1 - 4 = k - 3 \ge 12$이고 $k - 3 \le k$이므로 가정 범위 안에 있다. 강한 귀납 가정에 의해 $k - 3 = 4a + 5b$인 음이 아닌 정수 $a, b$가 존재하고, $k + 1 = (k - 3) + 4 = 4(a+1) + 5b$이다. 강한 귀납법에 의해 $n \ge 12$인 모든 정수에서 성립한다. $\blacksquare$ ### 문제 13 **접근.** (a)는 $1 < \sqrt2 < 2$의 각 변에 $b_0 > 0$을 곱하는 조작이다. (b)가 중심이다 — $a_1^2$과 $2b_1^2$을 전개한 뒤 $a_0^2 = 2b_0^2$을 대입해 비교한다. (c)는 (a)의 $a_0 < 2b_0$이 그대로 쓰인다. **풀이.** **(a)** $\sqrt2 = \frac{a_0}{b_0}$이고 $1^2 < 2 < 2^2$이므로 $1 < \sqrt2 < 2$이다 (16주차의 제곱 비교). 곧 $1 < \frac{a_0}{b_0} < 2$이고, 각 변에 $b_0 > 0$을 곱하면 $b_0 < a_0 < 2b_0$이다. **(b)** (a)에서 $a_0 - b_0 > 0$이고 $2b_0 - a_0 > 0$이므로 $a_1 = 2b_0 - a_0$과 $b_1 = a_0 - b_0$은 모두 자연수다(정수의 차는 정수, 근거 ②). 가정의 양변을 제곱하면 $a_0^2 = 2b_0^2$이다. 이제 두 값을 각각 전개한다. $$ a_1^2 = (2b_0 - a_0)^2 = 4b_0^2 - 4a_0b_0 + a_0^2 = 4b_0^2 - 4a_0b_0 + 2b_0^2 = 6b_0^2 - 4a_0b_0 $$ $$ 2b_1^2 = 2(a_0 - b_0)^2 = 2a_0^2 - 4a_0b_0 + 2b_0^2 = 4b_0^2 - 4a_0b_0 + 2b_0^2 = 6b_0^2 - 4a_0b_0 $$ (둘 다 마지막에서 두 번째 등호에서 $a_0^2 = 2b_0^2$을 대입했다.) 두 값이 같으므로 $a_1^2 = 2b_1^2$이고, $b_1 > 0$이므로 $\left(\frac{a_1}{b_1}\right)^2 = 2$이며 $\frac{a_1}{b_1} > 0$이다. 따라서 $\frac{a_1}{b_1} = \sqrt2$이다. **(c)** (a)에서 $a_0 < 2b_0$이므로 $b_1 = a_0 - b_0 < 2b_0 - b_0 = b_0$이다. 곧 $\frac{a_1}{b_1}$은 $\sqrt2$의 분수 표현이면서 분모가 $b_0$보다 작다 — $b_0$이 최소 분모라는 것과 모순이다. 따라서 $\sqrt2$의 자연수 분수 표현은 존재하지 않고, $\sqrt2$는 무리수다. $\blacksquare$ ### 문제 14 **접근.** 증명 대상이 명제가 아니라 원리라는 점만 다르고 안쪽은 최소 반례법 그대로다. 재료는 둘 — 기초는 $m \neq 1$을 만드는 데, 전달 장치는 $m-1$에서 $m$으로 넘어가는 데 쓰인다. **풀이.** $P(1)$이 참이고 모든 $k$에서 $P(k) \Rightarrow P(k+1)$이 성립한다고 하자. 모순을 위해 $P$가 거짓인 자연수가 있다고 가정하면 반례들의 집합 $S = \{n \in \mathbb{N} : P(n)$이 거짓$\}$은 공집합이 아니고, 최소원리에 의해 최소원소 $m$을 가진다. $P(1)$이 참이므로 $1 \notin S$, 곧 $m \ge 2$이다. 그러면 $m - 1$은 자연수이고 $m - 1 < m$이므로 $m$의 최소성에 의해 $m - 1 \notin S$, 곧 $P(m-1)$이 참이다. 전달 장치를 $k = m - 1$에 적용하면 $P(m)$이 참인데 이는 $m \in S$와 모순이다. 따라서 $S = \varnothing$이고 모든 자연수 $n$에서 $P(n)$이 참이다 — 이것이 귀납법의 결론이다. $\blacksquare$ ### 문제 15 **접근.** 분해형 강한 귀납이다. 최대의 $2^j$를 떼어내고 잔여 $r = k+1-2^j$에 강한 가정을 적용한다. 확인할 것이 셋 — $r$이 자연수인가, $r \le k$인가, $r < 2^j$인가. 셋째가 "서로 다름"을 만드는 조각이다. **풀이.** 강한 귀납법으로 증명한다. **[기초]** $n = 1 = 2^0$ — 한 항짜리 합이다. ✓ **[귀납]** $1$부터 $k$까지 성립한다고 가정하자. $k+1$에 대해, $2^j \le k+1$인 최대의 $j$를 잡는다 ($2^0 = 1 \le k+1$이므로 그런 $j$가 존재하고, 후보는 유한한 음이 아닌 정수의 집합이므로 최대가 있다 — 도전 문제군 앞의 상자). **경우 1: $2^j = k+1$.** 그 자체로 한 항짜리 합이므로 완료된다. **경우 2: $2^j < k+1$.** $r = k+1-2^j$라 하면 $1 \le r \le k+1-1 = k$이므로 강한 귀납 가정에 의해 $r$는 서로 다른 2의 거듭제곱들의 합이다. 또한 $r < 2^j$이다 — 만약 $r \ge 2^j$이면 $k+1 = 2^j + r \ge 2^{j+1}$이 되어 $j$의 최대성과 모순이기 때문이다. 따라서 $r$의 표현에 등장하는 거듭제곱들은 전부 $2^j$보다 작고, 거기에 $2^j$를 보태도 서로 다름이 유지된다. 곧 $k+1 = 2^j + r$은 서로 다른 2의 거듭제곱들의 합이며, 강한 귀납법에 의해 모든 자연수에서 성립한다. $\blacksquare$ ### 문제 16 **접근.** (a)는 조건 "소수"의 하중을 재는 문제다. 소수가 아닌 $p$를 두 인수로 쪼개 $a$와 $b$에 하나씩 배정하면 결론이 무너진다(2주차 문제 15). (b)는 존재와 유일의 차이를 서술로 정리하는 문제다. **풀이.** **(a)** $p = 6$으로 잡는다($6 = 2 \times 3$이므로 소수가 아니다). $a = 4$, $b = 9$라 하면 $ab = 36 = 6 \times 6$이므로 $6 \mid 36$이다. 그러나 $4 = 6c$인 정수 $c$도, $9 = 6c$인 정수 $c$도 없으므로 $6 \nmid 4$이고 $6 \nmid 9$이다. 곧 가정은 참인데 결론이 거짓이므로, 이 반례가 소수 조건이 본질적임을 보인다. **(b)** (예시 답안) 존재성은 "쪼개질 때까지 쪼갠다"로 도달하지만, 유일성은 "서로 다르게 쪼갠 두 결과가 반드시 일치한다"는 전혀 다른 주장이다. 한쪽 분해의 소수 $p$가 다른 쪽 분해의 곱을 나누므로, 유클리드 보조정리가 있어야 $p$가 그 곱의 **어느 인수 하나**를 나눈다고 결론할 수 있고 그 인수도 소수이므로 $p$와 같아진다. 이 장치가 없으면 겹치지 않는 두 분해의 공존을 배제할 방법이 없다. ### 문제 17 **접근.** 결론부터 의심한다. 정의대로 계산하면 $c_2 = 4 \neq 2$에서 곧바로 반박된다. 제시된 증명의 계산은 한 줄도 틀리지 않았으므로 오류는 설정에 있다 — 참조하는 과거가 몇 칸 뒤인지 센다. **풀이.** **결함.** 점화식이 두 칸 전($c_{n-2}$)을 참조하므로 **보폭이 2**이고, 기초는 $n = 1$과 $n = 2$ 두 개가 필요한데 제시된 증명은 $c_1$ 하나만 확인했다. 또 귀납 단계의 등식 $c_{k+1} = c_{k-1} + 2$는 점화식의 정의상 $k + 1 \ge 3$에서만 뜻이 있으므로 $P(2)$를 만들어 내지 못한다. 곧 $P(2)$가 기초에서도 귀납에서도 확보되지 않아, 전달 장치는 짝수 번째 항 전체를 하나도 세우지 못한다. **반박.** 정의대로 계산하면 $c_2 = 4 \neq 2$이고 $c_4 = c_2 + 2 = 6 \neq 4$이므로 명제는 거짓이다. 실제로 홀수 항은 $c_{2m+1} = 2m+1$로 참이지만 짝수 항은 $c_{2m} = 2m + 2$로 항상 2만큼 크다 — 명제가 절반에서만 성립한다. ### 문제 18 **접근.** 최소원리는 수열이 아니라 집합에 적용된다. 항들의 값을 모두 모으면 공집합이 아닌 자연수의 부분집합이 되고, 그 최소원소에 이름을 붙이면 다음 항이 곧 모순이다. **풀이.** 모순을 위해 그런 수열 $a_1 > a_2 > a_3 > \cdots$ (모든 $a_i \in \mathbb{N}$)가 존재한다고 가정하자. 값들의 집합 $S = \{a_i : i \in \mathbb{N}\}$을 생각하면 $a_1 \in S$이므로 $S$는 공집합이 아닌 자연수의 부분집합이다. 최소원리에 의해 $S$는 최소원소를 가지며, 그것은 어떤 항의 값이므로 $a_m$이라 쓸 수 있다. 그런데 수열이 순감소이므로 $a_{m+1} < a_m$이고 $a_{m+1} \in S$이다. 이는 $a_m$이 $S$의 최소원소라는 것과 모순이다. 따라서 그런 수열은 존재하지 않는다. $\blacksquare$ **연결.** 문제 13의 하강은 같은 조작을 반복해 $b_0 > b_1 > b_2 > \cdots$라는 순감소 무한 수열을 만들어 내므로 이 원리에 의해 애초에 불가능하다 — 최소원리를 수열의 언어로 바꿔 쓴 무한 강하법이다. ### 문제 19 **접근.** (a)는 후보가 유한함을 먼저 보인다 — $7b \le 17$이므로 $b \in \{0, 1, 2\}$뿐이고, 각각에서 남은 금액이 4의 배수인지 확인한다. (b)는 보폭 4이고 구조는 문제 12와 같다. **풀이.** **(a)** $17 = 4a + 7b$인 음이 아닌 정수 $a, b$가 있다고 하자. $7b \le 17$이므로 $b \le 2$, 곧 $b \in \{0, 1, 2\}$다. $b = 0$이면 $4a = 17$인데 $17 = 4 \cdot 4 + 1$로 4의 배수가 아니다. $b = 1$이면 $4a = 10$인데 $10 = 4 \cdot 2 + 2$로 4의 배수가 아니다. $b = 2$이면 $4a = 3$인데 $3$은 4의 배수가 아니다. 세 경우가 후보 전부를 덮고 어느 경우에도 해가 없으므로 17원은 만들 수 없다. $\blacksquare$ **(b)** 강한 귀납법으로 증명한다. **[기초]** $18 = 4 + 7 \cdot 2$, $19 = 4 \cdot 3 + 7$, $20 = 4 \cdot 5$, $21 = 7 \cdot 3$ ✓✓✓✓. **[귀납]** $k \ge 21$에 대해, $18$부터 $k$까지의 모든 정수가 $4a + 7b$ 꼴이라고 가정하자. $k+1 \ge 22$이므로 $k + 1 - 4 = k - 3 \ge 18$이고 $k - 3 \le k$이므로 가정 범위 안에 있다. 강한 귀납 가정에 의해 $k - 3 = 4a + 7b$이고, $k + 1 = (k-3) + 4 = 4(a+1) + 7b$이다. 강한 귀납법에 의해 $n \ge 18$인 모든 정수에서 성립한다. $\blacksquare$ **복기.** (a)와 (b)를 합치면 17이 마지막 불가능 금액이다. 서로소인 $m, n$ 우표에 대해 그 값은 $mn - m - n$이며(정수론의 프로베니우스 수), 여기서는 $4 \cdot 7 - 4 - 7 = 17$로 일치한다. ### 문제 20 **접근.** (a)는 문제 14(최소원리에서 귀납법이 나온다)와 문제 11(같은 명제가 두 문법으로 증명된다)을 근거로 든다. (b)는 정답이 하나가 아니지만 근거가 §1.4의 신호와 §1.6의 쓰임 표에 닿아 있어야 한다. **풀이.** (예시 답안) **(a)** 최소원리에서 귀납법이 유도되고(문제 14), 귀납법으로 증명되는 것은 최소 반례법 으로도 증명된다(문제 11에서 두 뼈대가 그대로 겹쳤다). 강한 귀납법은 보통 귀납의 가정을 넓힌 것이므로 셋은 서로를 유도한다. 곧 셋은 자연수의 같은 성질 — 1에서 시작해 한 칸씩 세어 나가고 무한히 작아지는 하강은 없다 — 을 세 가지 문법으로 적은 것이다. **(b)** (예시) ① 명제가 $n$에 대한 등식$\cdot$부등식이고 $k+1$의 식에서 $k$의 식이 바로 보이면 보통 귀납을 꺼낸다. ② $k+1$이 곱으로 쪼개지거나 성질이 몇 칸 뒤에서 오면 강한 귀납을 꺼내고 보폭만큼 기초를 확인한다. ③ "~은 존재하지 않는다", "모든 표현은 ~"처럼 반례나 후보 집합을 상정하기 좋은 꼴이면 최소원리를 먼저 스케치한다. --- **다음 주 예고:** 점화식으로 정의된 수열을 다룬다. 피보나치 수열을 무대로 "추측하고 귀납으로 확정하는" 실전 순환을 익히고, 두 칸 보폭 귀납(기초 두 개)을 반복 훈련한다. $F_1^2 + \cdots + F_n^2 = F_n F_{n+1}$ 같은 항등식이 증명 대상이 되며, 이번 주 §1.4의 보폭 규칙과 문제 17의 진단이 그대로 재사용된다.