# C10주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 판정부터 함께 만들기 완성된 답안을 먼저 보이지 않는다. 참$\cdot$거짓이 표시되지 않은 상태에서 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 참인 명제: 정찰에서 증명까지 **명제 (P-or-D).** 모든 정수 $n$에 대해, $n^2 + n$은 짝수이다. **설계 — 쓰기 전에 정하는 두 가지.** 여느 주와 달리 도착점이 아직 비어 있다. 참$\cdot$거짓을 정하는 것이 설계의 첫 일이다. | | **말** | **수식 번역** | |---|---|---| | 가정 (주어진 것) | $n$은 정수이다 | 무대 조건뿐이고 풀어 쓸 정의가 없다 | | 도착점 (만들 것) | 아직 정해지지 않았다 | $\underline{\quad(?)\quad}$ | :::{container} quotebox **확인 10.** 도착점 칸을 채워 보자. 이 명제의 도착점은 두 갈래이고, 어느 쪽인지는 걸음 ①이 정한다. 두 갈래를 각각 수식으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 참 쪽: 모든 정수 $n$에 대해 $n^2 + n = 2k$인 정수 $k$가 존재함을 보인다. 거짓 쪽: $n_0^2 + n_0$이 짝수가 아닌 정수 $n_0$가 존재함을 보인다 — 곧 증인 하나와 두 검증(C7주차 §1.4). 두 도착점은 서로 배타적이므로 하나를 고르기 전에는 첫 줄을 쓸 수 없다. 이것이 이번 주의 답안이 판정 선언으로 시작하는 이유다. ::: **걸음 ① 정찰.** 급소부터 넣는다. $0$, 음수, 작은 수를 우선한다. | **$n$** | **$n^2 + n$** | **짝$\cdot$홀** | |---|---|---| | $1$ | $2$ | 짝수 | | $2$ | $6$ | 짝수 | | $0$ | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ | | $-1$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ | | $3$ | $12$ | 짝수 | :::{container} quotebox **확인 11.** 표의 (1)~(4)를 채우고, 이 정찰이 §1.4의 급소 중 어느 것을 덮었고 어느 것을 덮지 않았는지 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $0$ (2) 짝수 (3) $0$ (4) 짝수. ($(-1)^2 + (-1) = 1 - 1 = 0$이다.) 덮은 급소: $0$, 음수, 아주 작은 수. 덮지 않은 급소: $0$과 $1$ 사이의 분수, 빈 집합. 다만 무대가 정수이므로 분수와 집합 관련 급소는 이 명제에 적용되지 않고, 소수 $2$는 $n = 2$에서 이미 대입되었다. **무대가 급소 목록의 어느 줄을 살리는지 먼저 보는 것**이 정찰의 순서를 정하는 방법이다. ::: **걸음 ② 추측.** 다섯 값 전부 짝수이고 급소도 통과했으므로 **참으로 추측한다**. 이 시점의 라벨은 추측이며, 아래 걸음 ③이 끝나기 전까지 아무것도 확정되지 않았다. **걸음 ③ 결단 — 어느 기법인가.** 참 추측이므로 증명을 쓴다. 기법은 C9주차 지도의 2단계가 정한다. :::{container} quotebox **확인 12.** 이 명제의 결론 "$n^2 + n$은 짝수이다"의 겉모양은 무엇이고, 지도의 어느 갈래로 가는가. 그리고 곧바로 정의를 풀면 무엇이 막히는가. ::: :::{admonition} 답 :class: quotebox dropdown 겉모양은 $\forall$ 안에 숨은 $\exists$다 — "짝수"의 정의가 "$n^2 + n = 2k$인 정수 $k$가 존재한다" 이므로, 지도의 2단계는 직접 증명과 구성을 가리킨다. 곧바로 정의를 풀면 막힌다. 가정 쪽에는 "$n$은 정수"뿐이라 풀 정의가 없고, 목표 쪽의 $k$를 만들려면 $n^2 + n$을 $2 \times (\text{정수})$로 묶어야 하는데 $n$의 짝$\cdot$홀을 모르므로 $n$을 등식으로 펼칠 수 없다. 재료가 하나 더 필요하다. ::: :::{container} quotebox **확인 13.** $n^2 + n$을 인수분해해 보자. 그 결과가 이미 증명된 어느 명제와 맞물리는가. ::: :::{admonition} 답 :class: quotebox dropdown $n^2 + n = n(n+1)$ — 연속한 두 정수의 곱이다. 이 꼴은 "연속한 두 정수의 곱은 짝수이다"(1권 1주차 문제 16, 근거 ④)와 정확히 맞물린다. 그 명제가 경우 나누기로 이미 증명되어 있으므로, 이번 답안은 경우 나누기를 다시 하지 않고 부품으로 인용한다. 인수분해 한 줄이 막힘을 푼 이유는 $n$의 짝$\cdot$홀을 몰라도 되는 꼴로 바꿨기 때문이다 — 연속한 두 정수 중 하나는 반드시 짝수이므로 어느 쪽인지 알 필요가 없다. ::: :::{container} quotebox **확인 14.** 이제 증인 $k$를 만들어 보자. $n(n+1)$이 짝수이면 정의에 의해 무엇을 받을 수 있고, 그것이 목표의 $k$와 어떻게 연결되는가. ::: :::{admonition} 답 :class: quotebox dropdown 정의에 의해 $n(n+1) = 2m$인 정수 $m$을 받는다. 그 $m$이 곧 목표의 증인이다 — $n^2 + n = n(n+1) = 2m$이고 $m$은 정수이므로 짝수의 정의가 그대로 충족된다. 받아 온 정수를 그대로 증인으로 내놓는 것이 구성법의 가장 짧은 경우다(S5주차 문제 3). ::: :::{container} quotebox **확인 15.** 마지막 문장을 완성해 보자: "따라서 모든 정수 $n$에 대해 $n^2 + n$은 $\underline{\qquad}$이므로, 이 명제는 $\underline{\quad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown "따라서 모든 정수 $n$에 대해 $n^2 + n$은 **짝수**이므로, 이 명제는 **참**이다." P-or-D 답안은 마지막에 판정을 다시 선언하고 끝낸다. 증명을 다 쓰고도 판정을 적지 않으면 지시문("증명하거나 반증하라")에 답하지 않은 답안이 된다. ::: **완성본.** 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 정찰: $n = 0, \pm1, 2, 3$에서 $n^2 + n$은 각각 $0, 2, 0, 6, 12$로 모두 짝수이다. 참으로 추측한다. | 걸음 ①②. 답안에 정찰을 적는 이유는 걸음 ③의 방향이 어디서 왔는지 밝히기 위함이다. 이 줄은 증거가 아니라 방향의 출처다. | | 이 명제는 참이다. 곧 모든 정수 $n$에 대해 $n^2 + n = 2k$인 정수 $k$가 존재함을 보인다. | 판정 선언. 확인 10의 두 갈래 중 하나를 골라 도착점을 못 박는다. 이 줄이 없으면 아래 계산이 무엇을 향한 것인지 확정되지 않는다. | | $n$을 정수라 하자. 그러면 $n^2 + n = n(n+1)$이다. | 대상을 문자로 잡고 인수분해한다. $n$의 짝$\cdot$홀을 모르는 상태에서 계산을 시작할 수 있게 만드는 변형이다(확인 13). | | $n$과 $n+1$은 연속한 두 정수이므로, 1권 1주차 문제 16에 의해 그 곱은 짝수이다. | 근거 ④. 출처를 대고 한 줄로 끝낸다. 경우 나누기를 여기서 다시 하지 않는 이유는 그 작업이 인용한 명제 안에 이미 들어 있기 때문이다. | | 따라서 $n(n+1) = 2m$인 정수 $m$이 존재하고, $n^2 + n = 2m$이다. | 짝수의 정의를 풀어 정수를 받고, 그것을 목표의 증인으로 그대로 내놓는다(확인 14). | | $m$은 정수이므로 $n^2 + n$은 짝수의 정의를 만족한다. 따라서 이 명제는 참이다. $\blacksquare$ | 증인의 자격을 확인하고 판정을 다시 선언하며 마무리한다. | **정찰이 답안에서 하는 일.** 위 답안에서 첫 줄(정찰)을 지워도 증명은 성립한다. 그럼에도 적는 이유는 두 가지다. 첫째, 판정 선언이 어디서 왔는지 독자가 복원할 수 있다. 둘째, 채점자가 방향을 근거 있게 정했는지 구분할 수 있다. 다만 정찰 줄은 **근거가 아니므로** 아래 줄에서 인용되지 않는다 — 증명의 무게는 전부 넷째$\cdot$다섯째 줄이 지고 있다. ### 예제 2.2 — 거짓 명제: 정찰에서 반례와 수리까지 **명제 (P-or-D).** 모든 양의 정수 $n$에 대해, $n^2 - n + 11$은 소수이다. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. (이 반례는 C7주차 §3 훈련 3에서 서식 연습의 재료였다. 그때는 "이 주장은 거짓이다"가 미리 주어져 있었고, 이번의 과제는 그 표시 없이 반례에 **도달하는 것**이다.) :::{container} quotebox **확인 16.** 정찰을 $n = 1$부터 $10$까지 마쳤고 값은 $11, 13, 17, 23, 31, 41, 53, 67, 83, 101$로 전부 소수였다. 여기서 걸음 ②를 어느 쪽으로 정하겠는가. 그리고 그 결정을 내리기 전에 아직 넣지 않은 급소가 있는지 점검해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 아직 정하지 않는다. §1.4 목록에서 **상수항이 지목하는 값**이 남아 있고, 이 명제는 상수항이 $11$이므로 그 급소가 살아 있다. 값이 $11$의 배수가 되는 $n$을 먼저 넣어야 정찰이 끝난다. 열 번의 통과만으로 참을 추측하면 §1.3의 삭제 실험 (가)와 같은 답안이 된다. 정찰을 언제 멈추는가에 대한 규칙은 이것이다 — **적용되는 급소를 전부 넣기 전에는 멈추지 않는다.** ::: :::{container} quotebox **확인 17.** $n^2 - n + 11$을 $n(n-1) + 11$로 다시 적어 보자. 값이 $11$의 배수가 되려면 $n$이 어떤 수여야 하는가. 그중 반례가 되는 가장 작은 값은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown $11$이 이미 $11$의 배수이므로, 값 전체가 $11$의 배수가 되려면 $n(n-1)$이 $11$의 배수여야 한다. $11$이 소수이므로 유클리드 보조정리에 의해 $11 \mid n$ 또는 $11 \mid n - 1$이다 — 곧 $n$이 $11$의 배수이거나 $11$의 배수보다 $1$ 큰 수다. 후보를 작은 것부터 적으면 $n = 1, 11, 12, 22, 23, \ldots$이고, $n = 1$은 값이 $11$ 자신이라 소수이므로 제외된다. 다음이 $n = 11$이며 값은 $121 = 11 \cdot 11$이다. $11$의 배수이면서 $11$보다 큰 수는 합성수이므로, 이 조건이 반례를 보장한다. ::: | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 정찰: $n = 1, \ldots, 10$에서 값은 $11, 13, 17, 23, 31, 41, 53, 67, 83, 101$로 전부 소수이다. 그러나 상수항 $11$이 급소를 지목하므로 정찰을 멈추지 않는다. | 걸음 ①. 열 번의 통과가 결론이 아님을 답안 안에서 밝힌다. 정찰을 멈추지 않은 이유까지 적는 것이 이 줄의 몫이다. | | $n^2 - n + 11 = n(n-1) + 11$이므로, $n$이 $11$의 배수이면 값 전체가 $11$의 배수가 된다. $n = 11$을 대입하면 $121$이다. 거짓으로 추측한다. | 걸음 ①의 계속과 걸음 ②. 급소를 산술로 계산해 낸 자리이며, 여기서 방향이 뒤집힌다. | | 이 명제는 거짓이다. 곧 "$n_0^2 - n_0 + 11$이 소수가 아닌 양의 정수 $n_0$가 존재한다"를 증명한다 [C7주차 §1.4 걸음 ①]. | 판정 선언과 부정 전개. 반증도 증명이므로 무엇을 증명할지 못 박는다. | | $n_0 = 11$로 두자. | 걸음 ② 증인 제시. 정찰이 찾아낸 값을 서식의 자리에 놓는다. | | $11$은 양의 정수이므로 무대 안에 있다. | 걸음 ③ 자격 검증. 조건문이 아닌 $\forall$ 명제이므로 자격은 무대 소속만 확인하면 된다. | | $11^2 - 11 + 11 = 121 = 11 \cdot 11$이고 $11 > 1$이므로, $121$은 $1$보다 큰 두 정수의 곱이며 따라서 소수가 아니다. | 걸음 ④ 사건 검증. 합성수의 정의를 실제로 적용한다. 계산 결과만 적고 넘어가지 않는다. | | 따라서 그러한 양의 정수가 존재하므로 이 명제는 거짓이다. $\blacksquare$ | 판정의 재선언. 여기까지가 걸음 ③이다. | | 수리: 무대를 $1 \le n \le 10$으로 좁히면 참이지만 유한 확인에 지나지 않아 얻는 것이 없다. 대신 관찰을 적는다 — 이 다항식은 $n$이 $11$의 배수이거나 $11$의 배수보다 $1$ 큰 자리에서 반드시 $11$의 배수가 되므로, 값이 $11$보다 큰 그런 $n$ 전부가 반례다. | 걸음 ④. 수리가 시시해지는 경우에는 그 사실을 적고, 대신 반례가 하나가 아니라 무한히 많음을 밝힌다. | **수리가 시시해지는 경우.** 자격을 좁혀도 유한 개의 확인으로 되돌아갈 뿐이면 그 수리는 정보를 주지 않는다. 그때 할 일은 수리를 억지로 만드는 것이 아니라 **반례의 구조를 밝히는 것**이다 — 위 답안의 마지막 줄이 그 일을 한다. 반례가 왜 그 자리에 있는지를 적으면, 같은 모양의 다른 명제에서 급소를 바로 계산할 수 있다. 문제 15와 18이 그 이식을 시험한다. ### 예제 2.3 — 반례와 증명의 왕복: 조건을 바꿔 가며 **명제 A (P-or-D).** 정수 $a, b$에 대해, $a \mid b$이고 $b \mid a$이면 $a = b$이다. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 18.** 명제 A를 정찰해 보자. 이 명제는 조건문이므로 정찰에 넣는 값이 **가정을 만족해야** 한다. 급소 목록에서 어느 줄을 먼저 쓰겠는가. 그리고 명제 A가 거짓이면 명제 B를 어떻게 만들겠는가. ::: :::{admonition} 답 :class: quotebox dropdown 급소는 **음수**다. 나눗셈은 부호를 지우지 않으므로 $a$와 $b$의 부호가 다를 때 가정은 살아 있고 결론만 깨질 수 있다. $a = -2$, $b = 2$가 그 자리다. 가정 검증: $2 = (-2) \cdot (-1)$이므로 $-2 \mid 2$이고, $-2 = 2 \cdot (-1)$이므로 $2 \mid -2$이다. 결론 위반: $-2 \neq 2$이다. 명제 B는 수리의 두 방향 중 하나로 만든다. 가정 강화이면 반례가 사는 음수를 잘라 "양의 정수 $a, b$"로 좁히고, 결론 약화이면 부호를 지워 "$\lvert a \rvert = \lvert b \rvert$"로 고친다. 아래에서는 앞쪽을 택한다 — 뒤쪽은 1권 2주차 문제 20이 이미 증명한 것이다. ::: **명제 A의 반증.** 명제 A는 거짓이다. 곧 "$a \mid b$이고 $b \mid a$이면서 $a \neq b$인 정수 $a, b$가 존재한다"를 증명한다. $a = -2$, $b = 2$로 두자. 둘 다 정수이므로 무대 안에 있고, $2 = (-2)(-1)$이므로 $-2 \mid 2$이며 $-2 = 2 \cdot (-1)$이므로 $2 \mid -2$이다 — 가정이 성립한다. 그런데 $-2 \neq 2$이므로 결론이 위반된다. 따라서 그러한 정수쌍이 존재하고, 명제 A는 거짓이다. $\blacksquare$ **명제 B (수리, P-or-D).** 양의 정수 $a, b$에 대해, $a \mid b$이고 $b \mid a$이면 $a = b$이다. **명제 B의 판정.** 정찰부터 다시 한다. $a = b = 3$에서 성립하고, $a = 2$, $b = 6$은 $6 \mid 2$가 거짓이라 가정을 만족하지 않으므로 반례 후보가 아니다. 무대에서 음수가 빠졌으므로 명제 A의 반례는 더 이상 들어오지 못한다. 참으로 추측한다. **증명.** 명제 B는 참이다. $a, b$를 양의 정수라 하고 $a \mid b$, $b \mid a$라 하자. 정의에 의해 $b = ak$, $a = bl$인 정수 $k, l$이 존재한다. 둘째 등식에 첫째 등식을 대입하면 $$ a = bl = (ak)l = a(kl) $$ 이고, $a > 0$이므로 양변을 $a$로 나누면 $kl = 1$이다. 한편 $a > 0$이고 $b = ak > 0$ 이므로 $k > 0$이며, 같은 이유로 $l > 0$이다. 곱이 $1$인 두 양의 정수는 $k = l = 1$ 뿐이므로 $b = ak = a$이다. 따라서 $a = b$이고 명제 B는 참이다. $\blacksquare$ 이 답안은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 답안은 처음부터 끝까지 이런 산문이다. **두 명제를 나란히 놓으면.** 명제 A와 B의 차이는 무대 한 줄뿐이고, 증명의 계산은 거의 같다. 갈린 자리는 $kl = 1$ 다음 줄이다 — 무대가 정수 전체이면 $(k, l)$이 $(1, 1)$과 $(-1, -1)$의 두 가지이고, 양의 정수이면 $(1, 1)$ 하나다. 명제 A의 반례는 정확히 버려진 그 경우에 살고 있었다(§1.3 확인 4). **반례는 명제를 지우는 것이 아니라 명제가 성립하는 정확한 범위를 알려 준다.** ### 관찰 — 세 예제의 같은 뼈대 예제 2.1, 2.2, 2.3은 결론이 서로 다르지만 밟은 순서가 같다. 대응표의 빈칸을 채워 보자. | **걸음** | **예제 2.1** | **예제 2.2** | **예제 2.3 (명제 A)** | |---|---|---|---| | ① 정찰 | $n = 0, \pm1, 2, 3$ | $n = 1, \ldots, 10$과 $n = 11$ | $\underline{\quad(1)\quad}$ | | ② 추측 | 참 | 거짓 | 거짓 | | ③ 결단 | $n(n+1)$의 인수분해로 증명 | $\underline{\quad(2)\quad}$ | 반례 $(-2, 2)$와 두 검증 | | ④ 수리 | 해당 없음 | 반례의 구조를 밝힘 | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 19.** 표의 (1)(2)(3)을 채우고, 걸음 ④가 "해당 없음"이 되는 조건을 한 줄로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 음수 급소 — $a = -2$, $b = 2$. (2) 반례 $n_0 = 11$과 두 검증(무대 소속, $121 = 11 \cdot 11$). (3) 무대를 양의 정수로 좁혀 명제 B를 만들고 다시 정찰$\cdot$증명했다. 걸음 ④가 해당 없음이 되는 조건: **걸음 ②의 추측이 참이었고 걸음 ③이 증명으로 끝난 경우.** 수리는 거짓으로 확정된 명제에만 있는 걸음이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **P-or-D 답안의 서식** ① **정찰 기록** — 대입한 값과 결과를 적고, 어느 급소를 덮었는지 밝힌다. 이 줄은 방향의 출처이지 근거가 아니다. ② **판정 선언** — "이 명제는 참이다" 또는 "이 명제는 거짓이다"를 한 문장으로 적고, 그것이 무엇을 증명한다는 뜻인지 이어 적는다. ③ **확정** — 참이면 완전한 증명, 거짓이면 반례 4단 서식(C7주차 §1.4). ④ **수리** — 거짓이면 자격을 좁힌 명제를 적고, 그 명제도 다시 정찰$\cdot$증명한다. 수리가 시시하면 반례의 구조를 대신 밝힌다. ::: 이 서식이 다음 주 C11주차부터는 겉으로 드러나지 않는다. 그러나 참인 정리만 나오는 주차에서도 걸음 ①은 남는다 — 정리를 읽고 작은 사례에 대입해 보는 일이 진술을 정확히 읽었는지 검사하는 가장 값싼 방법이기 때문이다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식과 절차의 빈칸 **명제 (P-or-D).** 모든 실수 $x$에 대해, $x^2 \ge x$이다. **걸음 ① 정찰.** $x = 2$: $4 \ge 2$ ✓. $x = 0$: $0 \ge 0$ ✓. $x = -1$: $1 \ge -1$ ✓. 급소 목록에서 아직 넣지 않은 것은 $0$과 $1$ 사이의 분수다. $x = \tfrac12$: $\tfrac14 \ge \tfrac12$은 $\underline{\quad(1)\quad}$(참$\cdot$거짓). **걸음 ② 추측.** $\underline{\quad(2)\quad}$으로 추측한다. **걸음 ③ 확정.** 이 명제는 $\underline{\quad(3)\quad}$이다. 곧 "$x_0^2 \ge x_0$이 성립하지 않는 실수 $x_0$가 존재한다"를 증명한다. $x_0 = \tfrac12$로 두자. 자격 — $\tfrac12$은 $\underline{\quad(4)\quad}$이다. 사건 — $\left(\tfrac12\right)^2 = \tfrac14$이고 $\tfrac14 < \tfrac12$이므로 부등식이 위반된다. 따라서 그러한 실수가 존재한다. $\blacksquare$ **걸음 ④ 수리.** $x^2 - x = x(x-1)$이 음수가 되는 구간은 $\underline{\quad(5)\quad}$ 이므로, 그 구간만 잘라 내면 "$x \le 0$ 또는 $x \ge 1$이면 $x^2 \ge x$"가 참이다. 무대를 $\underline{\quad(6)\quad}$로 바꾸는 수리도 가능하다 — 그 무대에는 $0$과 $1$ 사이의 값이 없기 때문이다. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장, 수리의 방향 이름도 빈칸이다. **명제 (P-or-D).** 모든 자연수 $n$에 대해, $2^n > n^2$이다. **걸음 ① 정찰.** 급소 목록의 "아주 작은 수"와 "등호가 성립하는 자리"부터 넣는다. | **$n$** | **$2^n$** | **$n^2$** | **판정** | |---|---|---|---| | $1$ | $2$ | $1$ | 성립 | | $2$ | $4$ | $4$ | $\underline{\quad(1)\quad}$ | | $3$ | $8$ | $9$ | 위반 | | $4$ | $16$ | $16$ | 위반 | | $5$ | $32$ | $25$ | 성립 | **걸음 ②③.** 위반이 나왔으므로 이 명제는 $\underline{\quad(2)\quad}$이다. 반례는 $n_0 = 2$이고, 자격은 "$2$는 자연수이다", 사건은 "$2^2 = 4$이고 $2^2 = 4$이므로 $4 > 4$가 거짓이다"이다. $\blacksquare$ **걸음 ④ 수리.** 반례가 $n = 2, 3, 4$에 몰려 있고 $n = 5$부터 성립하므로, $\underline{\quad(3)\quad}$ 방향으로 수리해 "모든 자연수 $n \ge 5$에 대해 $2^n > n^2$"을 새 명제로 세운다. 이 새 명제는 다시 판정을 받아야 하므로 증명한다 (S14주차 문제 11). **수리한 명제의 증명 (귀납).** 기저: $n = 5$에서 $32 > 25$이므로 성립한다. 귀납 단계: $n \ge 5$에서 $2^n > n^2$이라 가정하면 $$ 2^{n+1} = 2 \cdot 2^n > 2n^2 = n^2 + n^2 \ge \underline{\quad(4)\quad} = (n+1)^2 $$ 이다. 마지막 부등식에서 쓴 사실은 $n \ge 5$이면 $n^2 \ge 5n = 2n + 3n > 2n + 1$ 이라는 것이다. 다만 이 부등식만 보면 $n \ge 3$에서도 성립하므로, 자격의 하한을 $5$로 정한 것은 귀납 단계가 아니라 $\underline{\quad(5)\quad}$ 때문이다. 따라서 모든 $n \ge 5$에서 성립한다. $\blacksquare$ **검산.** $n = 6$에서 $64$와 $36$을 비교하면 $\underline{\quad(6)\quad}$이다. ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 네 걸음을 통째로 채운다. (1권 29주차 문제 7의 재방문 — 그때는 "반증하시오" 라는 지시가 붙어 있었고, 이번에는 참$\cdot$거짓이 표시되지 않았다.) **명제 (P-or-D).** 모든 소수 $p$에 대해, $2^p - 1$은 소수이다. $p = 2, 3, 5, 7$에서 값은 $3, 7, 31, 127$로 전부 소수다. 그럼에도 판정을 여기서 멈추지 않는다. **답안의 뼈대.** §2 관찰의 서식의 각 칸을 통째로 채운다. - ① 정찰 기록: $\underline{\quad(1)\quad}$ - ② 판정 선언: $\underline{\quad(2)\quad}$ - ③ 확정 — 증인 제시와 두 검증: $\underline{\quad(3)\quad}$ - ④ 수리 — 자격을 좁히는 방향과 그 결과: $\underline{\quad(4)\quad}$ (정찰의 방향에 대한 안내: 다음 소수는 $11$이고 $2^{11} = 2048$이다. 이 값이 합성수인지 확인하려면 작은 소수부터 나누어 본다. 그리고 수리 쪽에서는 자격을 좁히는 길이 막힐 수 있다 — 그때는 명제의 **역**이 참인지 검토하는 것이 다음 수순이다. $n$이 합성수이면 $2^n - 1$은 어떤 꼴로 인수분해되는가.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 각 명제에 대해 정찰 $\to$ 추측 $\to$ 증명 또는 반례 $\to$ (거짓이면) 수리를 수행한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. P-or-D 답안에는 채점 항목이 넷이다. ① 판정 선언이 답안 어딘가에 한 문장으로 적혀 있는가. 판정 없는 계산은 지시문에 답하지 않은 것이다. ② 판정이 참이면 **완전한 증명**이 있는가. 정찰 기록은 증명이 아니므로 점수가 되지 않는다. ③ 판정이 거짓이면 반례에 **두 검증**(자격$\cdot$사건)이 붙어 있는가. 조건문 명제의 자격은 "가정의 성립"이다. ④ 수리를 요구한 문항에서, 수리한 명제에 **다시 판정과 증명**이 붙어 있는가. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] P-or-D 흐름 4단계, 반례 급소 목록, 수리의 두 방향(가정 강화$\cdot$결론 약화)을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 네 걸음의 이름만 외우면 절반이다. 걸음마다 "이것을 빼면 무엇이 무너지는가"를 함께 적어 두면 일부를 잊었을 때 나머지에서 복구할 수 있다. §1.3의 해부 표가 그 복구의 재료이고, 급소 목록은 §1.4의 왼쪽 열이다. ::: **2.** 각 명제를 정찰만 하고 참$\cdot$거짓을 추측하시오 (증명과 반례는 아직 적지 않는다). (a) 모든 소수는 홀수이다. (b) 두 홀수의 합은 짝수이다. (c) 자연수 $n$에 대해 $n^2 > n$이다. (d) 모든 정수는 두 제곱수의 합이다. :::{admonition} 힌트 :class: quotebox dropdown 네 문항 모두 급소 목록의 첫 줄들로 갈린다. (a)는 소수 $2$, (c)는 아주 작은 수, (d)는 작은 수를 표로 만들어 전수 대입한다 — $0, 1, 2, 3$에서 두 제곱수의 합으로 만들 수 있는 값을 모두 적어 보면 빠진 수가 보인다. (b)는 급소를 넣어도 흔들리지 않는 유일한 문항이다. ::: **3.** 예제 2.2를 백지 재현하시오 (반례 $n = 11$까지 도달하는 과정을 포함한다). :::{admonition} 힌트 :class: quotebox dropdown 반례 값만 적으면 절반이다. 열 번의 정찰을 통과한 뒤 **왜 멈추지 않았는지**와 $n(n-1) + 11$이라는 변형이 급소를 어떻게 계산해 냈는지가 이 문항의 채점 대상이다. ::: **4.** §3의 빈칸 사다리 훈련 1~3을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 1과 2는 급소를 어디에 넣는지가 전부다. 훈련 3은 정찰이 네 번 통과한 뒤 다섯째 소수에서 뒤집히는 사례이며, 수리 칸이 막히는 것이 정상이다 — 막혔다는 사실 자체를 답안에 적는 것이 §2 예제 2.2에서 배운 처리다. ::: **5.** 예제 2.3의 명제 A(반례)와 B(증명)를 백지 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 두 명제의 차이는 무대 한 줄이다. 증명 B에서 $kl = 1$ 다음 줄이 명제 A와 갈리는 자리이므로, 그 줄에서 "양의 정수"라는 조건이 어떻게 소비되는지를 밝혀 적는다. ::: **6.** "모든 실수 $x$에 대해 $\sqrt{x^2} = x$"를 P-or-D하시오 (반례를 제시하고, 이어 가정 강화와 결론 약화의 두 방향으로 각각 수리하시오). :::{admonition} 힌트 :class: quotebox dropdown 좌변은 제곱을 거치므로 부호가 지워지고 우변은 부호를 남긴다. 두 변이 부호에 다르게 반응하므로 급소는 음수다. 수리에서 결론 약화 쪽은 "부호를 지우는 연산"을 우변에도 붙이는 것이다. ::: ### 표준 ●●○ **7.** P-or-D: "정수 $a, b$에 대해, $ab$가 짝수이면 $a$와 $b$가 모두 짝수이다." 거짓이면 반례를 제시하고, 결론을 고쳐 참이 되는 명제를 만들어 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 조건문이므로 반례는 가정을 만족해야 한다 — $ab$가 짝수인 쌍 중에서 찾는다. 수리는 결론의 접속사 한 글자를 바꾸는 것으로 끝나고, 그 새 명제의 증명은 대우로 쓰는 편이 짧다(두 홀수의 곱은 홀수). ::: **8.** P-or-D: "모든 자연수 $n$에 대해 $n^2 + n + 41$은 소수이다." (1권 1주차 문제 18의 재방문 — 이번에는 참$\cdot$거짓이 표시되지 않았다.) :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2에서 쓴 방법을 그대로 옮긴다. $n^2 + n + 41 = n(n+1) + 41$이므로 $n(n+1)$이 $41$의 배수가 되는 $n$을 찾으면 값 전체가 $41$의 배수가 된다. 가장 작은 후보는 $41$의 배수가 아니라 $41$의 배수보다 $1$ 작은 수 쪽에 있다. ::: **9.** P-or-D: "정수 $n$에 대해, $n^2$이 4의 배수이면 $n$이 4의 배수이다." $n = 2$를 검토하고, 거짓이면 결론을 "$n$이 짝수이다"로 약화한 명제를 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 조건문이므로 반례는 가정 "$n^2$이 $4$의 배수"를 만족하는 $n$ 중에서 찾는다. $n$이 $2$의 인수를 하나만 가지면 그 가정은 채워지고 결론은 깨진다. 수리한 명제는 대우로 증명하는 편이 짧다 — 홀수의 제곱이 홀수임을 보이면 된다. ::: **10.** P-or-D: "모든 양의 실수 $a, b$에 대해 $\sqrt{a + b} = \sqrt a + \sqrt b$이다." 거짓이면 등호를 부등호로 바꾼 올바른 명제를 적으시오 (S6주차 문제 13). :::{admonition} 힌트 :class: quotebox dropdown 급소를 찾을 필요가 거의 없다 — 가장 평범한 값 $a = b = 1$에서 이미 두 변이 갈린다. 수리의 방향을 정하려면 두 변을 제곱해 비교한다: $(\sqrt a + \sqrt b)^2$은 $a + b$보다 항상 큰가, 작은가. ::: **11.** P-or-D: "모든 자연수 $n$에 대해 $2^n + 1$은 소수이다." 반례를 제시하고, $2^n + 1$이 소수가 되기 위한 필요조건을 찾아 수리를 시도하시오 (S18주차 문제 18의 페르마 수). :::{admonition} 힌트 :class: quotebox dropdown 정찰은 $n = 1, 2$에서 통과하고 $n = 3$에서 뒤집힌다. 수리의 방향을 찾으려면 무너진 자리의 공통점을 본다 — $n$이 홀수 인수를 가질 때 $2^n + 1$이 인수분해된다. 항등식 $x^d + 1 \mid x^{de} + 1$($e$가 홀수)이 그 인수분해를 준다. ::: **12.** P-or-D: "정수 $a, b, c$에 대해, $a \mid (b + c)$이면 $a \mid b$ 또는 $a \mid c$이다." :::{admonition} 힌트 :class: quotebox dropdown 가정을 만족시키기가 쉽다 — $b + c$가 $a$의 배수가 되도록 $b$와 $c$를 반으로 쪼개면 된다. 그러면서 각각은 $a$의 배수가 아니도록 만든다. 가장 작은 $a$부터 시도한다. ::: **13.** P-or-D: "모든 자연수 $n$에 대해 $n^3 - n$은 6의 배수이다." (C6주차 문제 15와 같은 사실을 다른 언어로 진술한 것이다.) :::{admonition} 힌트 :class: quotebox dropdown 정찰이 참을 가리키면 증명으로 간다. $n^3 - n$을 인수분해하면 연속한 세 정수의 곱이 나오고, 그중 하나는 $2$의 배수, 하나는 $3$의 배수다. 두 사실을 합쳐 $6$의 배수라고 말하려면 $2$와 $3$이 서로소라는 점을 밝혀야 한다. ::: **14.** P-or-D: "두 무리수의 곱은 무리수이다." 거짓이면 반례를 제시하고, 무리수끼리의 곱이 유리수도 무리수도 될 수 있음을 예로 보이시오. :::{admonition} 힌트 :class: quotebox dropdown 같은 무리수를 두 번 쓰는 것이 허용된다. 제곱하면 근호가 사라지는 무리수를 고르면 반례가 한 줄로 끝난다. 수리 쪽에서는 "일반적인 조건을 붙일 수 없다"는 결론도 정당한 답이며, 그 근거로 두 방향의 예를 각각 든다. ::: ### 도전 ●●● **15.** (오일러 다항식) P-or-D: "모든 정수 $n \ge 0$에 대해 $n^2 + n + 41$은 소수이다." $n = 0, \ldots, 39$에서 전부 소수임을 확인하고 $n = 40$에서 반례를 제시하시오. 그리고 왜 하필 $40$인지를 $n^2 + n + 41 = n(n+1) + 41$의 구조로 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown 마흔 개를 손으로 다 계산할 필요는 없다 — 몇 개를 확인하고 "$n \le 39$에서 소수임은 지금은 인정하고 쓴다"로 적은 뒤, 이 문항의 무게가 실린 곳인 $n = 40$의 구조 설명에 집중한다. $40 \cdot 41 + 41$에서 두 항의 공통 인수를 묶는 것이 설명의 전부다. ::: **16.** (수리의 기술) 거짓 명제 "모든 실수 $x, y$에 대해 $\lvert x + y \rvert = \lvert x \rvert + \lvert y \rvert$"를 P-or-D하고, 참이 되는 정확한 조건을 찾으시오. 그 조건이 최소한임을 확인하시오. :::{admonition} 힌트 :class: quotebox dropdown 반례는 부호가 다른 두 수에서 나온다. 참이 되는 조건을 찾으려면 양변을 제곱해 비교한다 — $(x+y)^2$과 $(\lvert x \rvert + \lvert y \rvert)^2$의 차이가 한 항으로 압축되고, 그 항이 $0$ 이상일 조건이 곧 답이다. ::: **17.** (미묘한 참) P-or-D: "정수 $n$에 대해, $n$이 홀수이면 $8 \mid (n^2 - 1)$이다." 정찰이 강하게 참을 시사하는 경우에도 확정은 증명이 한다는 점을 답안에서 밝히시오 (1권 1주차 문제 17). :::{admonition} 힌트 :class: quotebox dropdown 정찰: $n = 1, 3, 5, 7$에서 $0, 8, 24, 48$이 전부 $8$의 배수다. 증명은 $n = 2k+1$을 대입해 $n^2 - 1 = 4k(k+1)$까지 간 뒤, $k(k+1)$에서 $2$를 하나 더 꺼내는 것으로 끝난다. 그 $2$를 보장하는 것이 근거 ④의 어느 부품인가. ::: **18.** (반증 후 재추측) P-or-D: "모든 자연수 $n$에 대해 $n^2 - 79n + 1601$은 소수이다." 정찰이 여러 번 통과한 뒤에도 판정을 미루고, 큰 $n$에서 반례를 찾으시오. :::{admonition} 힌트 :class: quotebox dropdown 이 다항식은 문제 15의 다항식을 옮겨 놓은 것이다. $m = n - 40$으로 치환해 전개해 보면 정체가 드러나고, 그러면 반례의 위치도 문제 15에서 그대로 옮겨 온다. ::: **19.** (조건 탐색 종합) P-or-D: "정수 $a, b$에 대해 $a^2 + b^2 = c^2$인 정수 $c$가 존재한다." 반례를 제시하고, 참이 되는 $(a, b)$의 조건을 탐색하시오. :::{admonition} 힌트 :class: quotebox dropdown 반례는 가장 작은 값에서 나온다. 수리 쪽에서는 자격을 좁히는 조건이 유한한 목록으로 적히지 않는다 — 그럴 때 답안에 적을 것은 "조건이 닫힌 꼴로 알려져 있는가"에 대한 판정이며, $(3,4,5)$와 $(5,12,13)$처럼 성립하는 쌍이 무한히 많다는 사실도 함께 적는다. ::: **20.** (서술) (a) "정찰은 필수지만 증명이 아니다"를 예제 2.1(참)과 예제 2.2(거짓)로 뒷받침하고, 정찰의 역할이 방향 결정임을 세 문장 이내로 쓰시오. (b) 반례가 "명제를 지우는 것이 아니라 다듬는다"를 예제 2.3으로 설명하고, 증명과 반증이 "한 탐구의 두 방향"인 이유를 두 문장 이내로 쓰시오. ## 백지 재현 — 복습 프로토콜 이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Chartrand 8장 통독 — 모르는 문장은 표시만 하고 통과한다 | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다 | | 3일차 | 원서 8장 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다 | | 4일차 | 교안 §3 빈칸 사다리와 §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | **1차 시도 — 틀 카드 허용.** P-or-D 흐름의 네 걸음, 급소 목록, 수리의 두 방향만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 본문과 계산은 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] P-or-D 흐름의 네 걸음을 쓰고, 걸음마다 그것을 빼면 무엇이 무너지는지 한 줄씩 적었다. - [ ] 반례 급소 목록을 열 줄까지 재현했다. - [ ] 정찰의 비대칭(통과는 추측, 위반은 확정)을 한 문장으로 적고 그 이유를 $\forall$의 부정으로 설명했다. - [ ] 수리의 두 방향을 쓰고, 각각의 예를 하나씩 들었다. - [ ] 예제 2.1을 재현했고, 정찰 줄이 근거가 아닌 이유를 말했다. - [ ] 예제 2.2를 재현했고, 열 번의 통과 뒤에 멈추지 않은 이유를 적었다. - [ ] 예제 2.3의 명제 A와 B를 재현했고, 두 증명이 갈리는 줄을 손가락으로 짚었다. - [ ] 오일러 다항식 두 개와 페르마 수에서 정찰이 통과한 횟수를 말했다. - [ ] 원서 8장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 참인지 거짓인지 정하지 못해 첫 줄이 나오지 않는다 | §1.2의 네 걸음 — 걸음 ①은 판정 없이도 시작할 수 있는 유일한 걸음이다 | | 정찰을 어디까지 해야 할지 모르겠다 | §1.4의 급소 목록 — 무대에 적용되는 급소를 전부 넣기 전에는 멈추지 않는다 | | 몇 번 대입해 보고 참이라 적었다가 틀린다 | §1.3의 삭제 실험 (가)와 §1.5의 비대칭 표 | | 거짓 명제를 증명하려 오래 매달린다 | §1.3의 삭제 실험 (나) — 증명이 오래 막히면 정찰로 돌아간다 | | 반례를 적었는데 채점에서 반쪽으로 처리된다 | C7주차 §1.4의 걸음 삭제 실험 — 빠진 것은 대개 자격 검증이다 | | 수리한 명제를 적기만 하고 끝낸다 | §1.6 확인 8 — 수리는 새 명제를 만드는 일이므로 걸음 ①②③을 다시 받는다 | | 수리 방향이 두 가지 중 어느 쪽인지 못 고르겠다 | §1.6의 대조표 — 반례가 사는 영역을 자를 수 있으면 가정 강화, 결론을 반례까지 덮도록 고칠 수 있으면 결론 약화 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) 거짓 (2) 거짓 (3) 거짓 (4) 실수 (5) $0 < x < 1$ (6) $\mathbb{Z}$(정수 전체) ※ 이 훈련의 관절은 (1)이다. $x = 2, 0, -1$에서 세 번 통과했으므로 그 상태로 멈추면 "참"이라고 적게 되는데, 아직 넣지 않은 급소가 하나 남아 있었다. $0$과 $1$ 사이에서 제곱이 원래 수보다 작아지는 이유는 $x(x-1)$의 두 인수가 부호가 갈리기 때문이며, 그 구간이 곧 반례가 사는 영역 전체다. (6)에서 무대를 정수로 옮기는 수리가 통하는 이유는 그 영역에 정수가 하나도 없기 때문이다 — 무대 교체는 가정 강화의 한 형태이고, 반례가 사는 영역을 통째로 비우는 방식이다. ### 빈칸 사다리 — 훈련 2 (1) 위반 (2) 거짓 (3) 가정 강화(무대 축소) (4) $n^2 + 2n + 1$ (5) 기저 (6) $64 > 36$이므로 성립 ※ (4)의 근거는 $n^2 \ge 2n + 1$이므로 $n^2 + n^2 \ge n^2 + 2n + 1 = (n+1)^2$이라는 것이다. 이 부등식이 성립하려면 $n \ge 3$이면 충분하다($3^2 = 9 \ge 7$). 그럼에도 자격을 $n \ge 5$로 잡는 이유는 귀납 단계가 아니라 **기저** 때문이다 — $n = 3, 4$에서는 명제 자체가 거짓이라 기저를 놓을 수 없다. 곧 수리한 자격의 하한은 "귀납 단계가 도는 곳"이 아니라 "기저가 서는 곳"이 정한다. 반례가 $n = 2, 3, 4$의 세 개인데 자격을 $n \ge 5$ 한 줄로 좁힌 것은 최소한의 수리다. $n = 1$이 자격에서 빠진 것은 손실이지만, $1$과 $5$ 사이가 끊겨 있으므로 한 줄의 부등식으로는 되살릴 수 없다 — 되살리려면 "$n = 1$ 또는 $n \ge 5$"로 적어야 한다. ### 빈칸 사다리 — 훈련 3 (1) $p = 2, 3, 5, 7$에서 $2^p - 1$은 각각 $3, 7, 31, 127$로 전부 소수이다. 그러나 네 번의 통과는 확정이 아니므로 다음 소수 $p = 11$을 넣는다: $2^{11} - 1 = 2047$이고 $2047 = 23 \cdot 89$이므로 소수가 아니다. 거짓으로 추측한다. (2) 이 명제는 거짓이다. 곧 "$2^{p_0} - 1$이 소수가 아닌 소수 $p_0$가 존재한다"를 증명한다. (3) $p_0 = 11$로 두자. 자격 — $11$의 양의 약수는 $1$과 $11$뿐이므로 $11$은 소수이다. 사건 — $2^{11} - 1 = 2048 - 1 = 2047$이고 $2047 = 23 \cdot 89$이며 $23 > 1$, $89 > 1$이므로 $2047$은 $1$보다 큰 두 정수의 곱, 곧 소수가 아니다. 따라서 그러한 소수가 존재하므로 명제는 거짓이다. $\blacksquare$ (4) 가정 강화 쪽은 막힌다. 반례가 사는 영역이 "$p = 11$"처럼 유한한 목록으로 적히지 않고, $p = 23, 29, 37, \ldots$에서도 합성수가 나오며 어느 소수에서 소수가 되는지는 지금도 열린 문제다. 자격을 좁혀 참이 되는 조건을 닫힌 꼴로 쓸 수 없으므로 이 방향의 수리는 성립하지 않는다. 대신 **역**이 참이다: $2^n - 1$이 소수이면 $n$은 소수이다. 대우로 보인다 — $n$이 소수가 아니라 하면 $n = 1$이거나 $n$이 합성수다. $n = 1$이면 $2^1 - 1 = 1$이고 $1$은 소수가 아니다. $n$이 합성수이면 $n = de$($d, e > 1$)로 쓸 수 있고 $$ 2^n - 1 = (2^d)^e - 1 = (2^d - 1)\left((2^d)^{e-1} + \cdots + 2^d + 1\right) $$ 이며 $d > 1$이므로 $2^d - 1 \ge 3$이고 $e > 1$이므로 둘째 인수도 $2^d + 1 \ge 5$이다. 두 인수 모두 $1$보다 크므로 $2^n - 1$은 합성수, 곧 소수가 아니다. 두 경우가 전부이므로 대우가 증명되었고 결론이 나온다. ※ 수리가 막히는 것은 실패가 아니다. §2 예제 2.2에서 본 처리 그대로, 막혔다는 사실과 그 이유(반례의 영역이 닫힌 꼴로 적히지 않는다)를 답안에 적는 것이 정답이다. 그리고 원 명제가 살아나지 않을 때 역을 검토하는 것이 그다음 수순이며, 여기서는 역이 정리로 확정되었다. 원 명제와 역의 진위가 서로 독립이라는 사실을 확인하는 자리이기도 하다. ### 문제 1 **접근.** 암기 항목을 문장으로만 외우면 일부를 잊었을 때 복구할 길이 없다. 흐름은 **걸음의 목록**이고, 걸음마다 "이것을 빼면 무엇이 무너지는가"가 붙어 있다. 그 붕괴 사례를 함께 외우면 남은 걸음에서 나머지를 재구성할 수 있다. 급소 목록도 마찬가지로 "어떤 명제가 그 자리에서 무너졌는가"를 한 쌍으로 외운다. **풀이.** **P-or-D 흐름 4단계.** ① **정찰** — 작은 사례와 급소에서 명제를 시험한다. 빼면 증명과 반례 중 무엇을 쓸지 근거 없이 고르게 된다. ② **추측** — 참 쪽인지 거짓 쪽인지 하나를 선언한다. 빼면 정찰 결과가 쌓이기만 하고 다음 줄이 정해지지 않는다. ③ **결단** — 참이면 완전한 증명, 거짓이면 반례 4단 서식으로 **확정**한다. 빼면 정찰 결과가 그대로 결론이 되어 거짓 명제를 참으로 선언하게 된다. ④ **수리** — 거짓이면 자격을 좁혀 참인 명제로 되물리고 그 명제를 다시 판정한다. 빼면 남는 것이 "거짓"이라는 한 낱말뿐이다. **반례 급소 목록.** $0$ / 음수 / $0$과 $1$ 사이의 분수 / 등호가 성립하는 자리 / 아주 작은 수 / 소수 $2$ / $1$(소수도 합성수도 아니다) / 빈 집합과 한 원소 집합 / 작은 수 전수 대입 / 상수항이 지목하는 값. 목록은 근거가 아니라 탐색 도구이며, 찾아낸 값은 반드시 반례 4단 서식으로 검증한다. **수리의 두 방향.** **가정 강화**(무대 축소) — 반례가 사는 영역을 가정에서 잘라 낸다. 예: "$2^n > n^2$"을 "$n \ge 5$에서"로 좁힌다. **결론 약화**(주장 완화) — 무대는 그대로 두고 결론이 반례까지 덮도록 고친다. 예: "$\sqrt{x^2} = x$"를 "$\sqrt{x^2} = \lvert x \rvert$"로 고친다. 좋은 수리는 반례를 정확히 배제하는 최소한의 조건이며, 필요 이상으로 좁히면 참이지만 쓸모가 줄고 덜 좁히면 여전히 거짓이다. **복기.** 세 항목이 서로 물려 있다. 급소 목록은 걸음 ①의 도구이고, 수리의 두 방향은 걸음 ④의 도구다. 목록만 외우고 어느 걸음의 도구인지 모르면 답안에서 쓸 자리를 찾지 못한다. ### 문제 2 **접근.** 이 문항은 걸음 ①②까지만 요구한다. 확정 작업을 하지 않으므로 답안의 라벨은 전부 "추측"이고, 그 점을 문장에 밝히는 것이 채점 대상이다. 네 문항 모두 급소 목록의 어느 줄이 살아 있는지를 먼저 정한 뒤 그 자리에 값을 넣는다. **풀이.** **(a) 모든 소수는 홀수이다.** 무대가 소수이므로 급소 "소수 $2$"가 살아 있다. $p = 2$: $2$는 소수이고 $2 = 2 \cdot 1$이라 짝수다. 위반이 나왔으므로 **거짓으로 추측한다.** ((a)$\cdot$(c)$\cdot$(d)는 위반 사례를 실제로 찾았으므로 §1.5의 비대칭에 의해 이미 거짓이 확정되고, 추측에 머무는 것은 (b)뿐이다 — 이 문항이 걸음 ②까지만 요구한 것은 답안의 라벨 연습을 위해서다.) **(b) 두 홀수의 합은 짝수이다.** $1 + 3 = 4$, $3 + 5 = 8$, $(-1) + 1 = 0$, $(-3) + (-5) = -8$. 음수와 $0$이라는 급소를 넣어도 흔들리지 않는다. **참으로 추측한다.** **(c) 자연수 $n$에 대해 $n^2 > n$이다.** 급소 "아주 작은 수"가 살아 있다. $n = 1$: $1 > 1$이 거짓이다. **거짓으로 추측한다.** 등호가 성립하는 자리가 곧 반례가 된 경우다. **(d) 모든 정수는 두 제곱수의 합이다.** 급소 "작은 수 전수 대입"을 쓴다. 두 제곱수의 합으로 만들 수 있는 작은 값은 $0 = 0+0$, $1 = 0+1$, $2 = 1+1$, $4 = 0+4$, $5 = 1+4$, $8 = 4+4$이고, $3$은 이 목록에 없다. **거짓으로 추측한다.** (음의 정수도 전부 반례다 — 제곱수의 합은 음수가 될 수 없다.) **복기.** (a)와 (c)는 급소 한 값이 곧 반례였고, (d)는 급소가 값 하나가 아니라 **표 전체**였다 — 개별 값을 넣는 대신 "만들 수 있는 값의 목록"을 만들어 빠진 자리를 찾았다. 정찰의 형태가 명제의 꼴에 따라 달라진다는 것이 이 문항의 첫 요점이다. 둘째 요점은 네 문항의 산물이 같은 무게가 아니라는 것이다 — (a)$\cdot$(c)$\cdot$(d)는 위반을 찾았으므로 §1.5에 의해 이미 거짓으로 확정되고, 급소를 다 넣고도 흔들리지 않은 (b)만 참 **추측**에 머문다. 답안에 라벨을 적을 때 이 차이를 함께 적는다. ### 문제 3 **접근.** 반례 값 $n = 11$만 적는 답안이 가장 흔하다. 이 문항이 묻는 것은 그 값이 아니라 **거기에 도달한 과정**이다. 열 번의 정찰을 통과한 뒤 멈추지 않은 이유와, $n(n-1) + 11$이라는 변형이 급소를 어떻게 계산해 냈는지를 문장으로 적는다. **풀이.** 정찰: $n = 1, \ldots, 10$에서 값은 $11, 13, 17, 23, 31, 41, 53, 67, 83, 101$ 로 전부 소수다. 그러나 급소 목록의 마지막 줄(상수항이 지목하는 값)이 아직 남아 있으 므로 멈추지 않는다. $n^2 - n + 11 = n(n-1) + 11$이고 $11$은 이미 $11$의 배수이므로, $n(n-1)$이 $11$의 배수이면 값 전체가 $11$의 배수가 된다. $11$이 소수이므로 유클리드 보조정리에 의해 그런 $n$은 $11$의 배수이거나 $11$의 배수보다 $1$ 큰 수다. 가장 작은 후보 $n = 1$은 값이 $11$ 자신이라 소수이므로 제외되고, 다음이 $n = 11$이다. 이 명제는 거짓이다. 곧 "$n_0^2 - n_0 + 11$이 소수가 아닌 양의 정수 $n_0$가 존재한다"를 증명한다. $n_0 = 11$로 두자. 자격 — $11$은 양의 정수이므로 무대 안에 있다. 사건 — $11^2 - 11 + 11 = 121 = 11 \cdot 11$이고 $11 > 1$이므로 $121$은 $1$보다 큰 두 정수의 곱이며 따라서 소수가 아니다. 그러한 양의 정수가 존재하므로 명제는 거짓이다. $\blacksquare$ 수리: 무대를 $1 \le n \le 10$으로 좁히면 참이지만 유한 확인일 뿐이라 얻는 것이 없다. 대신 반례의 구조를 적는다 — $n$이 $11$의 배수이거나 $11$의 배수보다 $1$ 큰 수이면서 값이 $11$보다 크면 언제나 반례이므로, 반례는 하나가 아니라 무한히 많다. **복기.** 이 문항의 이식 가능한 부분은 반례 값이 아니라 그 값을 **계산해 낸 경로**다 — 상수항 $c$가 소수인 $n(n \pm 1) + c$ 꼴에서는 유클리드 보조정리가 급소의 위치를 지목한다. 값 전체가 $c$의 배수가 되는 $n$을 그 보조정리로 좁히고, 그중 값이 $c$보다 커지는 가장 작은 것을 고르면 반례가 나온다. 문제 8과 15가 같은 경로를 다른 상수항에 돌린다. **검산.** $n = 12$에서 $144 - 12 + 11 = 143 = 11 \cdot 13$ ✓ — 구조가 예측한 대로 합성수다. $n = 22$에서 $484 - 22 + 11 = 473 = 11 \cdot 43$ ✓. ### 문제 4 **접근.** 훈련 1과 2는 급소를 어디에 넣는지가 전부이고, 훈련 3은 수리가 막히는 경우의 처리가 요점이다. 채점할 때는 빈칸의 값보다 **그 값이 어느 걸음의 산물인지**를 본다. **풀이.** §6의 "빈칸 사다리 — 훈련 1$\cdot$2$\cdot$3" 항목과 대조한다. 자가 채점 기준은 넷이다. ① 훈련 1에서 $x = \tfrac12$을 넣게 만든 것이 급소 목록의 어느 줄인지 말할 수 있는가 ($0$과 $1$ 사이의 분수). ② 훈련 2에서 자격의 하한을 $n \ge 5$로 정한 것이 귀납 단계가 아니라 기저 때문임을 말할 수 있는가. ③ 훈련 3에서 가정 강화가 막힌 이유를 한 문장으로 적었는가(반례의 영역이 닫힌 꼴로 적히지 않는다). ④ 훈련 3에서 역을 검토했고 그 역이 정리임을 인수분해로 보였는가. **복기.** 세 훈련은 걸음 ④의 세 가지 결말을 하나씩 담고 있다 — 훈련 1은 수리가 깔끔하게 되는 경우, 훈련 2는 수리한 명제를 다시 증명해야 하는 경우, 훈련 3은 수리가 막혀 다른 명제로 방향을 트는 경우다. 이 세 결말이 §1.6과 §2 예제 2.2에서 각각 설명된 것이다. ### 문제 5 **접근.** 두 명제의 차이는 무대 한 줄이고 계산도 거의 같으므로, 재현에서 검사할 것은 계산이 아니라 **갈리는 줄**이다. $kl = 1$ 다음 줄에서 "양의 정수"라는 조건이 어떻게 소비되는지를 밝히지 않으면 명제 A와 B가 구분되지 않는다. **풀이.** **명제 A (거짓).** 정찰: 급소 "음수"를 넣는다. $a = -2$, $b = 2$에서 $2 = (-2)(-1)$이므로 $-2 \mid 2$이고 $-2 = 2 \cdot (-1)$이므로 $2 \mid -2$이며, $-2 \neq 2$이다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$a \mid b$이고 $b \mid a$이면서 $a \neq b$인 정수 $a, b$가 존재한다"를 증명한다. $a = -2$, $b = 2$로 두자. 자격 — 둘 다 정수이고 위 계산으로 가정 두 조건이 성립한다. 사건 — $-2 \neq 2$이므로 결론이 위반된다. 따라서 명제 A는 거짓이다. $\blacksquare$ **명제 B (참).** 수리: 반례가 사는 음수를 무대에서 잘라 "양의 정수 $a, b$"로 좁힌다. 정찰에서 반례가 나오지 않으므로 참으로 추측하고 증명한다. $a, b$를 양의 정수라 하고 $a \mid b$, $b \mid a$라 하자. 정의에 의해 $b = ak$, $a = bl$인 정수 $k, l$이 존재한다. 대입하면 $a = (ak)l = a(kl)$이고, $a > 0$이므로 양변을 $a$로 나누어 $kl = 1$을 얻는다. $a > 0$이고 $b = ak > 0$이므로 $k > 0$이고, 같은 이유로 $l > 0$이다. 곱이 $1$인 두 양의 정수는 $k = l = 1$뿐이므로 $b = a$이다. 따라서 명제 B는 참이다. $\blacksquare$ **복기.** 갈리는 줄은 $kl = 1$ 바로 다음이다. 무대가 정수 전체이면 $(k, l)$이 $(1, 1)$과 $(-1, -1)$의 두 가지이고, 뒤쪽이 $b = -a$를 낳는다 — 그것이 명제 A의 반례가 사는 자리다. 무대를 양의 정수로 좁히면 $k > 0$이라는 한 줄이 그 경우를 지운다. **반례가 사는 자리는 증명이 막혔던 자리와 같다**는 것이 §1.3 확인 4에서 본 규칙이고, 이 문항이 그 규칙을 두 명제로 나란히 보여 준다. **검산.** 명제 B의 결론을 $a = 4$, $b = 4$에서 확인하면 $4 \mid 4$가 양쪽으로 성립하고 $a = b$ ✓. $a = 2$, $b = 4$는 $4 \mid 2$가 거짓이라 가정을 만족하지 않으므로 검사 대상이 아니다. ### 문제 6 **접근.** 좌변은 제곱을 거치므로 부호가 지워지고 우변은 부호를 그대로 남긴다. 두 변이 부호에 다르게 반응하므로 급소는 음수다. 수리에서는 두 방향이 모두 열려 있다 — 부호가 문제이므로, 음수를 무대에서 자르거나(가정 강화) 우변에도 부호를 지우는 연산을 붙인다(결론 약화). **풀이.** 정찰: $x = 2$에서 $\sqrt4 = 2$ ✓, $x = 0$에서 $\sqrt0 = 0$ ✓, $x = -1$에서 좌변은 $\sqrt{(-1)^2} = \sqrt1 = 1$이고 우변은 $-1$이다. 위반이 나왔으므로 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$\sqrt{x_0^2} \neq x_0$인 실수 $x_0$가 존재한다"를 증명한다. $x_0 = -1$로 두자. 자격 — $-1$은 실수이므로 무대 안에 있다. 사건 — $\sqrt{(-1)^2} = \sqrt{1} = 1$이고 $1 \neq -1$이다. 따라서 그러한 실수가 존재하므로 명제는 거짓이다. $\blacksquare$ 수리 (가정 강화): "$x \ge 0$이면 $\sqrt{x^2} = x$이다." 증명 — $x \ge 0$이라 하자. 제곱근의 정의에 의해 $\sqrt{x^2}$은 제곱하여 $x^2$이 되는 음이 아닌 실수이고, $x$도 제곱하여 $x^2$이 되는 음이 아닌 실수이다. 그런 실수는 하나뿐이므로 $\sqrt{x^2} = x$이다. $\blacksquare$ 수리 (결론 약화): "모든 실수 $x$에 대해 $\sqrt{x^2} = \lvert x \rvert$이다." 증명 — $x \ge 0$이면 $\lvert x \rvert = x$이므로 위 결과가 그대로 결론이다. $x < 0$이면 $\lvert x \rvert = -x > 0$이고 $(-x)^2 = x^2$이므로, 같은 이유로 $\sqrt{x^2} = -x = \lvert x \rvert$이다. 두 경우가 전부이므로 결론이 성립한다. $\blacksquare$ **복기.** 두 수리는 서로 다른 것을 얻는다. 가정 강화는 원래의 등식을 그대로 살리는 대신 적용 범위를 반으로 줄였고, 결론 약화는 범위를 유지하는 대신 결론의 우변을 고쳤다. 쓸모로 보면 뒤쪽이 넓다 — 실수 전체에서 쓸 수 있기 때문이다. **두 방향이 모두 열려 있을 때는 무대를 잃지 않는 쪽이 대개 낫다.** **검산.** $x = -3$에서 $\sqrt{9} = 3 = \lvert -3 \rvert$ ✓. $x = 3$에서 $\sqrt9 = 3 = \lvert 3 \rvert$ ✓. ### 문제 7 **접근.** 조건문이므로 반례는 가정 "$ab$가 짝수"를 만족해야 한다. 결론이 "$a$와 $b$가 **모두** 짝수"라는 강한 주장이므로, 곱만 짝수이고 한쪽은 홀수인 쌍을 만들면 된다. 수리는 결론의 접속사를 바꾸는 것으로 끝나고, 새 명제의 증명은 대우가 짧다. **풀이.** 정찰: $a = 2$, $b = 4$에서 가정과 결론이 모두 성립한다. $a = 2$, $b = 3$에서 $ab = 6$은 짝수이고 $b = 3$은 홀수다. 위반이 나왔으므로 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$ab$가 짝수이면서 $a$와 $b$가 모두 짝수인 것은 아닌 정수쌍이 존재한다"를 증명한다. $a = 2$, $b = 3$으로 두자. 자격 — 둘 다 정수이고 $ab = 6 = 2 \cdot 3$이므로 $ab$는 짝수이다(가정 성립). 사건 — $3 = 2 \cdot 1 + 1$이므로 $b$는 홀수이고, 따라서 "$a$와 $b$가 모두 짝수"가 거짓이다. 따라서 명제는 거짓이다. $\blacksquare$ 수리 (결론 약화): "정수 $a, b$에 대해, $ab$가 짝수이면 $a$ 또는 $b$가 짝수이다." 증명 (대우) — $a$와 $b$가 모두 홀수라 하자. $a = 2s+1$, $b = 2t+1$인 정수 $s, t$가 존재하고, $$ ab = (2s+1)(2t+1) = 4st + 2s + 2t + 1 = 2(2st + s + t) + 1 $$ 이다. $2st + s + t$는 정수이므로 $ab$는 홀수이고, 곧 짝수가 아니다. 대우가 증명되었으므로 원 명제도 참이다. $\blacksquare$ **복기.** $\land$를 $\lor$로 바꾸는 수리는 결론 약화의 가장 짧은 형태다. 약화가 정확히 반례를 배제하는지 확인하는 방법은 반례를 새 명제에 다시 넣어 보는 것이다 — $a = 2$, $b = 3$ 에서 "$a$ 또는 $b$가 짝수"는 참이므로 반례가 무력화되었다. **검산.** $a = 3$, $b = 5$에서 $ab = 15$는 홀수이므로 가정이 거짓이고 명제는 공허하게 참이다 ✓. $a = 6$, $b = 7$에서 $ab = 42$는 짝수이고 $a$가 짝수이므로 결론도 참이다 ✓. ### 문제 8 **접근.** 예제 2.2에서 쓴 방법을 그대로 옮긴다. 상수항이 $41$이므로 급소는 값 전체가 $41$의 배수가 되는 자리다. $n^2 + n + 41 = n(n+1) + 41$이므로 $n(n+1)$이 $41$의 배수가 되는 $n$을 찾는다. 예제 2.2와 달리 이번에는 $n$과 $n+1$이므로, $41$의 배수보다 $1$ 작은 수 쪽이 먼저 걸린다. **풀이.** 정찰: $n = 1, 2, 3$에서 $43, 47, 53$으로 전부 소수이고, 계속 넣어도 소수가 나온다. 그러나 상수항 $41$이 급소를 지목하므로 멈추지 않는다. $41$이 소수이므로 유클리드 보조정리에 의해 $41 \mid n(n+1)$이려면 $41 \mid n$ 또는 $41 \mid n+1$이어야 하고, 후자를 만족하는 가장 작은 자연수가 $n = 40$이다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$n_0^2 + n_0 + 41$이 소수가 아닌 자연수 $n_0$가 존재한다"를 증명한다. $n_0 = 40$으로 두자. 자격 — $40$은 자연수이므로 무대 안에 있다. 사건 — $$ 40^2 + 40 + 41 = 40 \cdot 41 + 41 = 41(40 + 1) = 41^2 = 1681 $$ 이고 $41 > 1$이므로 $1681$은 $1$보다 큰 두 정수의 곱이며 따라서 소수가 아니다. 그러한 자연수가 존재하므로 명제는 거짓이다. $\blacksquare$ 수리: 자격을 $1 \le n \le 39$로 좁히면 참이지만 유한 확인이라 얻는 것이 없다. 반례의 구조를 대신 적는다 — $n$이 $41$의 배수이거나 $41$의 배수보다 $1$ 작은 수이면 값이 $41$의 배수가 되므로, 그런 $n$ 전부가 반례다($n = 41$에서 $41 \cdot 42 + 41 = 41 \cdot 43$). **복기.** 예제 2.2와 이 문항의 차이는 다항식이 $n(n-1)$이냐 $n(n+1)$이냐 하나뿐이고, 그 차이가 급소의 위치를 $11$에서 $40$으로 옮겼다. **급소는 외우는 것이 아니라 상수항과 인수분해 꼴에서 계산하는 것**이라는 점이 이식 가능한 패턴이다. **검산.** $n = 41$에서 $1681 + 41 + 41 = 1763 = 41 \cdot 43$ ✓. ### 문제 9 **접근.** 조건문이므로 반례는 $n^2$이 $4$의 배수인 $n$ 중에서 찾는다. $n$이 $4$의 배수가 아니면서 $n^2$이 $4$의 배수이려면 $n$이 $2$의 인수를 하나만 가지면 되므로, 급소 "아주 작은 수"에서 $n = 2$가 곧바로 나온다. 수리는 결론 약화 쪽이며, 약화된 명제는 대우로 증명하는 것이 짧다. **풀이.** 정찰: $n = 4$에서 $16$이 $4$의 배수이고 $n$도 $4$의 배수다. $n = 2$에서 $n^2 = 4$는 $4$의 배수인데 $n = 2$는 $4$의 배수가 아니다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$n_0^2$이 $4$의 배수이면서 $n_0$은 $4$의 배수가 아닌 정수 $n_0$이 존재한다"를 증명한다. $n_0 = 2$로 두자. 자격 — $2$는 정수이고 $2^2 = 4 = 4 \cdot 1$이므로 $4 \mid n_0^2$이다(가정 성립). 사건 — $4k = 2$인 정수 $k$는 없으므로 $4 \nmid 2$이다. 따라서 명제는 거짓이다. $\blacksquare$ 수리 (결론 약화): "정수 $n$에 대해, $n^2$이 $4$의 배수이면 $n$은 짝수이다." 증명 (대우) — $n$이 홀수라 하자. $n = 2s+1$인 정수 $s$가 존재하고 $n^2 = 4s^2 + 4s + 1 = 2(2s^2 + 2s) + 1$이므로 $n^2$은 홀수다. 홀수는 $2$의 배수가 아니므로 $4$의 배수도 아니다. 대우가 증명되었으므로 원 명제도 참이다. $\blacksquare$ **복기.** 반례 $n = 2$가 알려 준 것은 "$n^2$이 $4$의 배수"라는 가정이 $n$에게서 $2$의 인수를 **하나만** 보장한다는 사실이다. 결론을 그 보장에 맞춰 "짝수"로 낮춘 것이 최소한의 수리이며, "$n$이 $2$의 배수"보다 더 낮출 필요도 없다. **반례가 가정의 실제 힘을 알려 주고, 그 힘에 맞춰 결론을 정하는 것**이 결론 약화의 요령이다. **검산.** $n = 6$에서 $36 = 4 \cdot 9$이므로 가정이 성립하고 $6$은 짝수 ✓. $n = 3$에서 $9$는 $4$의 배수가 아니므로 가정이 거짓이고 명제는 공허하게 참이다 ✓. ### 문제 10 **접근.** 급소를 찾을 필요가 거의 없다 — 가장 평범한 값에서 이미 두 변이 갈린다. 수리의 방향은 두 변을 제곱해 비교하면 정해진다. 우변의 제곱이 좌변의 제곱보다 항상 크거나 같으므로, 등호를 부등호로 바꾸는 결론 약화가 답이다. **풀이.** 정찰: $a = b = 1$에서 좌변은 $\sqrt2 \approx 1.414$이고 우변은 $2$이다. 위반이 나왔으므로 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$\sqrt{a_0 + b_0} \neq \sqrt{a_0} + \sqrt{b_0}$인 양의 실수 $a_0, b_0$이 존재한다"를 증명한다. $a_0 = b_0 = 1$로 두자. 자격 — $1$은 양의 실수이다. 사건 — 좌변은 $\sqrt2$이고 우변은 $1 + 1 = 2$인데, $(\sqrt2)^2 = 2 \neq 4 = 2^2$이고 두 수 모두 음이 아니므로 $\sqrt2 \neq 2$이다. 따라서 명제는 거짓이다. $\blacksquare$ 수리 (결론 약화): "모든 양의 실수 $a, b$에 대해 $\sqrt{a+b} \le \sqrt a + \sqrt b$이다." 증명 — 두 변 모두 음이 아니므로 제곱을 비교해도 대소가 보존된다. $$ (\sqrt a + \sqrt b)^2 = a + 2\sqrt{ab} + b = (a + b) + 2\sqrt{ab} \ge a + b = (\sqrt{a+b})^2 $$ 이고, 마지막 부등식은 $a, b > 0$이므로 $2\sqrt{ab} > 0$이라는 데서 나온다. 따라서 $\sqrt{a+b} \le \sqrt a + \sqrt b$이다. $\blacksquare$ (S6주차 문제 13이 같은 명제를 선택법의 서식으로 증명한 것이다.) **복기.** 근호가 든 등식$\cdot$부등식의 참$\cdot$거짓을 판정하는 표준 수단은 **양변을 제곱해 비교하는 것**이다. 두 변이 음이 아닐 때만 대소가 보존되므로, 제곱하기 전에 그 조건을 확인하는 줄이 필요하다. 이 절차는 문제 16에서 절댓값 등식에 그대로 이식된다. **검산.** $a = 9$, $b = 16$에서 좌변 $\sqrt{25} = 5$, 우변 $3 + 4 = 7$이므로 $5 \le 7$ ✓. 등호는 $\sqrt{ab} = 0$일 때만 성립하므로 양의 실수 무대에서는 언제나 강한 부등호다. ### 문제 11 **접근.** 정찰은 두 번 통과하고 세 번째에서 뒤집힌다. 수리의 방향을 찾으려면 무너진 자리의 공통점을 본다 — 지수 $n$이 $1$보다 큰 홀수 인수를 가지면 $2^n + 1$이 인수분해 된다. 그 인수분해를 주는 항등식이 수리의 근거이며, 그 결과 얻는 것은 필요조건일 뿐 충분조건이 아니라는 점까지 밝혀야 답안이 완결된다. **풀이.** 정찰: $n = 1$에서 $3$(소수), $n = 2$에서 $5$(소수), $n = 3$에서 $9 = 3^2$. 위반이 나왔으므로 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$2^{n_0} + 1$이 소수가 아닌 자연수 $n_0$가 존재한다"를 증명한다. $n_0 = 3$으로 두자. 자격 — $3$은 자연수이다. 사건 — $2^3 + 1 = 9 = 3 \cdot 3$ 이고 $3 > 1$이므로 $9$는 $1$보다 큰 두 정수의 곱, 곧 소수가 아니다. 따라서 명제는 거짓이다. $\blacksquare$ 수리 (가정 강화, 필요조건): "$2^n + 1$이 소수이면 $n$은 $2$의 거듭제곱이다." 증명 (대우) — $n$이 $2$의 거듭제곱이 아니라 하자. 그러면 $n$은 $1$보다 큰 홀수 인수 $e$를 가지므로 $n = de$로 쓸 수 있고 $d \ge 1$이다. $x = 2^d$로 두면 $e$가 홀수이므로 $$ x^e + 1 = (x + 1)\left(x^{e-1} - x^{e-2} + \cdots - x + 1\right) $$ 이 성립한다. 곧 $2^d + 1$이 $2^n + 1$을 나눈다. 그런데 $2^d + 1 \ge 3 > 1$이고, $e \ge 3$이므로 $2^n + 1 = 2^{de} + 1 > 2^d + 1$이다. 따라서 $2^n + 1$은 $1$보다 큰 두 정수의 곱이므로 소수가 아니다. 대우가 증명되었으므로 원 명제도 참이다. $\blacksquare$ **이 수리가 충분조건이 아니라는 점.** $n = 2^k$로 좁혀도 명제는 참이 되지 않는다. $k = 5$에서 $F_5 = 2^{32} + 1 = 641 \cdot 6700417$이 합성수이기 때문이다 (S18주차 문제 18). 곧 "$n$이 $2$의 거듭제곱"은 필요조건일 뿐이며, 자격을 그렇게 좁힌 명제 "모든 $k$에 대해 $2^{2^k} + 1$은 소수이다"는 다시 거짓이다. **복기.** 수리를 한 번 했다고 끝나는 것이 아니다. 좁힌 명제도 걸음 ①②③을 다시 받아야 하고(§1.6 확인 8), 이 문항에서는 그 재판정에서 또 반례가 나왔다. **필요조건을 찾는 것과 참인 명제를 만드는 것은 다른 일이다.** **검산.** $n = 6 = 2 \cdot 3$에서 $d = 2$, $e = 3$이므로 $2^2 + 1 = 5$가 $2^6 + 1 = 65$를 나눈다: $65 = 5 \cdot 13$ ✓. $n = 4 = 2^2$에서 $2^4 + 1 = 17$은 소수이므로 필요조건이 막지 않는다 ✓. ### 문제 12 **접근.** 가정 "$a \mid (b+c)$"를 만족시키기는 쉽다 — $b + c$를 $a$의 배수로 만들면 되고, 그러면서 $b$와 $c$ 각각은 $a$의 배수가 아니도록 반으로 쪼개면 결론이 깨진다. 결론이 $\lor$이므로 **두 갈래를 모두** 위반시켜야 사건 검증이 완결된다는 점이 이 문항의 채점 포인트다. **풀이.** 정찰: $a = 2$, $b = 2$, $c = 4$에서 가정과 결론이 모두 성립한다. 가장 작은 $a$부터 쪼개 본다 — $a = 2$, $b = c = 1$에서 $b + c = 2$이므로 가정은 성립하고, $2 \nmid 1$이므로 두 갈래가 모두 거짓이다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$a \mid (b+c)$이면서 $a \nmid b$이고 $a \nmid c$인 정수 $a, b, c$가 존재한다"를 증명한다. $a = 2$, $b = 1$, $c = 1$로 두자. 자격 — 셋 다 정수이고 $b + c = 2 = 2 \cdot 1$이므로 $2 \mid (b+c)$이다(가정 성립). 사건 — $2k = 1$인 정수 $k$는 없으므로 $2 \nmid 1$이며, $b$와 $c$가 모두 $1$이므로 "$a \mid b$ 또는 $a \mid c$"의 두 갈래가 모두 거짓이다. 따라서 명제는 거짓이다. $\blacksquare$ 수리: 결론을 약화할 자리가 없다 — 이미 $\lor$이므로 더 낮추면 주장이 사라진다. 가정 강화 쪽에서는 "$a$가 소수"라는 조건을 붙여도 반례가 그대로 살아 있다($a = 2$가 소수다). 성립하는 방향은 반대 방향의 정리다: $a \mid b$이고 $a \mid c$이면 $a \mid (b+c)$ 이며, 이것은 $b = ak$, $c = al$에서 $b + c = a(k+l)$로 한 줄에 증명된다. **복기.** 나눗셈은 합에 대해 한 방향으로만 작동한다 — 각 항을 나누면 합을 나누지만, 합을 나눈다고 각 항을 나누지는 않는다. 곱에서도 같은 비대칭이 있으며(C7주차 예제 2.1의 명제 $C$), 그쪽은 $a$가 소수일 때 유클리드 보조정리로 회복된다. 합 쪽에서는 소수성이 회복시켜 주지 못한다는 것이 이 문항의 대조점이다. **검산.** $a = 3$, $b = 1$, $c = 2$도 반례다 — $3 \mid 3$이고 $3 \nmid 1$, $3 \nmid 2$ ✓. ### 문제 13 **접근.** 정찰이 참을 가리키면 증명으로 간다. $n^3 - n$을 인수분해하면 연속한 세 정수의 곱이 나오고, 그 곱이 $2$의 배수이면서 $3$의 배수임을 각각 보인다. 두 사실을 합쳐 $6$의 배수라고 말하려면 $2$와 $3$이 서로 다른 소수라는 점을 밝혀야 한다 — 이 연결 고리를 빠뜨리는 답안이 흔하다. **풀이.** 정찰: $n = 1$에서 $0$, $n = 2$에서 $6$, $n = 3$에서 $24$, $n = 4$에서 $60$, $n = 5$에서 $120$. 전부 $6$의 배수이고 급소(작은 수)도 통과했으므로 참으로 추측한다. 이 명제는 참이다. $n$을 자연수라 하면 $$ n^3 - n = n(n^2 - 1) = (n-1)n(n+1) $$ 이므로 이 값은 연속한 세 정수의 곱이다. **$2$의 배수임.** $n-1$과 $n$은 연속한 두 정수이므로 1권 1주차 문제 16에 의해 그 곱은 짝수다. 짝수에 정수를 곱해도 짝수이므로 $(n-1)n(n+1)$은 $2$의 배수다. **$3$의 배수임.** $n$을 $3$으로 나눈 나머지로 경우를 나눈다. $n = 3q$이면 $n$이 $3$의 배수다. $n = 3q + 1$이면 $n - 1 = 3q$가 $3$의 배수다. $n = 3q + 2$이면 $n + 1 = 3q + 3 = 3(q+1)$이 $3$의 배수다. 세 경우가 전부이므로 세 인수 중 하나는 반드시 $3$의 배수이고, 따라서 곱도 $3$의 배수다. **합치기.** $(n-1)n(n+1) = 2s = 3t$인 정수 $s, t$가 존재한다. $3 \mid 2s$이고 $3$은 소수이므로 유클리드 보조정리에 의해 $3 \mid 2$ 또는 $3 \mid s$인데 앞은 거짓이므로 $3 \mid s$이다. 곧 $s = 3u$인 정수 $u$가 존재하고 $(n-1)n(n+1) = 6u$이다. 따라서 $n^3 - n$은 $6$의 배수이고 명제는 참이다. $\blacksquare$ **복기.** "$2$의 배수이고 $3$의 배수이면 $6$의 배수"는 자명해 보이지만 근거가 필요한 줄이다. 그 근거가 $\gcd(2,3) = 1$이고, 이 답안에서는 유클리드 보조정리가 그 일을 했다. 같은 자리에서 "$2$의 배수이고 $4$의 배수이면 $8$의 배수"라고 쓰면 거짓이다 ($4$는 두 조건을 다 만족하지만 $8$의 배수가 아니다) — 두 수가 서로소일 때만 통하는 줄이라는 점이 이식할 때 지켜야 할 조건이다. C6주차 문제 15는 같은 사실을 $n^3 \equiv n \pmod 6$이라는 합동의 언어로 진술한 것이다. **검산.** $n = 7$에서 $343 - 7 = 336 = 6 \cdot 56$ ✓. ### 문제 14 **접근.** 같은 무리수를 두 번 쓰는 것이 허용되므로, 제곱하면 근호가 사라지는 무리수를 고르면 반례가 한 줄로 끝난다. 수리 쪽에서는 "일반적인 조건을 붙일 수 없다"는 결론도 정당한 답이며, 그 근거로 곱이 유리수가 되는 예와 무리수가 되는 예를 각각 들어야 한다. **풀이.** 정찰: $\sqrt2 \cdot \sqrt3 = \sqrt6$은 무리수이고, $\sqrt2 \cdot \sqrt5 = \sqrt{10}$도 무리수다. 그러나 두 무리수가 같아도 되므로 $\sqrt2 \cdot \sqrt2$를 넣는다. 값은 $2$이고 이것은 유리수다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "곱이 무리수가 아닌 무리수쌍이 존재한다"를 증명한다. $a = b = \sqrt2$로 두자. 자격 — $\sqrt2$는 무리수이다(1권 21주차 예제 2.2). 사건 — $\sqrt2 \cdot \sqrt2 = (\sqrt2)^2 = 2$이고 $2 = 2/1$이므로 유리수이며, 따라서 무리수가 아니다. 그러한 무리수쌍이 존재하므로 명제는 거짓이다. $\blacksquare$ 수리: 무리수라는 조건만으로는 곱의 유리$\cdot$무리가 정해지지 않는다. 두 방향의 예가 모두 있기 때문이다 — $\sqrt2 \cdot \sqrt2 = 2$는 유리수이고, $\sqrt2 \cdot \sqrt3 = \sqrt6$은 무리수다(1권 21주차 문제 15). 따라서 가정을 "두 수가 무리수이다"로 유지한 채 결론을 정하는 수리는 불가능하다. 자격을 좁혀 보려는 시도도 곧바로 막힌다. "두 수가 서로 유리수 배가 아니다"라는 조건을 붙여도 $a = \sqrt2 + 1$, $b = \sqrt2 - 1$이 그 조건을 만족하는데 ($b/a = (\sqrt2 - 1)^2 = 3 - 2\sqrt2$는 무리수다) 곱은 $ab = (\sqrt2)^2 - 1^2 = 1$로 유리수다 — 이 조건으로 좁혀도 곱이 유리수인 쌍이 그대로 살아 있다. 곱을 무리수로 강제하려면 무리수라는 성질만으로는 부족하고 곱 자체에 대한 정보를 조건에 넣어야 하는데, 그것은 결론을 가정으로 옮겨 적는 일이라 수리가 되지 않는다(문제 19의 "자명한 재진술은 조건이 아니다"와 같은 처리다). **복기.** "무리수의 집합은 곱셈에 대해 닫혀 있지 않다"가 이 문항의 내용이다. 같은 검사를 덧셈에 하면 $\sqrt2 + (-\sqrt2) = 0$으로 역시 닫혀 있지 않다. **닫힘성은 근거 ②의 이름이지만 모든 집합이 갖는 성질은 아니며**, 새 집합을 만날 때마다 어느 연산에 닫혀 있는지 따로 확인해야 한다는 점이 이식 가능한 교훈이다. **검산.** 곱이 유리수가 되는 예를 하나 더 확인하면 $\sqrt2 \cdot \sqrt8 = \sqrt{16} = 4$ — 이것도 유리수다. 무리수 쪽 예로는 $\sqrt2 \cdot \sqrt3 = \sqrt6$이 그대로 쓰인다 (1권 21주차 문제 15). 두 방향의 예가 모두 쉽게 만들어진다는 사실 자체가 수리가 막히는 이유다. ### 문제 15 **접근.** 마흔 개를 손으로 다 계산할 필요는 없다. 정찰 기록에는 몇 개를 적고 나머지는 "$n \le 39$에서 소수임이 알려져 있다"로 처리한 뒤, 이 문항의 무게가 실린 곳인 $n = 40$의 구조 설명에 집중한다. 문제 8과 같은 다항식이지만 무대가 $n \ge 0$으로 넓어졌다는 점만 다르다. **풀이.** 정찰: $n = 0$에서 $41$, $n = 1$에서 $43$, $n = 2$에서 $47$, $n = 3$에서 $53$, $n = 4$에서 $61$, $n = 39$에서 $39 \cdot 40 + 41 = 1601$ — 전부 소수다. $n = 5$부터 $39$까지도 전부 소수인데, 마흔 개를 손으로 검산하는 것은 이 문항의 목적이 아니므로 **지금은 인정하고 쓴다**(1권 1주차 문제 18이 같은 사실을 같은 방식으로 인정했다). 그럼에도 상수항 $41$이 급소를 지목하므로 멈추지 않는다. 이 명제는 거짓이다. 곧 "$n_0^2 + n_0 + 41$이 소수가 아닌 정수 $n_0 \ge 0$이 존재한다"를 증명한다. $n_0 = 40$으로 두자. 자격 — $40$은 $0$ 이상의 정수이다. 사건 — $$ 40^2 + 40 + 41 = 40 \cdot 41 + 41 = 41(40+1) = 41^2 = 1681 $$ 이고 $41 > 1$이므로 $1681$은 소수가 아니다. 따라서 명제는 거짓이다. $\blacksquare$ **왜 하필 $40$인가.** $n^2 + n + 41 = n(n+1) + 41$이다. 뒤의 항이 이미 $41$의 배수이므로, 앞의 항 $n(n+1)$이 $41$의 배수이면 값 전체가 $41$의 배수가 된다. $41$이 소수이므로 유클리드 보조정리에 의해 $41 \mid n$ 또는 $41 \mid n+1$이어야 하고, $n \ge 0$에서 가장 작은 해는 $n + 1 = 41$, 곧 $n = 40$이다. 그리고 그때 값 $1681$은 $41$보다 크므로 $41$의 배수이면서 $41$ 자신이 아니고, 따라서 합성수다. 값이 $41$의 배수가 되는 것과 합성수가 되는 것은 다른 조건이며, 후자에는 "값이 $41$보다 크다"가 더 필요하다. **복기.** 마흔 번의 통과가 아무것도 보장하지 않는다는 것이 이 문항의 첫 교훈이고, 급소가 상수항에서 **계산된다**는 것이 둘째 교훈이다. 둘째 교훈이 이식 가능한 쪽이다 — $n^2 + n + c$ 꼴에서 $c$가 소수이면 $n = c - 1$과 $n = c$가 언제나 반례 후보다. 문제 18이 그 이식을 시험한다. **검산.** $n = 41$에서 $41 \cdot 42 + 41 = 41 \cdot 43 = 1763$ ✓ — 예측대로 합성수다. ### 문제 16 **접근.** 반례는 부호가 다른 두 수에서 나온다. 참이 되는 조건을 찾으려면 양변을 제곱해 비교한다 — 두 변 모두 음이 아니므로 제곱 비교가 등식을 보존하고, 차이가 한 항으로 압축된다. 그 항이 사라지는 조건이 곧 답이며, 그 조건이 필요이자 충분임을 확인해야 "최소한"이라고 말할 수 있다. **풀이.** 정찰: $x = 3$, $y = 5$에서 $8 = 8$ ✓. $x = -3$, $y = -5$에서 $\lvert -8 \rvert = 8 = 3 + 5$ ✓. 부호를 갈라 $x = 1$, $y = -1$을 넣으면 좌변은 $0$, 우변은 $2$다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$\lvert x_0 + y_0 \rvert \neq \lvert x_0 \rvert + \lvert y_0 \rvert$인 실수 $x_0, y_0$이 존재한다"를 증명한다. $x_0 = 1$, $y_0 = -1$로 두자. 자격 — 둘 다 실수이다. 사건 — 좌변은 $\lvert 1 + (-1) \rvert = \lvert 0 \rvert = 0$이고 우변은 $\lvert 1 \rvert + \lvert -1 \rvert = 1 + 1 = 2$이며 $0 \neq 2$이다. 따라서 명제는 거짓이다. $\blacksquare$ 수리 (가정 강화): "실수 $x, y$에 대해, $xy \ge 0$이면 $\lvert x + y \rvert = \lvert x \rvert + \lvert y \rvert$이다." 증명 — 두 변 모두 음이 아니므로 등식은 제곱의 등식과 동치다. 양변을 제곱하면 $$ \lvert x+y \rvert^2 = (x+y)^2 = x^2 + 2xy + y^2, \qquad (\lvert x \rvert + \lvert y \rvert)^2 = x^2 + 2\lvert xy \rvert + y^2 $$ 이므로 두 제곱이 같을 필요충분조건은 $xy = \lvert xy \rvert$이고, 이는 $xy \ge 0$과 같은 말이다. 가정이 $xy \ge 0$이므로 두 제곱이 같고, 따라서 두 변이 같다. $\blacksquare$ **이 조건이 최소한임.** 위 계산은 동치 관계이므로, $xy < 0$이면 두 제곱이 다르고 따라서 등식이 깨진다. 곧 $xy \ge 0$은 등식이 성립하는 값을 하나도 버리지 않고 깨지는 값을 하나도 남기지 않는다 — 더 좁힐 수도 더 넓힐 수도 없는 조건이다. **복기.** "필요충분조건을 찾으라"는 요구는 계산을 동치 변형으로만 이어 가라는 요구와 같다. 이 답안에서 제곱 비교가 동치였던 이유는 두 변이 음이 아니었기 때문이며, 그 확인 줄이 없으면 최소성 주장이 무너진다. 같은 절차가 문제 10에서 부등식 쪽으로 쓰였다 — 그쪽에서는 등호 조건이 $\sqrt{ab} = 0$이었다. **검산.** $x = 2$, $y = 0$에서 $xy = 0 \ge 0$이고 $\lvert 2 \rvert = 2 = 2 + 0$ ✓. $x = -2$, $y = 3$에서 $xy = -6 < 0$이고 좌변 $1$, 우변 $5$로 실제로 깨진다 ✓. ### 문제 17 **접근.** 정찰이 네 번 강하게 참을 가리키지만, 그것으로 확정할 수 없다는 점을 답안에 명시하는 것이 이 문항의 절반이다. 나머지 절반은 증명이며, $n = 2k+1$을 대입해 $n^2 - 1 = 4k(k+1)$까지 간 뒤 $k(k+1)$에서 $2$를 하나 더 꺼낸다. **풀이.** 정찰: $n = 1$에서 $0 = 8 \cdot 0$, $n = 3$에서 $8$, $n = 5$에서 $24$, $n = 7$에서 $48$, $n = -1$에서 $0$. 다섯 값 모두 $8$의 배수이고 음수 급소도 통과했다. 참으로 추측한다. 다만 다섯 번의 통과는 확정이 아니다 — 문제 15의 다항식은 마흔 번을 통과하고도 거짓이었다. 확정은 아래 증명이 한다. 이 명제는 참이다. $n$을 홀수라 하자. 정의에 의해 $n = 2k + 1$인 정수 $k$가 존재하고 $$ n^2 - 1 = (2k+1)^2 - 1 = 4k^2 + 4k = 4k(k+1) $$ 이다. $k$와 $k+1$은 연속한 두 정수이므로 1권 1주차 문제 16에 의해 그 곱은 짝수이고, 따라서 $k(k+1) = 2m$인 정수 $m$이 존재한다. 대입하면 $$ n^2 - 1 = 4 \cdot 2m = 8m $$ 이고 $m$은 정수이므로 $n^2 - 1$은 $8$의 배수다. 따라서 명제는 참이다. $\blacksquare$ (1권 1주차 문제 17이 같은 명제를 같은 경로로 증명한 것이다.) **복기.** 정찰이 강할수록 증명을 건너뛰고 싶어지는데, 정찰의 강도와 명제의 참$\cdot$거짓은 아무 관계가 없다. §1.5의 비대칭 표가 그 이유이고, 오일러 다항식 두 개가 그 증거다. 답안에 "정찰이 참을 시사하므로 참이다"라고 적으면 §1.3 삭제 실험 (가)와 같은 답안이 된다. 이식 가능한 계산 쪽 패턴은 **$4$까지 묶은 뒤 남은 인수에서 $2$를 더 꺼내는 것**이며, 그 $2$를 공급하는 것이 언제나 연속한 두 정수의 곱이다. **검산.** $n = 9$에서 $81 - 1 = 80 = 8 \cdot 10$ ✓. $n = -5$에서 $25 - 1 = 24 = 8 \cdot 3$ ✓ — 음의 홀수에서도 성립하므로 무대를 정수 전체로 잡은 것이 옳다. ### 문제 18 **접근.** 이 다항식은 문제 15의 다항식을 옮겨 놓은 것이다. 정체를 드러내려면 값이 가장 작아지는 자리를 중심으로 치환한다 — $-79/2$ 부근이므로 $m = n - 40$이 자연스럽다. 치환하면 문제 15의 다항식이 그대로 나오고, 반례의 위치도 함께 옮겨 온다. **풀이.** 정찰: 무대가 자연수이므로 $n = 1$부터 넣는다. $n = 1$에서 $1523$(소수), $n = 2$에서 $1447$(소수), $n = 40$에서 $1600 - 3160 + 1601 = 41$(소수), $n = 79$에서 $6241 - 6241 + 1601 = 1601$(소수). 여러 번 통과하지만 판정을 미룬다. $m = n - 40$으로 치환하면 $$ m^2 + m + 41 = (n-40)^2 + (n-40) + 41 = n^2 - 80n + 1600 + n - 40 + 41 = n^2 - 79n + 1601 $$ 이므로 이 다항식은 문제 15의 다항식과 같은 것이고, $n$과 $m$은 $40$만큼 어긋나 있다. 문제 15에서 반례가 $m = 40$이었으므로 여기서는 $n = 80$이다. 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$n_0^2 - 79n_0 + 1601$이 소수가 아닌 자연수 $n_0$가 존재한다"를 증명한다. $n_0 = 80$으로 두자. 자격 — $80$은 자연수이다. 사건 — $80^2 = 6400$이고 $79 \cdot 80 = 6320$이므로 $$ 80^2 - 79 \cdot 80 + 1601 = 6400 - 6320 + 1601 = 1681 = 41^2 $$ 이고 $41 > 1$이므로 $1681$은 소수가 아니다. 따라서 명제는 거짓이다. $\blacksquare$ **정찰이 몇 번 통과하는가.** $m^2 + m + 41$은 $m$과 $-1-m$에서 같은 값을 주므로 ($m^2 + m = (-1-m)^2 + (-1-m)$), $m = 0, \ldots, 39$에서 소수라는 사실이 $m = -40, \ldots, -1$에서도 소수임을 함께 준다. $m$이 $-40$부터 $39$까지 여든 개이므로 $n$으로는 $0$부터 $79$까지 여든 개에서 값이 소수다. 다만 이 명제의 무대는 자연수이므로 정찰이 실제로 밟는 것은 $n = 1$부터 $79$까지 일흔아홉 개이고, 일흔아홉 번의 통과 뒤 여든 번째 값 $n = 80$에서 무너진다. (§1.5의 표는 무대가 아니라 다항식 자체의 성질을 적은 것이므로 그쪽은 $n = 0$부터 여든 번으로 센다.) **복기.** 두 다항식이 겉모양은 전혀 달라도 치환 하나로 같아진다는 것이 이 문항의 내용이다. **정찰이 유난히 오래 통과하는 다항식을 만나면 치환으로 정체를 확인하는 것**이 이식 가능한 절차이고, 확인되고 나면 반례의 위치를 새로 찾을 필요 없이 옮겨 오면 된다. S18주차 문제 18의 페르마 수가 다섯 번의 통과로 같은 교훈을 주는 사례다. **검산.** $n = 81$에서 $6561 - 6399 + 1601 = 1763 = 41 \cdot 43$ ✓ — 문제 15의 $n = 41$에서 나온 값과 같다. ### 문제 19 **접근.** 반례는 가장 작은 값에서 나온다. 이 문항의 무게는 반례가 아니라 걸음 ④에 있다 — 참이 되는 $(a, b)$의 조건을 유한한 목록이나 간단한 부등식으로 적을 수 없다는 점을 확인하고, 그럼에도 성립하는 쌍이 무한히 많다는 사실을 함께 밝히는 것이 답안이다. **풀이.** 정찰: $a = 3$, $b = 4$에서 $9 + 16 = 25 = 5^2$이므로 $c = 5$가 존재한다. $a = 1$, $b = 1$에서 $1 + 1 = 2$이고 $c^2 = 2$인 정수 $c$는 없다($1^2 = 1 < 2 < 4 = 2^2$ 이므로 어떤 정수의 제곱도 $2$가 되지 않는다). 거짓으로 추측한다. 이 명제는 거짓이다. 곧 "$a_0^2 + b_0^2 = c^2$인 정수 $c$가 존재하지 않는 정수쌍 $(a_0, b_0)$이 존재한다"를 증명한다. $a_0 = b_0 = 1$로 두자. 자격 — 둘 다 정수이다. 사건 — $a_0^2 + b_0^2 = 2$이고, $c$가 정수이면 $\lvert c \rvert \le 1$일 때 $c^2 \le 1 < 2$이며 $\lvert c \rvert \ge 2$일 때 $c^2 \ge 4 > 2$이므로 $c^2 = 2$인 정수 $c$는 없다. 따라서 명제는 거짓이다. $\blacksquare$ 수리: 참이 되는 $(a, b)$의 조건은 "$a^2 + b^2$이 완전제곱수이다"인데, 이것은 원 명제를 말만 바꿔 적은 것이라 정보가 없다. 자격을 좁히는 실질적 조건을 찾으면 유클리드의 공식이 나온다 — 양의 정수 $s > t > 0$에 대해 $a = s^2 - t^2$, $b = 2st$로 두면 $$ a^2 + b^2 = (s^2 - t^2)^2 + (2st)^2 = s^4 - 2s^2t^2 + t^4 + 4s^2t^2 = (s^2 + t^2)^2 $$ 이므로 $c = s^2 + t^2$이 존재한다. 곧 그런 꼴의 $(a, b)$는 전부 참인 쌍이고, $s, t$를 바꿔 가며 무한히 많이 만들 수 있다($(s,t) = (2,1)$에서 $(3,4,5)$, $(s,t) = (3,2)$에서 $(5,12,13)$). 그러나 이 공식이 모든 참인 쌍을 덮는지, 그리고 공약수를 허용한 일반형까지 포함하는지는 이 시점의 도구로 판정되지 않는다 — 이 교재의 범위 밖인 정수론의 고전 주제(원시 피타고라스 삼중항의 분류)다. **복기.** 걸음 ④가 "닫힌 꼴의 조건을 찾지 못했다"로 끝나는 것도 정당한 결말이다. 그때 답안에 적을 것은 셋이다 — ① 자명한 재진술은 조건이 아니라는 점 ② 참인 쌍을 무한히 만드는 구성이 있다는 점 ③ 완전한 판정이 현재 도구의 범위 밖이라는 점. 훈련 3에서 만난 결말과 같은 종류이며, 수학의 실제 문제가 대개 이 모양이라는 점이 이번 주의 마지막 관찰이다. **검산.** $(s,t) = (4,1)$에서 $a = 15$, $b = 8$, $c = 17$이고 $225 + 64 = 289 = 17^2$ ✓. ### 문제 20 **접근.** (a)는 §1.5의 비대칭을 예제 두 개의 사실로 뒷받침하는 문항이고, (b)는 §1.6의 왕복을 예제 2.3의 두 명제로 설명하는 문항이다. 두 물음 모두 "예제에서 실제로 일어난 일"을 근거로 대야 하며, 일반론만 적으면 근거가 빈다. **풀이 (예시 답안).** **(a)** 예제 2.1에서 다섯 값의 정찰은 참 쪽을 가리켰고 그 방향에 따라 인수분해 증명을 썼으며, 예제 2.2에서 열 값의 정찰은 참 쪽을 가리켰으나 급소 하나를 더 넣자 방향이 뒤집혀 반례를 쓰게 되었다. 곧 정찰이 한 일은 두 예제 모두에서 "증명을 쓸 것인가 반례를 쓸 것인가"를 정한 것이지, 참$\cdot$거짓을 확정한 것이 아니다. 정찰이 없으면 그 결정을 근거 없이 하게 되므로 필수이고, 정찰만으로 끝내면 예제 2.2가 "참"으로 선언되므로 불충분하다. **(b)** 예제 2.3에서 반례 $(-2, 2)$는 명제 A를 지운 것이 아니라, 명제가 성립하지 않는 영역이 정확히 음수 쪽임을 알려 주었고 그 영역을 잘라 낸 명제 B가 참으로 증명되었다. 반례가 없었다면 명제 B가 성립하는 정확한 범위도 알 수 없었을 것이다. 증명 시도가 막히면 그 막힌 자리에서 반례를 찾고, 반례가 명제의 범위를 좁히면 좁힌 명제를 다시 증명하는 왕복이 한 탐구의 두 방향이며, 예제 2.3의 명제 A와 B가 그 왕복을 한 바퀴 돈 기록이다. **복기.** 두 물음의 답이 같은 곳에서 나온다. 정찰이 방향만 정하는 이유와 반례가 명제를 다듬는 이유는 모두 "$\forall$ 명제는 값 하나로 무너지고 값 전부로만 선다"는 비대칭의 결과다. 이 한 문장이 이번 주 전체의 요약이다. --- **다음 주 예고 (C11주차):** Chartrand 9장 — 동치관계. C2주차에서 씨앗으로 남겨 둔 **분할**이 여기서 정리로 자란다. 관계의 세 성질(반사$\cdot$대칭$\cdot$추이)을 판정하고, 세 성질을 모두 갖춘 관계를 동치관계라 부르며, 동치류 $[a]$를 다룬다. 그리고 이 책의 핵심 정리 하나 — 동치관계는 집합을 동치류로 분할하고, 모든 분할은 동치관계를 낳는다 — 를 증명한다. 1권 36~38주차의 관계와 합동 $\mathbb{Z}_n$이 정식 무대에 오른다. 원서 9장을 통독하고 온다.