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

## 예제 — 조건문 귀류 증명을 함께 만들기

### 예제 2.1 — 조건문 귀류의 기본형

**명제.** $a \ge 2$인 정수 $a$와 임의의 정수 $b$에 대해, $a \nmid b$ 또는 $a \nmid (b+1)$이다.

말로 옮기면 "2 이상의 정수는 연속한 두 정수를 동시에 나눌 수 없다"이다. 겉모습은 조건문이 아니지만, "$a \ge 2$인 정수 $a$에 대해"가 가정이므로 $P \Rightarrow Q$ 꼴로 읽을 수 있다.

**설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 도착점을 먼저 정한다. 귀류에서는 도착점이 "아무 모순"이므로, 대신 **충돌 후보**를 적어 둔다.

|  | **말** | **번역** |
|---|---|---|
| $P$ (그대로 유지) | $a$는 $2$ 이상의 정수 | $a \ge 2$ |
| $Q$ (부정할 것) | $a \nmid b$ 또는 $a \nmid (b+1)$ | — |
| $\neg Q$ — 새 출발점 | $\underline{\quad(1)\quad}$ | $b = ak$, $b + 1 = am$인 정수 $k, m$이 존재 |
| 충돌 후보 | $P$ 자체 | $\underline{\quad(2)\quad}$와 부딪히는 문장을 만든다 |

:::{container} quotebox
**확인 12.** 번역표의 빈칸 (1)(2)를 채워 보자. (1)에서 "또는"의 부정에 적용할 규칙의 이름을 함께 적는다.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $a \mid b$이고 $a \mid (b+1)$이다 — 드모르간 2(11주차 §1.3 둘째 행)로

"또는"이 "그리고"가 되고, $\nmid$의 부정은 $\mid$다.

(2) $a \ge 2$. 부정한 결과 손에 들어온 것이 등식 두 개이므로 전개가

시작된다. 직접 증명에서는 "나누지 않는다"를 만들어야 했는데 만들 꼴이

없었다 — 부정이 그 자리를 재료로 바꿨다.
:::

**1단계 — 두 가정을 둘 다 선언한다.** 서식(§1.4)의 첫 줄이다.

:::{container} quotebox
**확인 13.** 첫 문장을 완성해 보자: "모순을 이끌어내기 위해, $\underline{\quad}$인데 $\underline{\qquad}$이고 $\underline{\qquad}$라고 가정하자."
:::

:::{admonition} 답
:class: quotebox dropdown

"모순을 이끌어내기 위해, $a \ge 2$인데 $a \mid b$이고 $a \mid (b+1)$이라고

가정하자." $P$($a \ge 2$)를 빠뜨리면 §1.3 삭제 실험의 상황이 되어 충돌할

상대가 사라진다 — 실제로 $a = 1$이면 $1 \mid b$이고 $1 \mid (b+1)$이므로

$\neg Q$만으로는 모순이 없다.
:::

**2단계 — 두 재료를 결합한다.** 손에 $a \mid b$와 $a \mid (b+1)$이 있다. 둘을 함께 쓰는 부품이 2주차 문제 17이다.

:::{container} quotebox
**확인 14.** 둘째 문장을 완성해 보자: "$a \mid (b+1)$이고 $a \mid b$이므로 $a \mid \big(\underline{\qquad}\big) = \underline{\quad}$이다." 근거는 무엇인가.
:::

:::{admonition} 답
:class: quotebox dropdown

"$a \mid \big((b+1) - b\big) = 1$이다." 근거는 2주차 문제 17($a \mid (b+c)$이고

$a \mid b$이면 $a \mid c$)이며, $c$ 자리에 $1$이 들어간 판이다. 두 배수의

차를 잡는 것이 이 유형의 상투 수단이다 — 큰 정보 두 개에서 작은 정보 하나를

짜내면 $1$처럼 다루기 쉬운 수가 남는다.
:::

**3단계 — $a \mid 1$을 $a$에 대한 부등식으로 바꾼다.** 지금 손에 있는 것은 "$a$가 1을 나눈다"이고, 충돌시킬 상대는 부등식 $a \ge 2$다. 같은 언어로 맞춰야 부딪힌다.

:::{container} quotebox
**확인 15.** $a \mid 1$에서 $a$에 대해 무엇을 말할 수 있는가. 근거는 §1.9의 무엇인가.
:::

:::{admonition} 답
:class: quotebox dropdown

$a = 1$ 또는 $a = -1$이다 — 보조 명제 22.A. 어느 쪽이든 $a \le 1$이므로

$a \ge 2$일 수 없다. 부등식과 나누어떨어짐은 서로 다른 언어이므로, 충돌을

만들려면 한쪽을 다른 쪽의 언어로 번역해야 한다. 22.A가 그 번역기다.
:::

**4단계 — 충돌을 지목하고 원명제를 회수한다.**

:::{container} quotebox
**확인 16.** 마지막 문장을 완성해 보자: "이는 $\underline{\qquad}$와 모순이다. 따라서 $\underline{\qquad}$. $\blacksquare$"
:::

:::{admonition} 답
:class: quotebox dropdown

"이는 $a \ge 2$라는 가정과 모순이다. 따라서 $a \nmid b$ 또는 $a \nmid (b+1)$이다.

$\blacksquare$" 충돌한 두 문장은 "$a \ge 2$"와 "$a \le 1$"이며, 정수 $a$에

대해 이 둘은 동시에 성립할 수 없다. ($\neg C$라는 이름을 붙이려면 한 줄이

더 필요하다 — $\neg(a \ge 2)$는 11주차 §1.3에 의해 $a < 2$이고, $a$가

정수이므로 거기서 $a \le 1$이 나온다. 모순을 선언하는 데 그 이름이 꼭

필요하지는 않다.) 마지막 줄에서 두 문장을 지목하는 것이 도착점의 확인이다.
:::

**완성본.** 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다.

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| 모순을 이끌어내기 위해, $a \ge 2$인데 $a \mid b$이고 $a \mid (b+1)$이라고 가정하자. | 서식의 첫 줄. "또는"의 부정은 드모르간 2로 "그리고"가 된다(11주차). 가정 $P$를 함께 적어야 충돌 상대가 무대에 남는다. |
| $a \mid (b+1)$이고 $a \mid b$이므로 $a \mid \big((b+1) - b\big) = 1$이다. | 두 재료를 결합하는 부품이 2주차 문제 17(근거 ④). 두 배수의 차에서 $1$을 짜냈다. |
| 보조 명제 22.A에 의해 $a = 1$ 또는 $a = -1$이므로 $a \le 1$이다. | 나누어떨어짐을 부등식의 언어로 번역(근거 ④). 충돌시키려면 두 문장이 같은 언어여야 한다. |
| 이는 $a \ge 2$라는 가정과 모순이다. 따라서 $a \nmid b$ 또는 $a \nmid (b+1)$이다. $\blacksquare$ | 충돌한 두 문장($a \ge 2$와 $a \le 1$)을 지목하고 원명제를 회수한다. |

**이 네 줄이 "모든" 경우를 처리하는 이유.** 완성본의 문자에 구체적인 수를 넣어 읽어 보자.

:::{container} quotebox
**확인 17.** $a = 6$, $b = 20$일 때 둘째 줄과 셋째 줄은 각각 어떤 문장이 되는가. $a = 2$, $b = 7$이면 어떤가.
:::

:::{admonition} 답
:class: quotebox dropdown

$a = 6$, $b = 20$: 가정은 "$6 \mid 20$이고 $6 \mid 21$"이 된다. 둘째 줄은

"$6 \mid (21 - 20) = 1$", 셋째 줄은 "$6 \le 1$"이 되어 $6 \ge 2$와 부딪힌다.

$a = 2$, $b = 7$: 가정은 "$2 \mid 7$이고 $2 \mid 8$", 둘째 줄은 "$2 \mid 1$",

셋째 줄은 "$2 \le 1$"이 되어 역시 부딪힌다.

어느 수를 넣어도 네 줄이 그대로 성립한다. 증명의 어느 줄도 $a$나 $b$가

특정한 수라는 사실을 쓰지 않았기 때문이다.
:::

**해석.** 이 명제는 "연속한 두 정수는 서로소"라는 이름으로 정수론에서 상시 사용된다. 21주차 예제 2.3(소수 무한)에서 $p \mid 1$로 모순을 만들던 것과 같은 부품이다 — 그때도 목록의 소수 $p$가 $2$ 이상이라는 사실이 충돌의 한쪽이었다.

### 예제 2.2 — "또는" 결론의 귀류

**명제.** 실수 $x, y$에 대해, $x + y \ge 2$이면 $x \ge 1$ 또는 $y \ge 1$이다.

이번에는 설계만 함께 하고, 증명은 완성된 산문으로 본다.

:::{container} quotebox
**확인 18.** 번역표를 채워 보자.

$P$: $\underline{\qquad}$ / $Q$: $\underline{\qquad}$ /

$\neg Q = \underline{\qquad}$ / 첫 줄에 적을 가정 $P \land \neg Q = \underline{\qquad}$.

그리고 직접 증명이 막히는 이유를 한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$P$는 "$x + y \ge 2$", $Q$는 "$x \ge 1$ 또는 $y \ge 1$"이다. 드모르간 2와

$\ge$의 부정($<$)에 의해 $\neg Q$는 "$x < 1$이고 $y < 1$"이다. 첫 줄에 적을

가정은 "$x + y \ge 2$인데 $x < 1$이고 $y < 1$"이다.

직접 증명이 막히는 이유: 결론이 "또는"이므로 어느 쪽이 참인지 지목해야 하는데,

$x + y \ge 2$만으로는 지목할 수 없다($x = 100$일 수도 $y = 100$일 수도 있다).

부정하면 그 "또는"이 부등식 두 개가 되어 손에 들어온다.
:::

**증명.** 모순을 이끌어내기 위해, $x + y \ge 2$인데 $x < 1$이고 $y < 1$이라고 가정하자. 두 부등식을 변끼리 더하면(16주차 문제 2(c))

$$
x + y < 1 + 1 = 2
$$

이다. 이는 가정 $x + y \ge 2$와 모순이다. 따라서 $x \ge 1$ 또는 $y \ge 1$이다. $\blacksquare$

:::{container} quotebox
**확인 19.** 이 증명을 대우로 다시 쓰면 어떤 명제를 증명하게 되는가. 몸통은 얼마나 달라지는가.
:::

:::{admonition} 답
:class: quotebox dropdown

대우는 "$x < 1$이고 $y < 1$이면 $x + y < 2$이다"이고, 몸통은 "두 부등식을

변끼리 더한다" 한 줄로 위와 완전히 같다. 이 증명에서 $P$($x + y \ge 2$)는

마지막 충돌 선언에서만 쓰였으므로, §1.6의 관찰대로 **충돌 상대를 $P$로 정해

둔 귀류법** — 곧 대우 증명이다. 어느 쪽으로 적어도 정답이며, 서식만 정확하면

된다. 19주차 예제 2.3은 부등호를 $>$로 두고 숫자만 다르게 한 같은 유형을

대우로 증명한 자리다. 다만 부등호의 종류가 다르므로 몸통의 마지막 단계도

다르다 — 이번 주는 엄격 부등식 $x < 1$과 $y < 1$을 변끼리 더하는 16주차

문제 2(c)의 엄격 판본을 쓰고, 19주차는 $x \le 5$와 $y \le 5$를 (W2) 두 번과

추이성 (W6)으로 잇는 $\le$ 판본을 쓴다. 두 판본을 나란히 놓고 비교해 둔다

(문제 9 복기의 일반형 $x + y \ge 2s$와도 맞물린다).
:::

### 예제 2.3 — 귀류와 경우 나누기의 조합

**명제.** $x^2 - y^2 = 2$를 만족하는 정수 $x, y$는 존재하지 않는다.

이번에는 설계부터 스스로 해 보자.

:::{container} quotebox
**확인 20.** 첫 줄에 가정할 $\neg P$는 무엇이고, 그 가정이 손에 쥐여 주는 것은 무엇인가. 그 등식을 곱의 꼴로 바꾸면 어떻게 되는가.
:::

:::{admonition} 답
:class: quotebox dropdown

$\neg P$는 "$x^2 - y^2 = 2$를 만족하는 정수 $x, y$가 존재한다"이다(21주차

§1.6 둘째 신호 — 비존재의 부정은 존재이고, 존재하는 대상에는 이름을 붙일 수

있다). 손에 들어오는 것은 그런 정수 $x, y$와 등식 $x^2 - y^2 = 2$다.

인수분해하면 $(x - y)(x + y) = 2$ — 곱이 2가 되는 정수 두 개를 손에 쥔 셈이다.
:::

**증명.** 모순을 이끌어내기 위해, $x^2 - y^2 = 2$를 만족하는 정수 $x, y$가 존재한다고 가정하자. 인수분해하면

$$
(x - y)(x + y) = 2
$$

이다. 여기서 $(x - y) + (x + y) = 2x$는 짝수이므로, $x - y$와 $x + y$는 **같은 홀짝**이다. 만약 홀짝이 다르다면 그 합이 홀수가 되어(1주차 빈칸 사다리 훈련 1: 홀수와 짝수의 합은 홀수) $2x$가 짝수라는 것과 어긋나기 때문이다. 정수는 짝수이거나 홀수이므로(17주차 짝/홀 분할) 두 경우만 검사하면 된다.

**경우 1: $x - y$와 $x + y$가 둘 다 짝수.** $x - y = 2s$, $x + y = 2t$인 정수 $s, t$가 존재하므로 곱은 $(2s)(2t) = 4st$이고 $st$는 정수이므로 $4 \mid 2$가 된다. 그러나 $2 = 4c$인 정수 $c$는 없다($c = \frac{1}{2}$은 정수가 아니다). 모순이다.

**경우 2: $x - y$와 $x + y$가 둘 다 홀수.** 홀수와 홀수의 곱은 홀수이므로 (1주차 문제 8) $(x-y)(x+y)$는 홀수다. 그러나 $2 = 2 \times 1$이므로 2는 짝수다. 곧 같은 수가 짝수이면서 홀수가 되어 모순이다(문제 5에서 증명할 사실 — 지금은 인정하고 쓴다).

두 경우가 전체를 빠짐없이 덮고 어느 경우든 모순이므로, 그런 정수 $x, y$는 존재하지 않는다. $\blacksquare$

:::{container} quotebox
**확인 21.** 이 증명에서 "같은 홀짝이다"를 근거 없이 적으면 무엇이 무너지는가.
:::

:::{admonition} 답
:class: quotebox dropdown

경우 나누기의 첫째 채점 기준 — 경우들이 전체를 빠짐없이 덮는가 — 가 무너진다

(17주차 §1.3). 근거 없이 두 경우만 검사하면 "하나는 홀수, 하나는 짝수"인

셋째 경우가 검사되지 않은 채 남는다. 합 $2x$가 짝수라는 관찰이 그 셋째 경우를

실제로 제거하는 문장이므로, 빠뜨리면 증명이 아니라 두 사례의 확인이 된다.
:::

**구조 읽기.** 귀류(존재 가정)가 문을 열어 등식을 손에 쥐여 주고, 경우 나누기 (17주차)가 두 갈래를 각각 봉쇄한다. 기법은 서로를 대체하는 것이 아니라 부품처럼 조립된다 — 귀류가 바깥 틀이고 경우 나누기가 안쪽 몸통이다.

### 관찰 — 세 예제의 같은 뼈대

세 예제는 소재가 각각 나누어떨어짐$\cdot$부등식$\cdot$인수분해로 전혀 다르다. 대응표의 빈칸을 채워 뼈대를 비교해 보자.

| **단계** | **예제 2.1** | **예제 2.2** | **예제 2.3** |
|---|---|---|---|
| ① $P$와 $\neg Q$를 둘 다 가정 | $a \ge 2$인데 $a \mid b$이고 $a \mid (b+1)$ | $\underline{\quad(1)\quad}$ | 그런 정수 $x, y$가 존재한다 ($P$가 따로 없는 단일 명제) |
| ② 두 가정을 결합해 모순 후보 제작 | $a \mid 1$에서 $a \le 1$ | 변끼리 더해 $x + y < 2$ | $\underline{\quad(2)\quad}$ |
| ③ 충돌 지목과 원명제 회수 | $a \le 1$ vs $a \ge 2$ | $x + y < 2$ vs $x + y \ge 2$ | $\underline{\quad(3)\quad}$ |

:::{container} quotebox
**확인 22.** 표의 빈칸 (1)(2)(3)을 채워 보자. 그리고 ③의 충돌 상대가 세 예제에서 각각 무엇이었는지 비교해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $x + y \ge 2$인데 $x < 1$이고 $y < 1$

(2) 인수분해 후 두 인수가 같은 홀짝임을 보이고, 경우마다 곱의 홀짝(또는 4의

배수 여부)을 판정한다

(3) 경우 1에서 $4 \mid 2$ vs $4 \nmid 2$, 경우 2에서 곱이 홀수 vs $2$는 짝수

충돌 상대 비교: 예제 2.1과 2.2는 둘 다 가정 $P$와 충돌했고 **몸통의 어느

줄도 $P$를 쓰지 않았으므로**, §1.6의 뜻에서 대우 증명으로 다시 쓸 수 있다.

예제 2.3은 $P$가 따로 없고 이미 아는 사실(4의 배수 판정, 짝/홀 배타성)과

충돌했으므로 대우로 바꿀 수 없다 — 귀류법이 대우보다 넓은 이유가 이 한 칸에

들어 있다.

조건 "몸통이 $P$를 쓰지 않았다"를 빠뜨리면 안 된다. 충돌 상대가 $P$인데도

옮겨 적을 수 없는 사례가 이번 주에 있다 — 문제 8이다(§1.6). 그 증명은 마지막에

가정의 조각 "$p$가 소수"와 충돌하지만 몸통이 다른 조각 "$p > 2$"를 이미

소비하고, 대우의 결론이 "또는"이 되어 §1.1 시도 3과 같은 자리에서 막힌다.
:::

방금 확인한 뼈대에 이름을 붙인다.

:::{admonition} 백지 암기 대상
:class: keybox

**조건문 귀류의 3단계 틀**

① $P$와 $\neg Q$를 **둘 다** 가정하고, 각각을 정의로 풀어 재료로 만든다 $\to$ ② 두 재료를 결합해 모순 후보를 제작한다 $\to$ ③ 충돌한 두 문장을 지목하고 원명제를 회수한다
:::

21주차의 3단계 틀과 다른 것은 ①뿐이다 — 가정이 하나에서 둘로 늘었다. 23주차에서는 같은 명제를 세 기법으로 각각 써 보며 ①의 선택 자체를 훈련한다.

## 빈칸 사다리 — 지지대를 하나씩 빼며

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

### 훈련 1 ●○○ — 수식 빈칸

**명제.** 정수 $n$에 대해, $n^2$이 홀수이면 $n$은 홀수이다.

**증명.** 모순을 이끌어내기 위해, $n^2$이 홀수인데 $n$이 $\underline{\quad(1)\quad}$라고 가정하자. 그러면 정의 1.1에 의해 $n = 2k$인 정수 $k$가 존재하고,

$$
n^2 = (2k)^2 = \underline{\quad(2)\quad}
$$

이므로 $n^2$은 짝수이다. 이는 $n^2$이 $\underline{\quad(3)\quad}$라는 가정과 모순이다(문제 5에서 증명할 사실 — 지금은 인정하고 쓴다). 따라서 $n^2$이 홀수이면 $n$은 홀수이다. $\blacksquare$

### 훈련 2 ●●○ — 수식과 근거를 함께

이번에는 구조 낱말과 근거 문장도 빈칸이다.

**명제.** 정수 $a, b$에 대해, $ab$가 홀수이면 $a$와 $b$는 모두 홀수이다.

**증명.** 모순을 이끌어내기 위해, $ab$가 홀수인데 $\underline{\quad(1)\quad}$라고 가정하자. 결론의 부정은 $\underline{\quad(2)\quad}$에 의해 "$a$가 짝수이거나 $b$가 짝수"이므로, 두 경우로 나눈다.

**경우 1: $a$가 짝수.** $a = 2s$인 정수 $s$가 존재하므로 $ab = \underline{\quad(3)\quad}$이고, $\underline{\quad(4)\quad}$이므로 $ab$는 짝수이다.

**경우 2: $b$가 짝수.** 이번에는 $b = 2t$인 정수 $t$가 존재하므로 $ab = 2(at)$이고 $at$는 정수이므로 $ab$는 짝수이다.

어느 경우든 $ab$는 짝수인데 가정에서 $ab$는 홀수이므로, 문제 5에서 증명할 사실(지금은 인정하고 쓴다)에 의해 이는 $\underline{\quad(5)\quad}$이다. 따라서 $ab$가 홀수이면 $a$와 $b$는 모두 홀수이다. $\blacksquare$

### 훈련 3 ●●● — 뼈대만 남기고

이번에는 3단계 틀(§2 관찰)의 각 칸을 통째로 채운다.

**명제.** $x^2 - y^2 = 10$을 만족하는 정수 $x, y$는 존재하지 않는다.

**증명의 뼈대.**

- ① 부정 가정과 재료 확보: $\underline{\quad(1)\quad}$
- ② 재료 결합과 모순 후보 제작: $\underline{\quad(2)\quad}$
- ③ 충돌 지목과 원명제 회수: $\underline{\quad(3)\quad}$

(예제 2.3과 같은 설계다. 두 인수의 홀짝을 먼저 묶은 뒤 경우마다 판정한다. 이 훈련이 문제 14의 예행연습이다.)

## 연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다.

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. 이번 주 답안에서 가장 자주 비는 칸은 세

군데다 — 첫 줄에 가정 $P$를 함께 적었는가, $\neg Q$를 11주차 규칙으로

정확히 만들었는가, 마지막 줄에 충돌한 두 문장을 지목했는가. 셋 중 하나라도

비면 몸통의 계산이 전부 옳아도 증명이 닫히지 않는다.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
:::

### 기본 ●○○

**1.** 다음 조건문을 귀류로 증명할 때 가정할 내용($P \land \neg Q$)을 정확히 쓰시오 (증명 불필요). (a) $x$가 무리수이면 $x + 3$은 무리수이다. (b) $a \mid b$이고 $a \nmid c$이면 $a \nmid (b + c)$이다. (c) $x + y > 10$이면 $x > 5$ 또는 $y > 5$이다.

:::{admonition} 힌트
:class: quotebox dropdown

세 항목 모두 §1.4 서식의 첫 문장을 채우는 일이다. $P$는 손대지 않고 그대로

옮겨 적고, $Q$만 11주차 총목록으로 부정한다. (a)는 "무리수가 아니다"를

정의 15.1로 한 번 더 풀고, (c)는 "또는"이므로 드모르간 2가 들어간다.
:::

**2.** [백지] 조건문 귀류 증명의 서식과, 직접$\cdot$대우$\cdot$귀류의 "가정/도착지" 비교표를 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

서식은 §1.4의 네 줄, 비교표는 §1.5의 세 행이다. 표를 쓸 때 각 행의

"손에 쥐는 가정" 칸이 몇 개인지부터 채우면 나머지가 따라온다.
:::

**3.** 빈칸 훈련($n^2$ 홀수 $\Rightarrow$ $n$ 홀수)을 백지에서 완성하고, 같은 명제의 19주차 대우 증명과 몸통이 어떻게 겹치는지 한 문장으로 쓰시오.

:::{admonition} 힌트
:class: quotebox dropdown

귀류 증명에서 첫 줄과 마지막 줄을 지운 뒤 남는 문장들을 소리 내어 읽어

본다. 그것이 어떤 조건문의 직접 증명인지 물으면 답이 나온다.
:::

**4.** 예제 2.1($a \ge 2$이면 연속 두 정수를 동시에 못 나눔)을 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

네 줄이다. 두 배수의 차를 잡아 $1$을 만들고, 보조 명제 22.A로 부등식의

언어로 옮긴 뒤, $a \ge 2$와 부딪힌다.
:::

**5.** 어떤 정수도 짝수이면서 동시에 홀수일 수 없음을 귀류법으로 증명하시오. (힌트: $2a = 2b + 1$이 되면 $2 \mid 1$ — 17주차부터 "당연히" 써 온 사실의 빚 청산이다)

:::{admonition} 힌트
:class: quotebox dropdown

짝수와 홀수의 정의를 같은 수 $n$에 대해 동시에 적으면 등식 두 개가 생긴다.

두 등식의 우변을 같다고 놓고 정리하면 좌변에서 2를 묶어 낼 수 있고,

그 결과가 보조 명제 22.A와 부딪힌다.
:::

**6.** $x$가 유리수이고 $xy$가 무리수이면 $y$는 무리수임을 귀류법으로 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

가정이 둘($x$ 유리, $xy$ 무리)이고 부정이 하나($y$ 유리) 얹힌다. 유리수

두 개로 만들 수 있는 것을 15주차 닫힘성 목록에서 찾으면 $xy$가 나온다.
:::

### 표준 ●●○

**7.** $a \mid b$이고 $a \nmid c$이면 $a \nmid (b+c)$임을 귀류법으로 증명하시오. (부품: 2주차 문제 17)

:::{admonition} 힌트
:class: quotebox dropdown

§1.1에서 막힌 그 명제다. 손에 쥔 세 문장 가운데 $a \mid (b+c)$와 $a \mid b$

둘을 결합하면 부품이 발동한다. 남은 하나가 충돌 상대다.
:::

**8.** $p$가 소수이고 $p > 2$이면 $p$는 홀수임을 귀류법으로 증명하시오. (힌트: $p$가 짝수라면 2가 $p$의 약수 — 소수의 정의와 충돌시켜라)

:::{admonition} 힌트
:class: quotebox dropdown

정의 15.2는 "양의 약수가 1과 $p$뿐"이다. $p$가 짝수라면 2가 약수인데,

$p > 2$라는 가정이 2를 1도 $p$도 아닌 자리에 놓는다. 가정 $P$의 두 조각이

각각 어디서 소비되는지 확인한다.
:::

**9.** 실수 $x, y$에 대해, $x + y \ge 100$이면 $x \ge 50$ 또는 $y \ge 50$임을 귀류법으로 증명하시오.

**10.** 열린구간 $(0, 1)$에는 최솟값이 존재하지 않음을 증명하시오. (힌트: 최솟값 $m$이 있다면 $\frac{m}{2}$는 어디에 있는가?)

:::{admonition} 힌트
:class: quotebox dropdown

최솟값 $m$이 만족하는 조건을 두 줄로 나눠 적는다 — ① $m \in (0,1)$

② 모든 $z \in (0,1)$에 대해 $m \le z$. 반례가 될 $z$를 만들려면 ①과 ②를

동시에 어기는 수 하나면 되고, $\frac{m}{2}$가 구간 안에 있는지 확인하는

것이 증명의 절반이다.
:::

**11.** 모든 정수 $n$에 대해 $n$과 $n+1$의 공통 약수는 $\pm 1$뿐임을 증명하시오. (힌트: 공통 약수 $d$에 대해 $d \mid \big((n+1) - n\big)$)

**12.** $r$이 유리수이면 $r + \sqrt{2}$는 무리수임을 귀류법으로 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

목표는 $\sqrt{2}$를 유리수들만으로 표현하는 등식 한 줄을 만드는 것이다.

$\sqrt{2} = (r + \sqrt{2}) - r$로 쓰면 우변이 무엇의 차인지 보인다

(21주차 빈칸 사다리 훈련 1과 같은 설계다).
:::

**13.** 실수 $x_1, x_2, \dots, x_n$의 평균이 $\mu$이면, 적어도 하나의 $x_i$는 $\mu$ 이상임을 귀류법으로 증명하시오. (힌트: 전부 $\mu$ 미만이면 총합은?)

:::{admonition} 힌트
:class: quotebox dropdown

"적어도 하나가 ~이다"의 부정은 "전부 ~가 아니다"이다(11주차 총목록 다섯째

행). 부정하면 부등식이 $n$개 생기고, 그것을 전부 변끼리 더하면 평균의

정의에서 나온 등식과 부딪힌다.
:::

**14.** 예제 2.3($x^2 - y^2 = 2$ 불가능)을 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

세 관문이다 — 인수분해, "같은 홀짝"의 근거(합이 $2x$), 두 경우 각각의 충돌.

빈칸 사다리 훈련 3에서 숫자만 바꾼 판을 이미 한 번 썼다.
:::

### 도전 ●●●

:::{admonition} 이번 주에 처음 쓰는 기술 — 기약분수를 귀류의 재료로
:class: quotebox

문제 15는 21주차 예제 2.2($\sqrt{2}$)와 같은 설계를 쓴다. 유리수 해가

있다고 가정할 때 그 해를 **기약분수**로 잡아 두면(정의 21.2), 분자와 분모가

둘 다 짝수인 상황이 곧바로 모순이 된다. 곧 기약성은 나중에 충돌시킬 상대를

미리 설치해 두는 장치다. 설치해 두지 않으면 전개가 끝까지 가도 부딪힐 곳이

없다(21주차 확인 3).
:::

**15.** $a, b, c$가 모두 홀수이면 방정식 $ax^2 + bx + c = 0$은 유리수 해를 갖지 않음을 증명하시오. (안내: 유리수 해 $\frac{p}{q}$(기약)가 있다고 가정 $\to$ $ap^2 + bpq + cq^2 = 0$ $\to$ $p, q$의 홀짝은 (홀,홀), (홀,짝), (짝,홀)의 세 경우뿐(기약이므로 둘 다 짝수는 불가) $\to$ 각 경우 좌변의 홀짝을 추적해 "홀수 = 0(짝수)" 충돌)

:::{admonition} 힌트
:class: quotebox dropdown

각 경우에서 세 항 $ap^2$, $bpq$, $cq^2$의 홀짝을 하나씩 판정한다.

$a, b, c$가 전부 홀수이므로 각 항의 홀짝은 $p$와 $q$의 홀짝만으로 결정된다

(홀수를 곱해도 홀짝이 바뀌지 않는다 — 1주차 문제 8). 세 항의 홀짝이

정해지면 합의 홀짝도 정해지고, 그것을 $0$(짝수)과 비교한다.
:::

**16.** 정수 계수 방정식 $x^3 + x + 1 = 0$은 정수 해를 갖지 않음을 증명하시오. (힌트: $x^3 + x = x(x^2+1)$의 홀짝 — 케이스 또는 1주차식 부품)

:::{admonition} 힌트
:class: quotebox dropdown

등식을 $x^3 + x = -1$로 옮겨 두면 좌변과 우변의 홀짝을 각각 판정하는 문제가

된다. 좌변을 인수분해한 뒤 $x$가 짝수인 경우와 홀수인 경우를 나눠 보면,

두 경우 모두 같은 판정이 나온다.
:::

**17.** (무리수 상등 — "계수 비교"의 정당화) $a, b, c, d$가 유리수이고 $a + b\sqrt{2} = c + d\sqrt{2}$이면 $a = c$이고 $b = d$임을 증명하시오. (힌트: $b \neq d$라고 가정하면 $\sqrt2$를 유리수들로 풀어낼 수 있다)

:::{admonition} 힌트
:class: quotebox dropdown

결론이 "그리고"이므로 두 주장을 각각 확보해야 한다. 먼저 $b = d$를 귀류로

얻은 뒤, 그것을 원래 등식에 대입하면 $a = c$가 따라온다. 귀류 부분에서

$b - d \neq 0$이라는 조건이 양변을 $b - d$로 나누는 줄에서 소비된다.
:::

**18.** (귀류 남용 진단) 다음 답안을 읽고, 논리적으로 틀린 곳은 없지만 왜 "나쁜 증명"인지 지적하고 더 좋은 형태로 고치시오.

:::{container} quotebox
"명제: $n$이 짝수이면 $n^2$은 짝수이다. 증명: 모순을 위해 $n$이 짝수인데 $n^2$이 홀수라고 가정하자. $n = 2k$이므로 $n^2 = 4k^2 = 2(2k^2)$은 짝수이다. 이는 $n^2$이 홀수라는 가정과 모순. 따라서 명제가 성립한다. $\blacksquare$"
:::

:::{admonition} 힌트
:class: quotebox dropdown

§1.8의 자기 점검 질문 하나면 된다 — 가정 "$n^2$이 홀수"가 모순 선언

이전의 어느 줄에서 쓰였는지 손가락으로 짚어 본다. 짚을 곳이 없다면 그

가정은 아무 일도 하지 않은 것이다.
:::

**19.** (서술) 귀류법을 시도했는데 모순이 나오지 않는다. 가능한 원인 두 가지를 쓰고(21주차 문제 18 참고), 각각의 경우 다음 행동을 제안하시오.

:::{admonition} 힌트
:class: quotebox dropdown

갈림길은 "명제가 참인가 거짓인가"다. 참인데 못 찾은 경우와 애초에 거짓인

경우로 나누고, 각각에서 손이 할 일을 적는다. 21주차 문제 18의 $\sqrt{4}$가

둘째 경우의 실물이었다.
:::

**20.** (서술) 기법 선택 가이드 ①~④를 자기 언어로 재구성하고, "귀류 껍데기 안의 직접 증명"(문제 18)을 판별하는 자기 점검 질문 하나를 만드시오.

## 백지 재현 — 복습 프로토콜

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

**1차 시도 (4일차) — 틀 카드 허용.** 조건문 귀류의 3단계 틀(§2 관찰)$\cdot$서식(§1.4)$\cdot$ 근거 목록(§1.10)만 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 본문과 2주차 부품 문장은 보지 않는다.

**2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다.

- [ ] $\neg(P \Rightarrow Q) \equiv P \land \neg Q$를 쓰고, 왜 조건문이 아니라 "그리고"가 되는지 8주차 정의 8.1로 설명했다.
- [ ] 조건문 귀류 증명의 서식(§1.4) 네 줄을 조각 그대로 썼다 — 특히 첫 줄에 $P$를 함께 적었다.
- [ ] 직접$\cdot$대우$\cdot$귀류의 "가정 개수 / 도착지 / 적용 대상" 비교표를 재현했다.
- [ ] "대우는 충돌 상대를 $P$로 정해 둔 귀류법"을 예제 2.2로 설명했다.
- [ ] 예제 2.1을 백지에 재현했다 — 두 배수의 차로 $1$을 짜내는 지점과 보조 명제 22.A가 소비되는 지점을 짚으면서.
- [ ] 예제 2.3(귀류와 경우 나누기)을 재현했다 — "같은 홀짝"의 근거를 빠뜨리지 않고.
- [ ] 기법 선택 가이드 네 조를 썼다 (특히 ④ 남용 점검).
- [ ] 이번 주에 회수한 두 빚("짝수이면서 홀수일 수 없다", "1의 약수는 $\pm 1$뿐")이 어디서 쓰이던 사실이었는지 말할 수 있다.
- [ ] 모순이 끝까지 나오지 않을 때 무엇을 읽어야 하는지 말할 수 있다(문제 19).

**막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다.

| **막힌 지점** | **처방** |
|---|---|
| 첫 줄에 무엇을 가정할지 모르겠다 | §1.2의 표 — $P$는 그대로 옮기고 $Q$만 11주차 총목록으로 부정한다 |
| $\neg Q$는 썼는데 $P$를 빠뜨린다 | §1.3 조각 삭제 실험 — $P$가 없으면 충돌 상대가 무대에 없다 |
| "또는" 결론의 부정에서 막힌다 | 예제 2.2 확인 18 — 드모르간 2로 부등식 두 개를 만든다 |
| 재료 두 개를 어떻게 결합할지 모르겠다 | 예제 2.1의 2단계 — 두 배수의 차를 잡아 작은 수를 짜낸다 |
| 전개는 되는데 모순이 안 보인다 | §1.9 — 서로 다른 언어(나누어떨어짐 vs 부등식)를 한쪽으로 번역했는지 확인한다 |
| 경우가 전체를 덮는지 자신이 없다 | 예제 2.3 확인 21 — 분할의 근거를 문장으로 적었는지 본다 |
| 귀류로 썼는데 군더더기 같다 | §1.8 자기 점검 질문 — $\neg Q$가 쓰인 줄을 짚어 본다 |
| 모순이 끝까지 나오지 않는다 | 문제 19 — 전개가 부족한 것인지 명제가 거짓인 것인지 갈림길을 확인한다 |

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

## 해설

각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

### 빈칸 사다리 — 훈련 1

(1) 짝수  (2) $4k^2 = 2(2k^2)$  (3) 홀수

※ (2)에서 $4k^2$을 그대로 두지 않고 $2(2k^2)$으로 다시 묶는 것이 핵심이다. 짝수의 정의가 요구하는 꼴은 $2 \times (\text{정수})$이므로, 괄호 안이 $2k^2$이고 그것이 정수임(근거 ②)을 확인해야 "짝수이다"라고 선언할 수 있다. (3)에서 충돌 상대가 가정 $P$($n^2$이 홀수)라는 점에 주목한다 — §1.6의 뜻에서 이 증명은 대우 증명으로 다시 쓸 수 있고, 문제 3이 그 겹침을 묻는다.

### 빈칸 사다리 — 훈련 2

(1) $a$와 $b$가 모두 홀수는 아니다  (2) 드모르간 1 (11주차 §1.3 첫째 행) (3) $(2s)b = 2(sb)$  (4) $sb$는 정수 (근거 ②)  (5) 모순

※ 결론이 "그리고"이므로 부정하면 "또는"이 되고, "또는"인 가정은 경우 나누기로 처리한다(17주차). 이 흐름이 19주차 §1.5의 셋째 신호와 같은 내용임을 확인한다 — 그쪽은 대우로, 이쪽은 귀류로 처리했을 뿐이다. 두 경우가 겹칠 수 있다는 점도 문제가 되지 않는다. 분할의 채점 기준은 "빠짐없이 덮는가"이지 "겹치지 않는가"가 아니다.

### 빈칸 사다리 — 훈련 3

(1) 모순을 이끌어내기 위해, $x^2 - y^2 = 10$을 만족하는 정수 $x, y$가 존재한다고 가정하자. 인수분해하면 $(x - y)(x + y) = 10$이다. (2) $(x-y) + (x+y) = 2x$는 짝수이므로 $x - y$와 $x + y$는 같은 홀짝이다(홀짝이 다르면 합이 홀수가 되어 어긋난다 — 1주차 빈칸 사다리 훈련 1). 경우 1(둘 다 짝수): $x - y = 2s$, $x + y = 2t$인 정수 $s, t$가 존재하므로 곱은 $4st$이고 $st$는 정수이므로 $4 \mid 10$이 된다. 경우 2(둘 다 홀수): 홀수와 홀수의 곱은 홀수이므로 (1주차 문제 8) 곱은 홀수인데 $10 = 2 \times 5$는 짝수다. (3) 경우 1에서는 $10 = 4c$인 정수 $c$가 없으므로($c = \frac{5}{2}$) 모순이고, 경우 2에서는 같은 수가 짝수이면서 홀수가 되어 모순이다(문제 5). 두 경우가 전체를 덮으므로 그런 정수 $x, y$는 존재하지 않는다. $\blacksquare$

※ 예제 2.3과 숫자만 다르다. 이 설계가 통하는 조건은 "우변이 짝수이면서 4의 배수가 아닌 것"이다 — $2, 6, 10, 14, \dots$가 전부 같은 논증으로 처리된다. 반대로 $x^2 - y^2 = 8$은 $x = 3, y = 1$에서 실제로 성립하므로 같은 논증이 통하지 않는다. 어느 숫자에서 논증이 멈추는지 확인하는 것이 설계를 이해했다는 증거다.

### 문제 1

**접근.** 세 항목 모두 §1.4 서식의 첫 문장을 채우는 일이다. 규칙은 둘 — $P$는 손대지 않고 그대로 옮겨 적고, $Q$만 11주차 총목록으로 부정한다. (a)는 "무리수가 아니다"를 정의 15.1로 "유리수이다"까지 풀어야 전개 가능한 문장이 되고, (b)는 $\nmid$의 부정이 $\mid$이며, (c)는 "또는"이므로 드모르간 2가 들어가고 $>$의 부정이 $\le$가 된다.

**풀이.** (a) "모순을 이끌어내기 위해, $x$가 무리수인데 $x + 3$이 유리수라고 가정하자." (b) "모순을 이끌어내기 위해, $a \mid b$이고 $a \nmid c$인데 $a \mid (b + c)$라고 가정하자." (c) "모순을 이끌어내기 위해, $x + y > 10$인데 $x \le 5$이고 $y \le 5$라고 가정하자."

**복기.** 세 답안 모두 "$P$인데 $\neg Q$"의 한 문장이고, $P$ 부분에는 손을 대지 않았다. (b)에서 $P$가 두 조각($a \mid b$와 $a \nmid c$)인데 둘 다 그대로 남았다는 점을 확인한다 — 부정은 결론에만 걸린다. 첫 줄을 정확히 쓰는 것만으로 증명의 절반이 끝난다는 것이 이번 주의 채점 기준이다.

### 문제 2

**접근.** §1.4와 §1.5의 재현이다. 서식은 네 줄, 표는 세 행이며 각 행에 "손에 쥐는 가정 / 도착지 / 적용 대상" 세 칸이 있다. 외운 것을 적은 뒤 본문과 한 칸씩 대조한다.

**풀이.** 서식은 다음과 같다.

:::{container} quotebox
**명제.** $P$이면 $Q$이다.

**증명.** 모순을 이끌어내기 위해, $P$인데 $Q$가 아니라고 가정하자.

$\quad\vdots$

이는 ~와 모순이다. 따라서 $P$이면 $Q$이다. $\blacksquare$
:::

비교표는 다음과 같다.

| **기법** | **손에 쥐는 가정** | **도착지** | **적용 대상** |
|---|---|---|---|
| 직접 | $P$ — 한 개 | $Q$ 하나로 고정 | 조건문 (존재 명제는 15주차 §1.7의 증인 제작 서식) |
| 대우 | $\neg Q$ — 한 개 | $\neg P$ 하나로 고정 | 조건문 |
| 귀류 | $P$ 그리고 $\neg Q$ — 두 개 | 아무 모순 (고정되지 않음) | 아무 명제 |

**복기.** 표의 마지막 열이 세 기법의 위계를 정한다. 직접과 대우는 조건문에 걸리는 기법이다 — 조건문이 아닌 명제 가운데 존재 명제는 15주차 §1.7의 증인 제작 서식으로 귀류 없이 직접 증명한다(15주차 문제 19가 그 실물이다). 부정형$\cdot$비존재 결론처럼 만들 목표 꼴이 아예 없는 명제에는 귀류만 걸린다 — 21주차 예제 2.1~2.3이 조건문이 아닌데도 귀류로 처리된 이유가 이 칸이다.

### 문제 3

**접근.** 겹침을 보려면 귀류 증명에서 첫 줄과 마지막 줄을 지우고 남는 문장들을 읽어 본다. 남는 것이 어떤 조건문의 직접 증명인지 물으면 답이 나온다.

**풀이.** 완성된 귀류 증명은 다음과 같다.

모순을 이끌어내기 위해, $n^2$이 홀수인데 $n$이 짝수라고 가정하자. 정의 1.1에 의해 $n = 2k$인 정수 $k$가 존재하고,

$$
n^2 = (2k)^2 = 4k^2 = 2(2k^2)
$$

이며 $2k^2$은 정수이므로(근거 ②) $n^2$은 짝수이다. 이는 $n^2$이 홀수라는 가정과 모순이다(문제 5). 따라서 $n^2$이 홀수이면 $n$은 홀수이다. $\blacksquare$

겹침에 대한 한 문장: 이 귀류 증명에서 첫 줄과 마지막 줄을 지우면 "$n$이 짝수이면 $n^2$은 짝수이다"의 직접 증명이 그대로 남는데, 그것이 바로 원명제의 대우이므로(19주차 문제 1(a)에서 만든 그 대우다) 귀류 증명의 몸통은 대우 증명 전체와 한 줄도 다르지 않다.

**복기.** §1.6의 관찰이 실물로 확인된 자리다. 이 증명의 충돌 상대가 가정 $P$였다는 사실이 곧 "대우로 다시 쓸 수 있다"는 신호다. 대응이 하나 더 있다 — 문제 18에서 고쳐 쓴 직접 증명이 정확히 이 대우 증명이다. 같은 몸통이 어떤 명제의 대우 증명이면서 다른 명제의 직접 증명일 수 있다.

### 문제 4

**접근.** 네 줄짜리 증명이고 관문은 두 곳이다 — 두 배수의 차를 잡아 $1$을 짜내는 것(2주차 문제 17), 그리고 나누어떨어짐을 부등식의 언어로 옮기는 것 (보조 명제 22.A). 첫 줄에 $a \ge 2$를 함께 적었는지도 확인한다.

**풀이.** 모순을 이끌어내기 위해, $a \ge 2$인데 결론이 거짓 — 곧 드모르간 2에 의해 $a \mid b$이고 $a \mid (b+1)$이라고 가정하자. $a \mid (b+1)$이고 $a \mid b$이므로 2주차 문제 17에 의해

$$
a \mid \big((b+1) - b\big) = 1
$$

이다. 보조 명제 22.A에 의해 $a = 1$ 또는 $a = -1$이므로 $a \le 1$이다. 이는 $a \ge 2$라는 가정과 모순이다. 따라서 $a \nmid b$ 또는 $a \nmid (b+1)$이다. $\blacksquare$

(검산: $a = 5$, $b = 24$이면 $5 \mid 25$는 참이지만 $5 \mid 24$는 거짓이므로 결론의 "또는"이 성립한다. 두 배수 사이의 간격이 $a$ 이상이므로 연속한 두 정수가 동시에 걸릴 수 없다는 것이 수치적 그림이다.)

**복기.** "두 배수의 차를 잡아 작은 수를 짜낸다"는 이 주차에서 가장 자주 재사용되는 수단이다. 문제 11이 같은 두 줄을 귀류 없이 쓰고, 21주차 예제 2.3의 $p \mid 1$도 같은 자리에서 나왔다.

### 문제 5

**접근.** 같은 정수 $n$이 짝수이면서 홀수라고 가정하면 등식이 두 개 생긴다. 두 우변을 같다고 놓고 정리하면 $2 \times (\text{정수}) = 1$ 꼴이 나오고, 그것이 보조 명제 22.A와 부딪힌다. 이 문제가 5주차부터 인정하고 써 온 사실을 정리로 승격시키는 자리다.

**풀이.** 모순을 이끌어내기 위해, 어떤 정수 $n$이 짝수이면서 동시에 홀수라고 가정하자. 정의 1.1과 정의 1.2에 의해 $n = 2a$인 정수 $a$와 $n = 2b + 1$인 정수 $b$가 존재한다. 두 표현이 같은 수 $n$을 나타내므로

$$
2a = 2b + 1
$$

이고, 양변에서 $2b$를 빼면 $2a - 2b = 1$, 곧

$$
2(a - b) = 1
$$

이다. $a - b$는 정수이므로(근거 ②) 이 등식은 $2 \mid 1$을 뜻한다(정의 2.1). 그런데 보조 명제 22.A에 의해 1의 약수는 $1$과 $-1$뿐이고 $2$는 그중 어느 것도 아니다. 모순이다. 따라서 짝수이면서 동시에 홀수인 정수는 존재하지 않는다. $\blacksquare$

**복기.** 5주차 빈칸 사다리 훈련 1에서 $E \cap O = \emptyset$로 적었고, 17주차의 짝/홀 분할에서 "둘 중 정확히 하나"의 '정확히'가 이 사실이었으며, 21주차 빈칸 사다리 훈련 3이 이것을 명시적으로 빌렸다. 오래 인정하고 쓴 사실도 결국 정의 두 개와 뺄셈 한 번으로 갚아진다 — 인정하고 쓴다는 것은 포기가 아니라 회수 일정에 올린다는 뜻이다.

### 문제 6

**접근.** 가정이 둘($x$가 유리수, $xy$가 무리수)이고 거기에 부정 하나($y$가 유리수)가 얹힌다. 손에 유리수가 둘($x$와 $y$) 있으면 15주차 닫힘성 목록에서 곱을 꺼낼 수 있고, 그 결과가 남은 가정과 부딪힌다.

**풀이.** 모순을 이끌어내기 위해, $x$가 유리수이고 $xy$가 무리수인데 $y$가 유리수라고 가정하자. $x$와 $y$가 모두 유리수이므로, 유리수의 곱은 유리수라는 사실(15주차 빈칸 사다리 훈련 1)에 의해 $xy$는 유리수이다. 이는 $xy$가 무리수라는 가정과 모순이다(정의 15.1에 의해 한 실수가 유리수이면서 무리수일 수는 없다). 따라서 $y$는 무리수이다. $\blacksquare$

**복기.** 21주차 문제 8과 비교해 둔다. 그쪽 명제("$x$가 0이 아닌 유리수이고 $y$가 무리수이면 $xy$는 무리수")는 증명에서 $\frac{xy}{x}$를 만들어야 하므로 $x \neq 0$이 필요했다. 이번 방향은 곱만 쓰므로 그 조건이 필요 없다. 같은 재료라도 어느 연산을 쓰느냐에 따라 요구되는 조건이 달라진다 — 조건의 소비처를 확인하는 습관이 여기서 값을 한다.

### 문제 7

**접근.** §1.1에서 세 기법이 차례로 막힌 그 명제다. 귀류로 첫 줄을 쓰면 손에 세 문장이 들어온다 — $a \mid b$, $a \nmid c$, 그리고 $a \mid (b+c)$. 이 중 앞뒤 두 개를 결합하면 2주차 문제 17이 발동해 $a \mid c$가 나오고, 남은 $a \nmid c$가 충돌 상대다.

**풀이.** 모순을 이끌어내기 위해, $a \mid b$이고 $a \nmid c$인데 $a \mid (b+c)$라고 가정하자. $a \mid (b+c)$이고 $a \mid b$이므로 2주차 문제 17에 의해 $a \mid c$이다. 이는 $a \nmid c$라는 가정과 모순이다. 따라서 $a \nmid (b+c)$이다. $\blacksquare$

(검산: $a = 3$, $b = 6$, $c = 4$이면 $3 \mid 6$이고 $3 \nmid 4$이므로 가정이 성립하고, $b + c = 10$에 대해 $3 \nmid 10$으로 결론도 성립한다.)

**복기.** 세 줄짜리 증명이지만 §1.1에서 직접과 대우가 모두 막힌 명제다. 증명의 길이와 기법 선택의 난이도는 별개다. 이 명제는 2주차 문제 17에서 가정 하나($a \mid (b+c)$)와 결론($a \mid c$)을 서로 부정해 맞바꾼 동치 형태다 — "$A$이고 $B$이면 $C$"와 "$B$이고 $\neg C$이면 $\neg A$"는 언제나 동치이므로, 두 명제는 같은 내용의 두 포장이다. 다만 이것을 대우라고 부르지는 않는다. 문제 17의 진짜 대우는 "$a \nmid c$이면 $a \nmid (b+c)$ 또는 $a \nmid b$이다"로 결론이 "또는"인 별개의 명제다. 그리고 이번 명제를 직접 대우로 쓰려 하면 $\neg P$가 "또는"이 되어 막힌다는 점이 §1.1 시도 3의 관찰이었다.

### 문제 8

**접근.** 소수의 정의 15.2는 "양의 약수가 1과 $p$뿐"이다. $p$가 짝수라고 가정하면 2가 $p$의 양의 약수가 되고, 가정 $p > 2$가 2를 "1도 아니고 $p$도 아닌 자리"에 놓는다. 가정 $P$의 두 조각($p$가 소수, $p > 2$)이 각각 어디서 소비되는지 확인하며 쓴다.

**풀이.** 모순을 이끌어내기 위해, $p$가 소수이고 $p > 2$인데 $p$가 짝수라고 가정하자. $p$가 짝수이므로 정의 1.1에 의해 $p = 2k$인 정수 $k$가 존재하고, 정의 2.1에 의해 $2 \mid p$이다. 곧 2는 $p$의 양의 약수이다. 그런데 $p > 2$이므로 $2 \neq p$이고, 또 $2 \neq 1$이다. 따라서 $p$는 1도 $p$ 자신도 아닌 양의 약수 2를 가진다. 이는 $p$가 소수라는 가정, 곧 정의 15.2("양의 약수가 1과 $p$뿐")와 모순이다. 따라서 $p$는 홀수이다. $\blacksquare$

**복기.** 가정의 두 조각이 서로 다른 곳에서 소비됐다 — "$p$가 소수"는 마지막 충돌 선언에서, "$p > 2$"는 2가 $p$ 자신이 아님을 확인하는 줄에서. $p > 2$를 빠뜨리면 $p = 2$에서 실제로 반례가 된다(2는 짝수인 소수다). 따름정리로 "2는 유일한 짝수 소수"가 나오고, 이 진술은 26주차의 유일성 증명에서 다시 포장된다.

### 문제 9

**접근.** 예제 2.2의 숫자를 바꾼 판이다. 결론이 "또는"이므로 부정하면 드모르간 2로 부등식 두 개가 손에 들어오고, 변끼리 더하면 가정과 정면으로 부딪힌다.

**풀이.** 모순을 이끌어내기 위해, $x + y \ge 100$인데 $x < 50$이고 $y < 50$이라고 가정하자. 두 부등식을 변끼리 더하면(16주차 문제 2(c))

$$
x + y < 50 + 50 = 100
$$

이다. 이는 가정 $x + y \ge 100$과 모순이다. 따라서 $x \ge 50$ 또는 $y \ge 50$이다. $\blacksquare$

**복기.** 예제 2.2와 이 문제의 유일한 차이는 $2$가 $100$으로, $1$이 $50$으로 바뀐 것뿐이다. 일반형으로 적으면 "$x + y \ge 2s$이면 $x \ge s$ 또는 $y \ge s$"이고, 증명은 글자 그대로 같다 — 이런 유형에서는 숫자를 문자로 바꿔 두면 문제 하나가 무한히 많은 문제를 덮는다. 문제 13이 같은 발상을 $n$개의 수로 확장한 판이다.

### 문제 10

**접근.** "최솟값이 존재하지 않는다"는 비존재 결론이므로 부정하면 최솟값 $m$이 손에 들어온다(21주차 §1.6 셋째 신호). 최솟값이라는 말에는 조건이 두 개 들어 있다 — ① $m$ 자신이 구간 안에 있다 ② 구간의 모든 원소가 $m$ 이상이다. $\frac{m}{2}$를 만들어 ②를 어기되, ①의 검증(그 수가 정말 구간 안에 있는가)을 빠뜨리지 않는 것이 이 문제의 관문이다.

**풀이.** 모순을 이끌어내기 위해, 열린구간 $(0,1)$에 최솟값 $m$이 존재한다고 가정하자. 최솟값의 뜻에 의해 $m \in (0,1)$이고, 모든 $z \in (0,1)$에 대해 $m \le z$이다.

$m \in (0,1)$이므로 $0 < m < 1$이다. $\frac{m}{2}$을 생각하자.

첫째, $\frac{m}{2} \in (0,1)$이다. $m > 0$이고 $2 > 0$이므로 $\frac{m}{2} > 0$이고, $m < 1$이므로 $\frac{m}{2} < \frac{1}{2} < 1$이다.

둘째, $\frac{m}{2} < m$이다. $m > 0$이므로 $\frac{m}{2} < m$은 양변에 2를 곱한 $m < 2m$, 곧 $0 < m$과 같은 내용이고 이는 참이다.

따라서 $\frac{m}{2}$은 $(0,1)$의 원소이면서 $m$보다 작다. 이는 모든 $z \in (0,1)$에 대해 $m \le z$라는 최소성과 모순이다. 따라서 $(0,1)$에는 최솟값이 존재하지 않는다. $\blacksquare$

**복기.** 최소성을 어기는 원소를 만들 때는 두 검증이 모두 필요하다 — 만든 수가 무대 안에 있는가, 그리고 정말 더 작은가. 하나만 확인하면 반례가 되지 않는다. 이 구간이 최솟값을 갖지 않는다는 사실은 33주차 최소원리의 대조군으로 다시 등장한다. 자연수의 부분집합은 반드시 최소원소를 갖는데 실수의 구간은 그렇지 않다는 대비가, 최소원리가 자연수의 특권임을 보여 주는 자리다.

### 문제 11

**접근.** "공통 약수는 $\pm 1$뿐"은 "모든 공통 약수 $d$에 대해 $d = \pm 1$"이므로, 임의의 공통 약수 $d$를 잡아 $d = \pm 1$을 직접 보이면 된다. 예제 2.1과 같은 부품을 쓰지만 귀류가 필요 없다 — 결론이 긍정형이고 목표 꼴이 있기 때문이다 (가이드 ①).

**풀이.** $d$를 $n$과 $n+1$의 공통 약수라 하자. 곧 $d \mid n$이고 $d \mid (n+1)$이다. $d \mid (n+1)$이고 $d \mid n$이므로 2주차 문제 17에 의해

$$
d \mid \big((n+1) - n\big) = 1
$$

이다. 보조 명제 22.A에 의해 $d = 1$ 또는 $d = -1$이다. $d$는 임의의 공통 약수였으므로, $n$과 $n+1$의 공통 약수는 $\pm 1$뿐이다. $\blacksquare$

(검산: $n = 8$이면 8의 약수는 $\pm 1, \pm 2, \pm 4, \pm 8$이고 9의 약수는 $\pm 1, \pm 3, \pm 9$이므로 공통인 것은 $\pm 1$뿐이다.)

**복기.** 예제 2.1은 같은 사실을 귀류로 적었고 이 문제는 직접으로 적었다. 두 서술의 차이는 첫 줄뿐이며, 몸통("두 배수의 차로 $1$을 짜낸다")은 같다 — 가이드 ①의 실물 사례다. 이 명제는 "연속한 두 정수는 서로소"라는 이름으로 34주차 문제 12(연속한 피보나치 수)에서 같은 부품으로 재사용된다.

### 문제 12

**접근.** 결론이 "무리수"라는 부정형 개념이므로 귀류다(21주차 §1.6 첫째 신호). 목표는 $\sqrt{2}$를 유리수들만으로 표현하는 등식 한 줄을 만드는 것이다. $\sqrt{2} = (r + \sqrt{2}) - r$로 쓰면 우변이 유리수 두 개의 차가 된다.

**풀이.** 모순을 이끌어내기 위해, $r$이 유리수인데 $r + \sqrt{2}$가 유리수라고 가정하자. 그러면

$$
\sqrt{2} = (r + \sqrt{2}) - r
$$

이고, 우변은 유리수 $r + \sqrt{2}$에서 유리수 $r$을 뺀 것이므로 유리수이다 (15주차 문제 9: 두 유리수의 차는 유리수). 곧 $\sqrt{2}$가 유리수가 된다. 이는 $\sqrt{2}$가 무리수라는 사실(21주차 예제 2.2)과 모순이다. 따라서 $r + \sqrt{2}$는 무리수이다. $\blacksquare$

**복기.** 이 설계의 이름을 붙이면 "무리수를 유리수들로 고립시키기"다. 21주차 빈칸 사다리 훈련 1(유리수 + 무리수 = 무리수)이 같은 설계였고, 문제 17이 같은 설계를 한 단계 복잡한 식에 쓴다. 고립시킬 때 필요한 것은 유리수 닫힘성 다섯 개(합$\cdot$차$\cdot$곱$\cdot$역수$\cdot$몫)이며, 어느 것을 쓰는지에 따라 필요한 조건이 달라진다는 점을 문제 6에서 확인했다.

### 문제 13

**접근.** 결론 "적어도 하나의 $x_i$가 $\mu$ 이상"은 존재 주장이므로, 부정하면 "모든 $i$에 대해 $x_i < \mu$"가 된다(11주차 총목록 다섯째 행). 부정하면 부등식이 $n$개 생기고, 그것을 전부 변끼리 더하면 평균의 정의에서 나온 등식과 부딪힌다. 평균의 정의를 등식으로 먼저 적어 두는 것이 출발점이다.

**풀이.** 평균이 $\mu$이므로, 평균의 정의 $\mu = \dfrac{x_1 + x_2 + \cdots + x_n}{n}$의 양변에 $n$을 곱하면

$$
x_1 + x_2 + \cdots + x_n = n\mu
$$

이다. 모순을 이끌어내기 위해, 모든 $i$에 대해 $x_i < \mu$라고 가정하자. 이 부등식 $n$개를 변끼리 더하면(16주차 문제 2(c)를 $n-1$번 적용)

$$
x_1 + x_2 + \cdots + x_n < \underbrace{\mu + \mu + \cdots + \mu}_{n\text{개}} = n\mu
$$

이다. 그런데 위에서 좌변은 $n\mu$와 같으므로 $n\mu < n\mu$가 되어, 같은 수가 자기 자신보다 작다는 모순에 이른다. 따라서 적어도 하나의 $x_i$는 $\mu$ 이상이다. $\blacksquare$

**복기.** 존재 결론("적어도 하나")의 귀류는 전칭 가정("전부 아니다")을 준다 — 11주차의 부정 규칙이 그대로 증명 전략이 되는 자리다. 이 증명은 어느 $x_i$가 $\mu$ 이상인지 특정하지 않는다. 존재를 증명하면서 증인을 지목하지 않는 이런 증명을 26주차에서 비구성적 존재 증명이라는 이름으로 다시 다룬다. 정수 판으로 옮기면 26주차 문제 19의 비둘기집 원리가 된다.

### 문제 14

**접근.** 세 관문이 있다 — 인수분해로 곱의 꼴을 만드는 것, 두 인수가 "같은 홀짝"임을 근거와 함께 보이는 것, 그리고 두 경우를 각각 봉쇄하는 것. 둘째 관문을 빠뜨리면 경우가 전체를 덮지 않는다.

**풀이.** 모순을 이끌어내기 위해, $x^2 - y^2 = 2$를 만족하는 정수 $x, y$가 존재한다고 가정하자. 인수분해하면 $(x-y)(x+y) = 2$이다.

여기서 $(x-y) + (x+y) = 2x$는 짝수이다. 만약 $x - y$와 $x + y$의 홀짝이 다르다면 그 합은 홀수이므로(1주차 빈칸 사다리 훈련 1: 홀수와 짝수의 합은 홀수) $2x$가 짝수라는 것과 어긋난다. 따라서 $x - y$와 $x + y$는 같은 홀짝이고, 정수는 짝수이거나 홀수이므로(17주차 짝/홀 분할) 다음 두 경우가 전체를 덮는다.

**경우 1: 둘 다 짝수.** $x - y = 2s$, $x + y = 2t$인 정수 $s, t$가 존재하므로 $(x-y)(x+y) = 4st$이고 $st$는 정수이다(근거 ②). 곧 $2 = 4st$이므로 $4 \mid 2$인데, $2 = 4c$인 정수 $c$는 존재하지 않는다($c = \frac{1}{2}$은 정수가 아니다). 모순이다.

**경우 2: 둘 다 홀수.** 홀수와 홀수의 곱은 홀수이므로(1주차 문제 8) $(x-y)(x+y)$는 홀수이다. 그런데 그 값은 $2 = 2 \times 1$로 짝수이다. 곧 같은 수가 짝수이면서 홀수이므로 문제 5에 의해 모순이다.

두 경우가 전체를 빠짐없이 덮고 어느 경우든 모순이므로, $x^2 - y^2 = 2$를 만족하는 정수 $x, y$는 존재하지 않는다. $\blacksquare$

**복기.** 귀류가 바깥 틀이고 경우 나누기가 안쪽 몸통인 이중 구조다. 기법은 서로를 대체하지 않고 층으로 쌓인다 — 문제 15가 같은 구조를 세 경우로 확장한 판이고, 빈칸 사다리 훈련 3에서 숫자만 바꾼 판을 한 번 썼다.

### 문제 15

**접근.** 유리수 해가 있다고 가정하되 **기약분수**로 잡는다(정의 21.2). 기약성이 "$p$와 $q$가 둘 다 짝수인 경우"를 미리 제거해 주므로 검사할 경우가 셋으로 줄어든다. 각 경우에서 세 항 $ap^2$, $bpq$, $cq^2$의 홀짝을 하나씩 판정하고, 그 합의 홀짝을 $0$(짝수)과 비교한다. $a, b, c$가 전부 홀수라는 가정이 여기서 소비된다 — 홀수를 곱해도 홀짝이 바뀌지 않으므로(1주차 문제 8) 각 항의 홀짝이 $p$와 $q$의 홀짝만으로 결정된다.

**풀이.** 모순을 이끌어내기 위해, $a, b, c$가 모두 홀수인데 $ax^2 + bx + c = 0$이 유리수 해를 갖는다고 가정하자. 그 해를 기약분수 $x = \dfrac{p}{q}$ ($p, q$는 정수, $q \neq 0$)로 잡는다. 대입하면

$$
a\frac{p^2}{q^2} + b\frac{p}{q} + c = 0
$$

이고, 양변에 $q^2$을 곱하면

$$
ap^2 + bpq + cq^2 = 0
$$

이다. 기약분수이므로 $p$와 $q$의 공통 약수는 $\pm 1$뿐이고, 따라서 둘 다 짝수일 수는 없다(둘 다 짝수라면 2가 공통 약수가 된다). 정수는 짝수이거나 홀수이므로 남는 경우는 다음 셋뿐이고, 이 셋이 전체를 덮는다.

**경우 1: $p$ 홀수, $q$ 홀수.** $ap^2$은 홀수 세 개의 곱이므로 홀수이고 (1주차 문제 8을 두 번 적용), $bpq$도 홀수 세 개의 곱이므로 홀수이며, $cq^2$도 같은 이유로 홀수이다. 홀수 셋의 합은 홀수이다(홀+홀=짝, 짝+홀=홀 — 1주차 예제 2.3과 빈칸 사다리 훈련 1). 그런데 우변 $0 = 2 \times 0$은 짝수이므로, 같은 수가 홀수이면서 짝수가 되어 문제 5에 의해 모순이다.

**경우 2: $p$ 홀수, $q$ 짝수.** $ap^2$은 홀수 세 개의 곱이므로 홀수이다. $bpq$는 인수에 짝수 $q$가 있으므로 짝수이고, $cq^2$도 마찬가지로 짝수이다. 합은 홀수 + 짝수 + 짝수이므로 홀수이다. 우변 $0$은 짝수이므로 모순이다.

**경우 3: $p$ 짝수, $q$ 홀수.** $ap^2$은 인수에 짝수 $p$가 있으므로 짝수이고, $bpq$도 마찬가지로 짝수이다. $cq^2$은 홀수 세 개의 곱이므로 홀수이다. 합은 짝수 + 짝수 + 홀수이므로 홀수이다. 우변 $0$은 짝수이므로 모순이다.

세 경우가 전체를 덮고 어느 경우든 모순이므로, 유리수 해는 존재하지 않는다. $\blacksquare$

**복기.** 귀류 + 기약분수 + 경우 나누기가 한 증명에 겹쳐진 이번 주의 종합 문제다. 기약성은 여기서 두 가지 일을 한다 — 경우를 넷에서 셋으로 줄이고, $p$와 $q$의 홀짝 조합을 통제한다. 결과를 도구로 쓰면 $x^2 + x + 1 = 0$이나 $3x^2 + 5x + 7 = 0$이 유리근을 갖지 않음을 계산 없이 즉시 알 수 있다 — 계수 셋이 모두 홀수인지만 보면 된다.

### 문제 16

**접근.** 등식을 $x^3 + x = -1$로 옮기면 좌변과 우변의 홀짝을 각각 판정하는 문제가 된다. 좌변을 $x(x^2+1)$로 인수분해한 뒤 $x$가 짝수인 경우와 홀수인 경우를 나누면, 두 경우 모두 좌변이 짝수라는 같은 판정이 나온다. 우변 $-1$은 홀수이므로 충돌한다.

**풀이.** 모순을 이끌어내기 위해, $x^3 + x + 1 = 0$을 만족하는 정수 $x$가 존재한다고 가정하자. 이항하면

$$
x^3 + x = -1
$$

이고, 좌변을 인수분해하면 $x^3 + x = x(x^2 + 1)$이다. 정수는 짝수이거나 홀수이므로(17주차 짝/홀 분할) 두 경우로 나눈다.

**경우 1: $x$가 짝수.** $x = 2k$인 정수 $k$가 존재하므로 $x(x^2+1) = 2\big(k(x^2+1)\big)$이고 $k(x^2+1)$은 정수이므로(근거 ②) 좌변은 짝수이다.

**경우 2: $x$가 홀수.** $x$가 홀수이면 $x^2$도 홀수이므로(1주차 문제 11) $x^2 = 2j + 1$인 정수 $j$가 존재하고, $x^2 + 1 = 2j + 2 = 2(j+1)$은 짝수이다. 따라서 $x(x^2+1) = x \cdot 2(j+1) = 2\big(x(j+1)\big)$이고 $x(j+1)$은 정수이므로 좌변은 짝수이다.

두 경우가 전체를 덮고 어느 경우든 좌변 $x^3 + x$는 짝수이다. 그런데 우변 $-1 = 2 \times (-1) + 1$은 홀수이다. 곧 같은 수가 짝수이면서 홀수이므로 문제 5에 의해 모순이다. 따라서 정수 해는 존재하지 않는다. $\blacksquare$

(검산: $x = -2, -1, 0, 1$을 넣으면 $x^3 + x + 1$의 값이 각각 $-9, -1, 1, 3$으로 $0$이 아니다. 실수 해는 $-1$과 $0$ 사이에 하나 있지만 정수가 아니다.)

**복기.** "좌변과 우변의 홀짝을 각각 판정해 어긋남을 보인다"는 21주차 빈칸 사다리 훈련 3과 같은 요령이다. 이런 문제에서 경우 나누기는 좌변의 홀짝이 $x$에 따라 달라질 수 있다는 우려를 없애는 장치이고, 두 경우가 같은 결론에 도달하면 그 결론은 $x$와 무관하게 성립한다.

### 문제 17

**접근.** 결론이 "$a = c$이고 $b = d$"라는 "그리고"이므로 두 주장을 각각 확보해야 한다. 순서를 잡으면 쉬워진다 — 먼저 $b = d$를 귀류로 얻고, 그것을 원래 등식에 대입하면 $a = c$가 따라온다. 귀류 부분의 설계는 문제 12와 같다. $\sqrt{2}$를 유리수들로 고립시키는 것이고, $b - d \neq 0$이 양변을 $b - d$로 나누는 줄에서 소비된다.

**풀이.** $a, b, c, d$를 유리수라 하고 $a + b\sqrt{2} = c + d\sqrt{2}$라 하자.

**1단계: $b = d$.** 모순을 이끌어내기 위해 $b \neq d$라고 가정하자. 주어진 등식을 정리하면

$$
(b - d)\sqrt{2} = c - a
$$

이고, $b \neq d$이므로 $b - d \neq 0$이어서 양변을 $b - d$로 나눌 수 있다.

$$
\sqrt{2} = \frac{c - a}{b - d}
$$

우변에서 $c - a$는 두 유리수의 차이므로 유리수이고(15주차 문제 9), $b - d$도 같은 이유로 유리수이며 $0$이 아니다. 0이 아닌 유리수로 유리수를 나눈 몫은 유리수이므로(15주차 문제 15) 우변은 유리수이다. 곧 $\sqrt{2}$가 유리수가 된다. 이는 $\sqrt{2}$가 무리수라는 사실(21주차 예제 2.2)과 모순이다. 따라서 $b = d$이다.

**2단계: $a = c$.** $b = d$를 원래 등식에 대입하면 $a + b\sqrt{2} = c + b\sqrt{2}$이고, 양변에서 $b\sqrt{2}$를 빼면 $a = c$이다.

두 주장이 모두 확보되었으므로 $a = c$이고 $b = d$이다. $\blacksquare$

**복기.** 고등학교에서 "무리수 부분끼리, 유리수 부분끼리 비교한다"고 외운 규칙의 증명이다. 규칙이 아니라 정리였고, 근거는 $\sqrt{2}$의 무리수성이었다. "그리고" 결론을 처리하는 표준 순서도 확인된다 — 두 주장을 동시에 만들려 하지 말고, 하나를 먼저 확보한 뒤 그것을 도구로 나머지를 얻는다.

### 문제 18

**접근.** §1.8의 자기 점검 질문 하나면 된다 — 가정 "$n^2$이 홀수"가 모순 선언 이전의 어느 줄에서 쓰였는지 손가락으로 짚어 본다. 짚을 곳이 없으면 그 가정은 아무 일도 하지 않았고, 귀류의 껍데기가 군더더기라는 진단이 선다.

**풀이.** 논리적 오류는 없다. 각 줄의 근거도 정확하고 결론도 옳다. 문제는 귀류 가정 "$n^2$이 홀수"가 **본문의 어느 줄에서도 사용되지 않았다**는 점이다. 증명의 몸통 "$n = 2k$이므로 $n^2 = 4k^2 = 2(2k^2)$은 짝수이다"는 가정 "$n$이 짝수"만으로 완결되며, 그 자체가 원명제의 완전한 직접 증명이다. 곧 첫 줄과 마지막 두 줄이 전부 군더더기다.

고쳐 쓴 형태는 다음과 같다.

**명제.** $n$이 짝수이면 $n^2$은 짝수이다. **증명.** $n$이 짝수라 가정하자. 정의 1.1에 의해 $n = 2k$인 정수 $k$가 존재한다. 그러면 $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$이고 $2k^2$은 정수이므로 (근거 ②) $n^2$은 짝수이다. $\blacksquare$

가이드 ④의 문장 그대로다 — 부정 가정을 쓰지 않았다면 그것은 귀류법이 아니었다.

**복기.** 21주차 예제 2.2($\sqrt{2}$)와 비교하면 차이가 분명하다. 그쪽에서는 부정 가정("유리수이다")이 등식 $\sqrt{2} = \frac{a}{b}$를 낳았고 그 등식 없이는 한 줄도 나아갈 수 없었다. 여기서는 부정 가정이 아무것도 낳지 않는다. 판별의 기준은 감이 아니라 "그 가정에서 나온 문장이 하나라도 있는가"다. 이 문제의 수정본이 곧 문제 3에서 다룬 대우 증명과 같은 문장들이라는 점도 확인해 둔다.

### 문제 19

**접근.** 21주차 문제 18($\sqrt{4}$)에서 실물로 본 상황의 일반화다. 갈림길은 "명제가 참인가 거짓인가" 하나이고, 두 갈래 각각에서 손이 할 일이 다르다.

**풀이.** (예시 답안)

**원인 1 — 명제는 참인데 아직 충돌 지점을 찾지 못했다.** 귀류법의 도착점은 "아무 모순"이므로 방향이 지정되어 있지 않고(§1.5), 따라서 전개가 모순에서 먼 쪽으로 갈 수 있다. 행동: ① 가정에서 아직 풀지 않은 정의가 있는지 확인해 전부 등식으로 바꾼다 ② 충돌 상대를 미리 설치했는지 점검한다(기약성 같은 조건 — 21주차 확인 3) ③ 경우 나누기로 분기해 각 갈래에서 다시 시도한다 ④ 직접이나 대우로 기법을 바꿔 본다.

**원인 2 — 명제가 애초에 거짓이다.** 명제가 거짓이면 $\neg P$가 참이고, 참인 가정에서는 모순이 유도될 수 없다. 아무리 오래 전개해도 모순이 나오지 않는 것이 당연하다. 행동: 작은 값들을 차례로 대입해 반례를 수색한다. 반례가 하나라도 나오면 그 명제는 거짓으로 확정된다.

두 원인을 구분하는 실전 동선은 왕복이다 — 증명이 막히면 반례를 찾고, 반례가 찾아지지 않으면 그 실패에서 얻은 정보(어떤 조건 때문에 반례가 안 되는가)를 가지고 다시 증명을 시도한다. 이 왕복을 정식 과목으로 다루는 것이 29주차의 반증이다.

**복기.** 21주차 문제 18의 $\sqrt{4}$는 원인 2의 실물이었다 — $\sqrt{4} = 2$는 유리수이므로 "무리수이다"라는 명제가 거짓이고, 그래서 $\sqrt{2}$ 증명의 흉내가 $b^2 = c^2$에서 멈춘 것이다. 모순이 나오지 않는다는 사실 자체가 정보라는 것이 이 문제의 요점이다.

### 문제 20

**접근.** 가이드 네 조를 외워 옮기는 것이 아니라, 이번 주에 푼 문제들을 조별로 분류해 각 칸에 문제 번호를 붙여 본다. 붙일 문제가 떠오르지 않는 조가 있으면 그 조를 아직 쓰지 못한 것이다.

**풀이.** (예시 답안)

① 먼저 직접을 시도한다 — 가정을 정의로 풀어 결론의 목표 꼴을 만든다. 가정도 결론도 긍정형이고 정의가 즉시 풀리면 직접이 최단이다. (이번 주에서는 문제 11이 그랬다 — 결론이 "$d = \pm 1$"이라는 긍정형이라 귀류가 필요 없었다.)

② 가정이 $n^2$ 같은 합성식이거나 부정형이거나, 결론이 "또는"$\cdot$"그리고"이면 대우로 갈아탄다 — 가정과 결론이 자리를 바꾸면 다루기 쉬운 쪽이 가정이 된다. (문제 3에서 다룬 명제가 대우로도 같은 몸통이 되는 사례였고, 결론이 "또는"인 문제 1(c)$\cdot$문제 9는 대우로 적어도 몸통이 같다.)

③ 결론이 무리수$\cdot$비존재$\cdot$무한 등 부정 자체이거나, 대우로 뒤집어도 결론 쪽에 "또는"이 남아 지목이 안 되면 귀류로 간다 — 부정이 재료가 되기 때문이다. (문제 7, 10, 12, 14, 15가 전부 이 조에 해당한다.)

④ 다 쓴 뒤 점검한다 — 귀류 가정을 실제로 썼는가. 안 썼다면 껍데기를 벗긴다. (문제 18이 이 조의 실물이다.)

자기 점검 질문: **"귀류 가정 $\neg Q$에서 유도된 문장이 모순 선언 이전에 하나라도 있는가."** 하나도 없다면 그 증명은 귀류법이 아니라, 직접 증명 앞뒤에 문장 두 개를 덧붙인 것이다.

**복기.** 가이드는 규칙이 아니라 순서다 — ①부터 시도해 막히면 다음으로 내려간다. 막히는 자리가 곧 신호이므로, 기법 선택은 취향이 아니라 문제 문장이 정한다. 이 순서를 세 기법 모두에 대해 한 명제로 실습하는 것이 다음 주의 내용이다.

---

**다음 주 예고:** 23주차에서는 같은 명제를 직접$\cdot$대우$\cdot$귀류 세 방식으로 각각 증명해 보고, 어느 문장에 어느 기법이 자연스러운지 비교한다. 이번 주에 세운 기법 선택 가이드 ①~④가 판단의 기준이 되고, 특히 ④(남용 점검)가 세 답안을 나란히 놓고 길이를 비교하는 자리에서 실물로 확인된다 — 기법 선택이 감이 아니라 신호 읽기가 되도록 만드는 훈련 주간이다.