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

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

예제 — 판정부터 함께 만들기#

완성된 답안을 먼저 보이지 않는다. 참\(\cdot\)거짓이 표시되지 않은 상태에서 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 참인 명제: 정찰에서 증명까지#

명제 (P-or-D). 모든 정수 \(n\)에 대해, \(n^2 + n\)은 짝수이다.

설계 — 쓰기 전에 정하는 두 가지. 여느 주와 달리 도착점이 아직 비어 있다. 참\(\cdot\)거짓을 정하는 것이 설계의 첫 일이다.

말

수식 번역

가정 (주어진 것)

\(n\)은 정수이다

무대 조건뿐이고 풀어 쓸 정의가 없다

도착점 (만들 것)

아직 정해지지 않았다

\(\underline{\quad(?)\quad}\)

확인 10. 도착점 칸을 채워 보자. 이 명제의 도착점은 두 갈래이고, 어느 쪽인지는 걸음 ①이 정한다. 두 갈래를 각각 수식으로 적어 보자.

답

참 쪽: 모든 정수 \(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\)

짝수

확인 11. 표의 (1)~(4)를 채우고, 이 정찰이 §1.4의 급소 중 어느 것을 덮었고 어느 것을 덮지 않았는지 적어 보자.

답

(1) \(0\) (2) 짝수 (3) \(0\) (4) 짝수. (\((-1)^2 + (-1) = 1 - 1 = 0\)이다.)

덮은 급소: \(0\), 음수, 아주 작은 수. 덮지 않은 급소: \(0\)과 \(1\) 사이의 분수, 빈 집합.

다만 무대가 정수이므로 분수와 집합 관련 급소는 이 명제에 적용되지 않고, 소수 \(2\)는

\(n = 2\)에서 이미 대입되었다. 무대가 급소 목록의 어느 줄을 살리는지 먼저 보는 것이

정찰의 순서를 정하는 방법이다.

걸음 ② 추측. 다섯 값 전부 짝수이고 급소도 통과했으므로 참으로 추측한다. 이 시점의 라벨은 추측이며, 아래 걸음 ③이 끝나기 전까지 아무것도 확정되지 않았다.

걸음 ③ 결단 — 어느 기법인가. 참 추측이므로 증명을 쓴다. 기법은 C9주차 지도의 2단계가 정한다.

확인 12. 이 명제의 결론 “\(n^2 + n\)은 짝수이다”의 겉모양은 무엇이고, 지도의 어느 갈래로 가는가. 그리고 곧바로 정의를 풀면 무엇이 막히는가.

답

겉모양은 \(\forall\) 안에 숨은 \(\exists\)다 — “짝수”의 정의가 “\(n^2 + n = 2k\)인 정수 \(k\)가 존재한다”

이므로, 지도의 2단계는 직접 증명과 구성을 가리킨다.

곧바로 정의를 풀면 막힌다. 가정 쪽에는 “\(n\)은 정수”뿐이라 풀 정의가 없고,

목표 쪽의 \(k\)를 만들려면 \(n^2 + n\)을 \(2 \times (\text{정수})\)로 묶어야 하는데

\(n\)의 짝\(\cdot\)홀을 모르므로 \(n\)을 등식으로 펼칠 수 없다. 재료가 하나 더 필요하다.

확인 13. \(n^2 + n\)을 인수분해해 보자. 그 결과가 이미 증명된 어느 명제와 맞물리는가.

답

\(n^2 + n = n(n+1)\) — 연속한 두 정수의 곱이다.

이 꼴은 “연속한 두 정수의 곱은 짝수이다”(1권 1주차 문제 16, 근거 ④)와 정확히

맞물린다. 그 명제가 경우 나누기로 이미 증명되어 있으므로, 이번 답안은 경우

나누기를 다시 하지 않고 부품으로 인용한다.

인수분해 한 줄이 막힘을 푼 이유는 \(n\)의 짝\(\cdot\)홀을 몰라도 되는 꼴로 바꿨기 때문이다 —

연속한 두 정수 중 하나는 반드시 짝수이므로 어느 쪽인지 알 필요가 없다.

확인 14. 이제 증인 \(k\)를 만들어 보자. \(n(n+1)\)이 짝수이면 정의에 의해 무엇을 받을 수 있고, 그것이 목표의 \(k\)와 어떻게 연결되는가.

답

정의에 의해 \(n(n+1) = 2m\)인 정수 \(m\)을 받는다. 그 \(m\)이 곧 목표의 증인이다 —

\(n^2 + n = n(n+1) = 2m\)이고 \(m\)은 정수이므로 짝수의 정의가 그대로 충족된다.

받아 온 정수를 그대로 증인으로 내놓는 것이 구성법의 가장 짧은 경우다(S5주차 문제 3).

확인 15. 마지막 문장을 완성해 보자: “따라서 모든 정수 \(n\)에 대해 \(n^2 + n\)은 \(\underline{\qquad}\)이므로, 이 명제는 \(\underline{\quad}\)이다.”

답

“따라서 모든 정수 \(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에서 서식 연습의 재료였다. 그때는 “이 주장은 거짓이다”가 미리 주어져 있었고, 이번의 과제는 그 표시 없이 반례에 도달하는 것이다.)

확인 16. 정찰을 \(n = 1\)부터 \(10\)까지 마쳤고 값은 \(11, 13, 17, 23, 31, 41, 53, 67, 83, 101\)로 전부 소수였다. 여기서 걸음 ②를 어느 쪽으로 정하겠는가. 그리고 그 결정을 내리기 전에 아직 넣지 않은 급소가 있는지 점검해 보자.

답

아직 정하지 않는다. §1.4 목록에서 상수항이 지목하는 값이 남아 있고, 이 명제는

상수항이 \(11\)이므로 그 급소가 살아 있다. 값이 \(11\)의 배수가 되는 \(n\)을 먼저 넣어야

정찰이 끝난다.

열 번의 통과만으로 참을 추측하면 §1.3의 삭제 실험 (가)와 같은 답안이 된다.

정찰을 언제 멈추는가에 대한 규칙은 이것이다 — **적용되는 급소를 전부 넣기 전에는

멈추지 않는다.**

확인 17. \(n^2 - n + 11\)을 \(n(n-1) + 11\)로 다시 적어 보자. 값이 \(11\)의 배수가 되려면 \(n\)이 어떤 수여야 하는가. 그중 반례가 되는 가장 작은 값은 무엇인가.

답

\(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\)이다.

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

확인 18. 명제 A를 정찰해 보자. 이 명제는 조건문이므로 정찰에 넣는 값이 가정을 만족해야 한다. 급소 목록에서 어느 줄을 먼저 쓰겠는가. 그리고 명제 A가 거짓이면 명제 B를 어떻게 만들겠는가.

답

급소는 음수다. 나눗셈은 부호를 지우지 않으므로 \(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}\)

확인 19. 표의 (1)(2)(3)을 채우고, 걸음 ④가 “해당 없음”이 되는 조건을 한 줄로 적어 보자.

답

(1) 음수 급소 — \(a = -2\), \(b = 2\).

(2) 반례 \(n_0 = 11\)과 두 검증(무대 소속, \(121 = 11 \cdot 11\)).

(3) 무대를 양의 정수로 좁혀 명제 B를 만들고 다시 정찰\(\cdot\)증명했다.

걸음 ④가 해당 없음이 되는 조건: **걸음 ②의 추측이 참이었고 걸음 ③이 증명으로

끝난 경우.** 수리는 거짓으로 확정된 명제에만 있는 걸음이다.

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

백지 암기 대상

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\) (거짓이면) 수리를 수행한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. P-or-D 답안에는 채점 항목이 넷이다.

① 판정 선언이 답안 어딘가에 한 문장으로 적혀 있는가. 판정 없는 계산은 지시문에 답하지 않은 것이다.

② 판정이 참이면 완전한 증명이 있는가. 정찰 기록은 증명이 아니므로 점수가 되지 않는다.

③ 판정이 거짓이면 반례에 두 검증(자격\(\cdot\)사건)이 붙어 있는가. 조건문 명제의 자격은 “가정의 성립”이다.

④ 수리를 요구한 문항에서, 수리한 명제에 다시 판정과 증명이 붙어 있는가.

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

기본 ●○○#

1. [백지] P-or-D 흐름 4단계, 반례 급소 목록, 수리의 두 방향(가정 강화\(\cdot\)결론 약화)을 쓰시오.

힌트

네 걸음의 이름만 외우면 절반이다. 걸음마다 “이것을 빼면 무엇이 무너지는가”를 함께

적어 두면 일부를 잊었을 때 나머지에서 복구할 수 있다. §1.3의 해부 표가 그 복구의

재료이고, 급소 목록은 §1.4의 왼쪽 열이다.

2. 각 명제를 정찰만 하고 참\(\cdot\)거짓을 추측하시오 (증명과 반례는 아직 적지 않는다). (a) 모든 소수는 홀수이다. (b) 두 홀수의 합은 짝수이다. (c) 자연수 \(n\)에 대해 \(n^2 > n\)이다. (d) 모든 정수는 두 제곱수의 합이다.

힌트

네 문항 모두 급소 목록의 첫 줄들로 갈린다. (a)는 소수 \(2\), (c)는 아주 작은 수,

(d)는 작은 수를 표로 만들어 전수 대입한다 — \(0, 1, 2, 3\)에서 두 제곱수의 합으로

만들 수 있는 값을 모두 적어 보면 빠진 수가 보인다. (b)는 급소를 넣어도 흔들리지

않는 유일한 문항이다.

3. 예제 2.2를 백지 재현하시오 (반례 \(n = 11\)까지 도달하는 과정을 포함한다).

힌트

반례 값만 적으면 절반이다. 열 번의 정찰을 통과한 뒤 왜 멈추지 않았는지와

\(n(n-1) + 11\)이라는 변형이 급소를 어떻게 계산해 냈는지가 이 문항의 채점 대상이다.

4. §3의 빈칸 사다리 훈련 1~3을 백지에서 완성하시오.

힌트

훈련 1과 2는 급소를 어디에 넣는지가 전부다. 훈련 3은 정찰이 네 번 통과한 뒤

다섯째 소수에서 뒤집히는 사례이며, 수리 칸이 막히는 것이 정상이다 — 막혔다는

사실 자체를 답안에 적는 것이 §2 예제 2.2에서 배운 처리다.

5. 예제 2.3의 명제 A(반례)와 B(증명)를 백지 재현하시오.

힌트

두 명제의 차이는 무대 한 줄이다. 증명 B에서 \(kl = 1\) 다음 줄이 명제 A와 갈리는

자리이므로, 그 줄에서 “양의 정수”라는 조건이 어떻게 소비되는지를 밝혀 적는다.

6. “모든 실수 \(x\)에 대해 \(\sqrt{x^2} = x\)”를 P-or-D하시오 (반례를 제시하고, 이어 가정 강화와 결론 약화의 두 방향으로 각각 수리하시오).

힌트

좌변은 제곱을 거치므로 부호가 지워지고 우변은 부호를 남긴다. 두 변이 부호에

다르게 반응하므로 급소는 음수다. 수리에서 결론 약화 쪽은 “부호를 지우는 연산”을

우변에도 붙이는 것이다.

표준 ●●○#

7. P-or-D: “정수 \(a, b\)에 대해, \(ab\)가 짝수이면 \(a\)와 \(b\)가 모두 짝수이다.” 거짓이면 반례를 제시하고, 결론을 고쳐 참이 되는 명제를 만들어 증명하시오.

힌트

조건문이므로 반례는 가정을 만족해야 한다 — \(ab\)가 짝수인 쌍 중에서 찾는다.

수리는 결론의 접속사 한 글자를 바꾸는 것으로 끝나고, 그 새 명제의 증명은 대우로

쓰는 편이 짧다(두 홀수의 곱은 홀수).

8. P-or-D: “모든 자연수 \(n\)에 대해 \(n^2 + n + 41\)은 소수이다.” (1권 1주차 문제 18의 재방문 — 이번에는 참\(\cdot\)거짓이 표시되지 않았다.)

힌트

예제 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\)이 짝수이다”로 약화한 명제를 증명하시오.

힌트

조건문이므로 반례는 가정 “\(n^2\)이 \(4\)의 배수”를 만족하는 \(n\) 중에서 찾는다.

\(n\)이 \(2\)의 인수를 하나만 가지면 그 가정은 채워지고 결론은 깨진다.

수리한 명제는 대우로 증명하는 편이 짧다 — 홀수의 제곱이 홀수임을 보이면 된다.

10. P-or-D: “모든 양의 실수 \(a, b\)에 대해 \(\sqrt{a + b} = \sqrt a + \sqrt b\)이다.” 거짓이면 등호를 부등호로 바꾼 올바른 명제를 적으시오 (S6주차 문제 13).

힌트

급소를 찾을 필요가 거의 없다 — 가장 평범한 값 \(a = b = 1\)에서 이미 두 변이

갈린다. 수리의 방향을 정하려면 두 변을 제곱해 비교한다: \((\sqrt a + \sqrt b)^2\)은

\(a + b\)보다 항상 큰가, 작은가.

11. P-or-D: “모든 자연수 \(n\)에 대해 \(2^n + 1\)은 소수이다.” 반례를 제시하고, \(2^n + 1\)이 소수가 되기 위한 필요조건을 찾아 수리를 시도하시오 (S18주차 문제 18의 페르마 수).

힌트

정찰은 \(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\)이다.”

힌트

가정을 만족시키기가 쉽다 — \(b + c\)가 \(a\)의 배수가 되도록 \(b\)와 \(c\)를 반으로 쪼개면

된다. 그러면서 각각은 \(a\)의 배수가 아니도록 만든다. 가장 작은 \(a\)부터 시도한다.

13. P-or-D: “모든 자연수 \(n\)에 대해 \(n^3 - n\)은 6의 배수이다.” (C6주차 문제 15와 같은 사실을 다른 언어로 진술한 것이다.)

힌트

정찰이 참을 가리키면 증명으로 간다. \(n^3 - n\)을 인수분해하면 연속한 세 정수의

곱이 나오고, 그중 하나는 \(2\)의 배수, 하나는 \(3\)의 배수다. 두 사실을 합쳐 \(6\)의

배수라고 말하려면 \(2\)와 \(3\)이 서로소라는 점을 밝혀야 한다.

14. P-or-D: “두 무리수의 곱은 무리수이다.” 거짓이면 반례를 제시하고, 무리수끼리의 곱이 유리수도 무리수도 될 수 있음을 예로 보이시오.

힌트

같은 무리수를 두 번 쓰는 것이 허용된다. 제곱하면 근호가 사라지는 무리수를

고르면 반례가 한 줄로 끝난다. 수리 쪽에서는 “일반적인 조건을 붙일 수 없다”는

결론도 정당한 답이며, 그 근거로 두 방향의 예를 각각 든다.

도전 ●●●#

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\)의 구조로 설명하시오.

힌트

마흔 개를 손으로 다 계산할 필요는 없다 — 몇 개를 확인하고 “\(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하고, 참이 되는 정확한 조건을 찾으시오. 그 조건이 최소한임을 확인하시오.

힌트

반례는 부호가 다른 두 수에서 나온다. 참이 되는 조건을 찾으려면 양변을 제곱해

비교한다 — \((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).

힌트

정찰: \(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\)에서 반례를 찾으시오.

힌트

이 다항식은 문제 15의 다항식을 옮겨 놓은 것이다. \(m = n - 40\)으로 치환해

전개해 보면 정체가 드러나고, 그러면 반례의 위치도 문제 15에서 그대로 옮겨 온다.

19. (조건 탐색 종합) P-or-D: “정수 \(a, b\)에 대해 \(a^2 + b^2 = c^2\)인 정수 \(c\)가 존재한다.” 반례를 제시하고, 참이 되는 \((a, b)\)의 조건을 탐색하시오.

힌트

반례는 가장 작은 값에서 나온다. 수리 쪽에서는 자격을 좁히는 조건이 유한한 목록으로

적히지 않는다 — 그럴 때 답안에 적을 것은 “조건이 닫힌 꼴로 알려져 있는가”에 대한

판정이며, \((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장을 통독하고 온다.