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

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

예제 — 다섯 무대를 한 절차로#

완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 나눗셈: 선형결합 성질#

Result. 정수 \(a, b, c\)에 대해, \(a \mid b\)이고 \(a \mid c\)이면 임의의 정수 \(x, y\)에 대해 \(a \mid (bx + cy)\).

설계 — 쓰기 전에 정하는 두 가지. 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 정한다. 둘 다 정의 6.1로 번역해서 얻는다 — 걸음 ②와 ③이다.

말

수식 번역

가정 (출발점)

\(a \mid b\), \(a \mid c\)

\(b = ak\), \(c = al\)인 정수 \(k, l\)이 존재

목표 (도착점)

\(a \mid (bx + cy)\)

\(bx + cy = \underline{\quad(?)\quad}\) 꼴을 만든다

확인 11. 목표 칸의 빈칸을 채워 보자. “\(a \mid (bx+cy)\)를 보인다”를 정의 6.1로 번역하면 무엇을 만들어야 하는가.

답

\(bx + cy = a \times (\text{정수})\) 꼴. 정의 6.1의 “존재한다”가 목표 쪽에 있으므로,

그런 정수를 직접 구성해 제시하는 것이 이 증명의 일이다. 출발점(등식 두 개)과

도착점(만들 꼴)이 정해졌으니 그 사이는 걸음 ④의 계산이다.

1단계 — 대상을 문자로 잡고 가정을 쓴다. 명제는 “모든 정수 \(a, b, c, x, y\)”에 대한 주장이므로 특정 숫자가 아니라 문자를 올린다.

확인 12. 첫 문장을 완성해 보자: “정수 \(a, b, c\)에 대해 \(\underline{\qquad}\)이고 \(\underline{\qquad}\)라 하자. 또 \(x, y\)를 \(\underline{\qquad}\)라 하자.”

답

“정수 \(a, b, c\)에 대해 \(a \mid b\)이고 \(a \mid c\)라 하자. 또 \(x, y\)를 임의의 정수라

하자.” \(x, y\)에는 가정이 붙어 있지 않으므로 풀 정의가 없다 — 정수라는 자격만

선언하고 그대로 둔다.

2단계 — 정의를 풀어 쓴다(걸음 ②). “나눈다”는 아직 말이다. 등식으로 바꾼다.

확인 13. 둘째 문장을 완성해 보자: “정의 6.1에 의해 \(b = \underline{\quad}\)인 정수 \(k\)가 존재하고, \(c = \underline{\quad}\)인 정수 \(\underline{\quad}\)이 존재한다.” 왜 문자를 둘 쓰는가.

답

\(b = ak\), \(c = al\)인 정수 \(l\). 문자를 같은 \(k\)로 쓰면 \(b = c\)라고 몰래 가정한

셈이 된다 — 약수는 같은 \(a\)지만 몫은 각각이므로 서로 다른 문자를 쓴다

(1권 2주차 예제 2.2와 같은 자리다).

3단계 — 도착점의 꼴로 조립한다(걸음 ④). 재료 \(ak\), \(al\)을 목표 꼴 \(a \times (\text{정수})\)에 맞춰 조립한다.

확인 14. 셋째 문장을 완성해 보자: “그러면 \(bx + cy = \underline{\qquad} = a(\underline{\qquad})\)이다.”

답

\(bx + cy = (ak)x + (al)y = akx + aly = a(kx + ly)\). 분배법칙으로 \(a\)를 묶었다 —

근거 ③. 목표 꼴이 “\(a \times\) 무엇”이므로 묶을 대상이 처음부터 정해져 있었다.

4단계 — 괄호 안의 자격을 확인한다(걸음 ⑤ 전반). \(a(kx+ly)\)가 정의 6.1의 꼴이려면 괄호 안이 정수여야 한다. 이 확인이 빠지면 §1.3의 삭제 실험이 재연된다.

확인 15. 넷째 문장을 완성해 보자: “\(k, l, x, y\)가 전부 정수이고 \(\underline{\qquad}\)이므로 \(kx + ly\)는 정수이다.”

답

“정수의 곱과 합은 정수이므로” — 근거 ②. 곱 두 번과 합 한 번이 쓰였다.

5단계 — 결론을 선언한다(걸음 ⑤ 후반). 도착점 꼴이 완성되었음을 정의를 인용해 선언한다.

확인 16. 마지막 문장을 완성해 보자: “따라서 \(bx + cy = a(kx+ly)\)는 \(\underline{\qquad}\)의 꼴을 만족하므로 \(\underline{\qquad}\)이다. \(\blacksquare\)”

답

“따라서 \(bx + cy = a(kx+ly)\)는 정의 6.1의 꼴을 만족하므로 \(a \mid (bx + cy)\)이다.

\(\blacksquare\)” 이 다섯 문장이 완성된 증명이고, (D2)가 증명되었으므로 이제부터

근거 ④로 인용할 수 있다.

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

증명의 한 줄

왜 이 줄을 쓰는가?

정수 \(a, b, c\)에 대해 \(a \mid b\)이고 \(a \mid c\)라 하자. 또 \(x, y\)를 임의의 정수라 하자.

걸음 ① — 무대는 나눗셈이고 대상을 문자로 올린다. \(x, y\)에는 가정이 없으므로 자격만 선언한다.

정의 6.1에 의해 \(b = ak\)인 정수 \(k\)가 존재하고 \(c = al\)인 정수 \(l\)이 존재한다.

걸음 ② 전진면 — 이름을 등식으로 바꾼다(근거 ①). 몫이 각각이므로 문자를 다르게 쓴다.

목표는 \(bx + cy\)를 “\(a \times (\text{정수})\)” 꼴로 만드는 것이다.

걸음 ③ 후진면 — 도착점을 먼저 적어 두어야 어느 변형이 진전인지 판정된다(§1.4의 걸음 삭제 실험).

그러면 \(bx + cy = akx + aly = a(kx + ly)\)이다.

걸음 ④ — 대입하고 분배법칙으로 \(a\)를 묶는다(근거 ③). 묶을 대상은 도착점이 지정했다.

\(kx + ly\)는 정수이므로(정수의 곱과 합은 정수), 정의 6.1에 의해 \(a \mid (bx + cy)\)이다. \(\blacksquare\)

걸음 ⑤ — 자격 확인(근거 ②) 후 정의를 인용해 닫는다.

[주의] 자주 하는 실수: 도착점 없이 전개하기. \(bx + cy\)에 \(b = ak\), \(c = al\)을 대입한 뒤 \(akx + aly\)에서 멈추는 경우가 많다. 식은 옳지만 정의 6.1의 꼴이 아니다. 걸음 ③을 적어 두지 않으면 “\(a\)로 묶어야 한다”는 판단이 나오지 않는다.

이 성질이 뒤에서 쓰이는 자리. \(x = y = 1\)이면 (D2)는 “\(a \mid (b+c)\)”가 되고 \(x = 1, y = -1\)이면 “\(a \mid (b-c)\)”가 된다. 문제 16에서 “\(9 \mid n\)과 \(9 \mid \sum d_i\)가 서로를 결정한다”를 보일 때 쓰는 것이 바로 이 두 특수 경우다. 선형결합 성질은 C15주차 유클리드 호제법의 씨앗이기도 하다.

예제 2.2 — 합동: 곱 보존 (C5)#

Result (곱 보존). \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이면 \(ac \equiv bd \pmod n\).

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

확인 17. 번역표를 채워 보자.

가정: \(a \equiv b\), \(c \equiv d \pmod n\) \(\to\) 정의 6.2와 6.1을 연이어 풀면 \(a - b = \underline{\quad}\), \(c - d = \underline{\quad}\)인 정수 \(s, t\)가 존재.

목표: \(ac \equiv bd \pmod n\) \(\to\) \(\underline{\qquad}\)가 “\(n \times (\text{정수})\)” 꼴임을 보인다.

답

가정: \(a - b = ns\), \(c - d = nt\). 합동은 정의가 두 겹이므로 정의 6.2로 \(n \mid (a-b)\)를

얻고 정의 6.1로 등식까지 내려가야 계산이 시작된다.

목표: \(ac - bd\)가 “\(n \times (\text{정수})\)” 꼴임을 보인다. 도착점이 \(ac - bd\)라는

차라는 것이 이 예제의 전부다 — 손에 있는 재료는 \(a - b\)와 \(c - d\)이므로,

걸음 ④의 과제는 “\(ac - bd\)를 이 두 차로 표현하는 것”이 된다.

확인 18. \(ac - bd\)를 \(a - b\)와 \(c - d\)로 표현해 보자. 두 재료를 동시에 쓰려면 항 하나를 더하고 빼는 조작이 필요하다. 무엇을 더하고 빼는가.

답

\(bc\)를 더하고 뺀다.

\[ ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) \]

앞 묶음에서 \(a - b\)가, 뒤 묶음에서 \(c - d\)가 각각 나온다. \(bc\) 대신 \(ad\)를 더하고

빼도 된다 — \(ac - ad + ad - bd = a(c-d) + d(a-b)\). 어느 쪽이든 두 재료를 한 번씩

쓰는 것이 목적이고, 그 목적은 걸음 ③이 도착점을 \(ac - bd\)로 못 박아 두었기에 나온다.

증명의 한 줄

왜 이 줄을 쓰는가?

\(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이라 하자.

걸음 ① — 무대는 합동이고 대상을 문자로 올린다.

정의 6.2에 의해 \(n \mid (a-b)\)이고 \(n \mid (c-d)\)이며, 정의 6.1에 의해 \(a - b = ns\), \(c - d = nt\)인 정수 \(s, t\)가 존재한다.

걸음 ② — 정의가 두 겹이므로 두 번 푼다. 등식이 나와야 근거 ③이 작동한다.

목표는 \(ac - bd\)를 “\(n \times (\text{정수})\)” 꼴로 만드는 것이다.

걸음 ③ — 도착점이 차 \(ac - bd\)임을 못 박는다. 이 한 줄이 다음 줄의 조작을 지시한다.

\(ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d)\)이다.

걸음 ④ 전반 — \(bc\)를 더하고 빼서 두 재료가 각각 나타나도록 항을 쪼갠다(근거 ③).

\(= c(ns) + b(nt) = n(cs + bt)\)이다.

걸음 ④ 후반 — 대입 후 \(n\)을 묶는다. 도착점이 지정한 묶음이다.

\(cs + bt\)는 정수이므로 \(n \mid (ac - bd)\)이고, 정의 6.2에 의해 \(ac \equiv bd \pmod n\)이다. \(\blacksquare\)

걸음 ⑤ — 자격 확인(근거 ②) 후 정의 두 겹을 거슬러 올라가 닫는다.

활용. (C5)가 손에 들어오면 §1.1의 과제가 두 줄로 끝난다. \(7 \equiv -1 \pmod 4\)이고 (확인 7), 거듭제곱 보존에 의해 \(7^{100} \equiv (-1)^{100} = 1 \pmod 4\)이다. \(7^{100}\)을 한 번도 계산하지 않았다.

감상. 이 증명의 값은 “\(bc\)를 더하고 빼기”라는 기교에 있지 않다. 그 기교는 재료 \(a - b\)와 \(c - d\)를 각각 한 번씩 쓰는 경로를 택했을 때 걸음 ③이 지정한 도착점이 불러낸 계산이다. §1.4에서 본 대입-전개 경로도 같은 도착점에 이르므로, 걸음 ③이 고르는 것은 유일한 기교가 아니라 어느 변형이 진전인지의 판정 기준이다. 그리고 (C4)(C5)가 증명된 덕분에 합동식을 등식처럼 더하고 곱할 수 있게 되며, 이것이 C11주차에서 “잘 정의된 연산”이라는 이름으로 다시 다뤄진다.

예제 2.3 — 집합·곱: 원소 추적#

Result. \(A \times (B \cap C) = (A \times B) \cap (A \times C)\).

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

확인 19. 이 무대의 설계를 세 줄로 적어 보자.

① 양변의 원소는 어떤 자료형인가.

② 목표가 집합의 상등일 때 증명은 몇 파트인가. 각 파트의 첫 문장은 무엇인가.

③ 좌변과 우변을 각각 논리식으로 번역하면 무엇인가.

답

① 순서쌍 \((x, y)\)다. 곱의 원소이므로 좌표가 둘이다(정의 6.3).

② 두 파트다(1권 27주차 §1.4). (\(\subseteq\)) “\((x,y) \in A \times (B \cap C)\)라

하자.” (\(\supseteq\)) “\((x,y) \in (A \times B) \cap (A \times C)\)라 하자.”

③ 좌변: \(x \in A\) 이고 (\(y \in B\) 이고 \(y \in C\)). 우변: (\(x \in A\) 이고

\(y \in B\)) 이고 (\(x \in A\) 이고 \(y \in C\)). 두 논리식은 “이고”의 괄호 배치와

\(x \in A\)의 중복만 다르다 — 이 관찰이 증명 전체를 미리 보여 준다.

증명. (\(\subseteq\)) \((x, y) \in A \times (B \cap C)\)라 하자. 정의 6.3에 의해 \(x \in A\)이고 \(y \in B \cap C\)이다. 교집합의 정의에 의해 \(y \in B\)이고 \(y \in C\)이다. 그러면 \(x \in A\)이고 \(y \in B\)이므로 정의 6.3에 의해 \((x, y) \in A \times B\)이고, \(x \in A\)이고 \(y \in C\)이므로 \((x, y) \in A \times C\)이다. 따라서 교집합의 정의에 의해 \((x, y) \in (A \times B) \cap (A \times C)\)이다.

(\(\supseteq\)) \((x, y) \in (A \times B) \cap (A \times C)\)라 하자. 교집합의 정의에 의해 \((x, y) \in A \times B\)이고 \((x, y) \in A \times C\)이다. 앞쪽에서 정의 6.3에 의해 \(x \in A\)이고 \(y \in B\)를 얻고, 뒤쪽에서 \(y \in C\)를 얻는다. 그러면 \(y \in B\)이고 \(y \in C\)이므로 \(y \in B \cap C\)이고, \(x \in A\)이므로 정의 6.3에 의해 \((x, y) \in A \times (B \cap C)\)이다.

양방향 포함이 성립하므로 \(A \times (B \cap C) = (A \times B) \cap (A \times C)\)이다. \(\blacksquare\)

이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고 실전의 증명은 처음부터 끝까지 이런 산문이다. 이 명제는 1권 28주차 예제 2.1과 같은 명제이지만, 그때는 논리식 번역을 앞세워 증명했고 여기서는 걸음 ②③④⑤를 따라 적었다. 같은 결과에 이르는 길이 두 개인 것이 아니라, 1권의 서식이 이번 주 절차의 집합 무대 사례였음이 드러난 것이다.

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

예제 2.1, 2.2, 2.3은 무대가 전부 다르지만 걸음의 배치가 같다. 대응표의 빈칸을 채워 보자.

걸음

예제 2.1 (나눗셈)

예제 2.2 (합동)

예제 2.3 (곱)

② 전진면

\(b = ak\), \(c = al\)

\(a - b = ns\), \(c - d = nt\)

\(\underline{\quad(1)\quad}\)

③ 후진면

\(bx+cy\)를 \(a \times (\text{정수})\) 꼴로

\(\underline{\quad(2)\quad}\)

\((x,y)\)가 우변의 두 좌표 조건을 갖췄음을 보이기

④ 대수

\(a\)로 묶기

\(bc\) 더하고 빼기 + \(n\)으로 묶기

\(\underline{\quad(3)\quad}\)

⑤ 자격 확인

\(kx + ly\)가 정수

\(cs + bt\)가 정수

두 좌표가 각각 해당 집합의 원소

확인 20. 빈칸 (1)~(3)을 채워 보자.

답

(1) \((x, y)\)에서 \(x \in A\), \(y \in B\), \(y \in C\)를 꺼낸다.

(2) \(ac - bd\)를 \(n \times (\text{정수})\) 꼴로 만든다.

(3) “이고”의 묶음을 다시 배치한다 — \(x \in A \wedge (y \in B \wedge y \in C)\)를

\((x \in A \wedge y \in B) \wedge (x \in A \wedge y \in C)\)로 재조립한다.

세 무대에서 걸음 ④의 도구만 다르다 — 대수의 묶기, 항의 쪼개기, 논리 연결의 재배치.

확인 21. 세 예제에서 공통으로 반복된 순서를 다섯 걸음으로 적어 보자. 걸음 ③을 건너뛰면 세 예제 각각에서 무엇이 무너지는가.

답

① 무대 확인 \(\to\) ② 전진면 \(\to\) ③ 후진면 \(\to\) ④ 무대의 대수 \(\to\) ⑤ 자격 확인과 선언.

③을 건너뛰면 예제 2.1에서는 \(akx + aly\)에서 멈춰 \(a\)로 묶을 이유를 찾지 못하고,

예제 2.2에서는 전개를 해 놓고도 그것이 도착점에 닿았는지 판정하지 못한 채

멈추며, 예제 2.3에서는

어느 방향의 포함을 증명 중인지 놓쳐 두 파트가 뒤섞인다.

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

백지 암기 대상

무대 이동 절차

① 무대 확인 — 명제의 이름이 어느 정의의 소관인지 지목한다 \(\to\) ② 전진면 — 가정의 이름을 정의로 풀어 재료를 받는다 \(\to\) ③ 후진면 — 목표의 이름을 정의로 풀어 만들어야 할 꼴을 먼저 적는다 \(\to\) ④ 무대의 대수 — 재료를 그 꼴에 맞춰 조립한다 \(\to\) ⑤ 자격 확인과 선언 — 요구된 자격을 밝히고 정의를 인용해 닫는다.

무대가 바뀌어도 엔진은 같다. 바뀌는 것은 ①에서 지목하는 정의와 ④에서 쓰는 대수의 종류뿐이다. 이 절차는 C7주차의 반례\(\cdot\)귀류\(\cdot\)존재 증명에서도 뼈대로 남고, 거기서는 걸음 ③의 도착점이 “모순”이나 “증인”으로 갈릴 뿐이다.

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

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

훈련 1 ●○○ — 수식과 절차 빈칸#

Result. 정수 \(a\)에 대해, \(a \equiv 3 \pmod 5\)이면 \(a^2 \equiv 4 \pmod 5\)이다.

  • \(a \equiv 3 \pmod 5\)라 하자. 합동의 \(\underline{\quad(1)\quad}\) 보존을 반복 적용한 결과(거듭제곱 보존)에 의해 \(a^2 \equiv 3^2 \pmod 5\)이다.

  • \(3^2 = 9\)이고 \(9 - 4 = 5\)이므로 \(9 \equiv \underline{\quad(2)\quad} \pmod 5\)이다.

  • 두 합동식을 잇는 데 쓰는 성질은 (C1)~(C5) 중 \(\underline{\quad(3)\quad}\)이고, 그 결과 \(a^2 \equiv 4 \pmod 5\)이다. \(\blacksquare\)

  • 이 계산의 핵심: 큰 수 \(a^2\)을 작은 대표 \(3^2 = 9\)로 갈아 끼운 뒤 그 대표를 다시 줄였다 — 합동을 \(\underline{\quad(4)\quad}\)처럼 다룰 수 있게 해 주는 것이 (C4)(C5)다.

  • 검산: \(a = 8\)은 \(8 - 3 = 5\)이므로 \(a \equiv 3 \pmod 5\)이다. \(a^2 = 64\)이고 \(64 - 4 = 60 = 5 \times 12\)이므로 \(64 \equiv \underline{\quad(5)\quad} \pmod 5\) ✓.

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

이번에는 각 걸음의 근거 이름과 걸음 번호도 빈칸이다.

Result. 정수 \(a, b\)와 양의 정수 \(n\)에 대해, \(a \equiv b \pmod n\)이면 \(a^2 \equiv b^2 \pmod n\)이다.

  • \(a \equiv b \pmod n\)이라 하자. 정의 6.2에 의해 \(\underline{\quad(1)\quad}\)이고, 정의 6.1에 의해 \(a - b = ns\)인 정수 \(s\)가 존재한다. 이 두 줄이 무대 이동 절차의 걸음 \(\underline{\quad(2)\quad}\)이고, 대는 근거는 \(\underline{\quad(3)\quad}\)이다.

  • 목표를 정의로 풀면 “\(a^2 - b^2\)이 \(n \times (\text{정수})\) 꼴”이다. 이 줄이 걸음 ③이다.

  • \(a^2 - b^2 = (a - b)(a + b) = \underline{\quad(4)\quad}\)이다.

  • \(s(a+b)\)는 정수이므로(근거 \(\underline{\quad(5)\quad}\)) \(n \mid (a^2 - b^2)\)이고, 정의 6.2에 의해 \(a^2 \equiv b^2 \pmod n\)이다. \(\blacksquare\)

  • 같은 결론을 (C5)에 \(c = a\), \(d = b\)를 대입해 한 줄로 얻을 수도 있다. 이때 대는 근거는 \(\underline{\quad(6)\quad}\)이고, 인용 조건은 (C5)가 \(\underline{\quad(7)\quad}\)이다.

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

이번에는 절차의 각 칸을 통째로 채운다. 무대는 곱과 차집합이 섞여 있다.

Result. \(A \times (B - C) = (A \times B) - (A \times C)\).

  • ① 무대 확인과 자료형, 양변의 논리식 번역: \(\underline{\quad(1)\quad}\)

  • ② (\(\subseteq\)) 파트 — 첫 문장부터 마지막 문장까지: \(\underline{\quad(2)\quad}\)

  • ③ (\(\supseteq\)) 파트 — 첫 문장부터 마지막 문장까지 (한 군데에서 “\(x \notin A\) 또는 \(y \notin C\)” 중 하나를 배제하는 걸음이 필요하다): \(\underline{\quad(3)\quad}\)

  • ④ 마무리 선언: \(\underline{\quad(4)\quad}\)

이 훈련은 차집합이 붙는 좌표가 왼쪽이 아니라 오른쪽일 뿐 문제 17과 같은 뼈대다 — 좌표 위치만 바꾸면 문제 17이 된다.

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 이 순서가 답지 암기 습관을 끊는 장치다. 나눗셈\(\cdot\)합동 문제는 정의 전개를, 집합\(\cdot\)곱 문제는 원소 추적을 각 줄에 명시한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 이번 주의 근거는 세 형태로 제출된다. ① 나눗셈\(\cdot\)합동 문제에서는 정의를 몇 겹 풀었는지가 점수다 — 합동은 정의 6.2와 6.1을 연이어 풀어야 등식이 나오고, “합동이므로 \(a - b = ns\)”라고 한 겹을 건너뛴 답안은 근거가 한 줄 비어 있다. ② 합동식을 변형한 줄에서는 인용한 성질의 번호가 점수다 — “양변에 곱하면”은 등식의 성질이 아니라 (C5)이고, 나누기는 어느 번호로도 인용할 수 없다(확인 8). ③ 집합\(\cdot\)곱 문제에서는 몇 파트인지와 각 파트의 첫 문장이 점수다 — 상등은 두 파트이고 각 파트는 자기 첫 문장으로 시작한다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. [백지] 나눗셈 정의\(\cdot\)세 성질, 합동 정의\(\cdot\)대수 보존(덧셈\(\cdot\)곱셈\(\cdot\)거듭제곱), 데카르트 곱 정의를 쓰시오.

힌트

다섯 항목을 한 줄씩 순서대로 떠올리면 중간에서 끊긴다. 두 묶음으로 나눈다 —

무대를 여는 정의(6.1\(\cdot\)6.2\(\cdot\)6.3)와 그 무대에서 인용 가능한 정리((D1)~(D3),

(C1)~(C5), 거듭제곱 보존)다. 묶음 이름이 서면 그 안의 항목이 따라 나온다.

2. 계산하시오 (합동 활용). (a) \(3^{50} \pmod 4\) (b) \(2^{10} \pmod 3\) (c) \(123 \times 456 \pmod{10}\) (일의 자리)

힌트

세 문제 모두 걸음은 같다 — 큰 수를 합동인 작은 대표로 갈아 끼운 뒤 (C5)나

거듭제곱 보존을 인용한다. (a)(b)는 대표를 \(-1\)로 잡으면 거듭제곱이 부호 계산으로

끝난다. (c)는 일의 자리가 법 10의 나머지라는 번역부터 한다.

3. 예제 2.1(선형결합)을 백지 재현하시오.

힌트

다섯 걸음의 이름부터 세로로 적고 칸을 채운다. 걸음 ③(”\(a \times (\text{정수})\)

꼴을 만든다”)을 적지 않으면 걸음 ④에서 무엇으로 묶을지가 나오지 않는다.

4. 빈칸 훈련을 백지에서 완성하시오.

힌트

훈련 3이 막히면 ①만 먼저 적는다. 양변을 논리식으로 옮겨 나란히 두면 두 파트에서

각각 무엇을 도출해야 하는지가 보인다. (\(\supseteq\)) 방향에서 “또는” 하나를

배제하는 걸음은, 이미 손에 있는 사실 \(x \in A\)와 충돌하는 쪽을 지우는 일이다.

5. 예제 2.2(곱셈 보존)를 백지 재현하고 \(7^{100} \pmod 4\)를 계산하시오.

힌트

재현에서 막히는 곳은 언제나 “\(bc\)를 더하고 빼기”다. 그 조작을 외우지 말고

도착점 \(ac - bd\)와 재료 \(a-b\), \(c-d\)를 나란히 적어 보면, 두 재료를 한 번씩 쓰려면

중간에 무엇이 필요한지가 계산으로 나온다.

6. “\(a \mid b\)이고 \(b \mid c\)이면 \(a \mid c\)”(추이성)를 직접 증명하시오 (S3주차 문제 7의 재방문).

힌트

정의를 두 번 푼다. 두 번째 등식의 좌변이 첫 번째 등식의 좌변과 다르다는 것이

열쇠다 — \(b = ak\)이고 \(c = bl\)이므로, \(c\)의 식에 \(b\)를 대입할 자리가 있다.

표준 ●●○#

7. 합동 덧셈 보존(”\(a \equiv b, c \equiv d \pmod n\)이면 \(a + c \equiv b + d\)”)을 증명하시오 (예제 2.2의 덧셈판).

힌트

도착점은 \((a+c) - (b+d)\)가 \(n \times (\text{정수})\) 꼴임을 보이는 것이다. 이번에는

예제 2.2와 달리 항을 더하고 뺄 필요가 없다 — 도착점의 차를 재배열하면 재료 둘이

그대로 나온다. 왜 곱셈 쪽에서만 다리가 필요했는지도 함께 생각해 본다.

8. “정수 \(a\)에 대해, \(a\)가 홀수이면 \(a^2 \equiv 1 \pmod 8\)”을 증명하시오.

힌트

전개 후 \(4k^2 + 4k\)에서 4를 묶으면 \(4k(k+1)\)이 나온다. 남은 일은 \(k(k+1)\)이

짝수임을 대는 것이고, 그 사실은 1권 1주차 문제 16에서 경우 나누기로 증명되었다.

9. “\(A \subseteq B\)이면 \(A \times C \subseteq B \times C\)”를 증명하시오 (순서쌍 분해 + 선택법).

힌트

목표가 포함이므로 파트는 하나이고 첫 문장은 “\((x, y) \in A \times C\)라 하자”다.

가정 \(A \subseteq B\)는 원소 하나에 발동하는 재료다 — \(x \in A\)를 얻은 줄 바로

다음에 쓴다 (S7주차의 특수화).

10. 다음 제시된 증명을 평가하시오 (C5주차의 증명 평가 절차).

Result. 정수 \(a, b\)와 양의 정수 \(n\)에 대해, \(a \equiv b \pmod n\)이면 \(a^2 \equiv b^2 \pmod n\).

제시된 증명. \(a \equiv b\)이므로 \(a = b\)이다. 따라서 \(a^2 = b^2\)이라 \(a^2 \equiv b^2\).

힌트

C5주차의 평가 절차를 순서대로 돌린다. ① 명제 자체는 참인가 거짓인가를 먼저

판정한다 — 이 판정 결과에 따라 뒤의 지적이 “논증 결함”인지 “명제 자체가 거짓”인지

갈린다. 판정이 끝나면 결함이 있는 줄을 지목하고 반례로 뒷받침한다.

11. 정수 \(a, b\)에 대해 “\(a \mid b\)이고 \(b \neq 0\)이면 \(\lvert a \rvert \le \lvert b \rvert\)”를 증명하시오.

힌트

이 문제의 진짜 걸음은 “\(k \neq 0\)”을 확보하는 자리다. \(b \neq 0\)에서 어떻게

\(k \neq 0\)이 나오는지 한 줄로 적는다. 그다음 “0이 아닌 정수의 절댓값은 1 이상”이

정수라는 자격에서 오는 사실임을 밝힌다.

12. 페르마 소정리 맛보기: \(a^5 \equiv a \pmod 5\)를 모든 \(a \in \{0,1,2,3,4\}\)에서 직접 확인하시오. 이것은 “\(a^p \equiv a \pmod p\)”의 \(p = 5\) 사례다(C15주차 예고).

힌트

다섯 값을 각각 계산하되, 계산마다 “몇에서 몇을 빼면 5의 배수인가”를 함께 적는다.

그것이 정의 6.2를 실제로 확인하는 줄이다. \(4^5\)은 \(4 \equiv -1 \pmod 5\)로 갈아

끼우면 값을 구하지 않고도 답이 나온다.

13. 데카르트 곱과 합집합: \(A \times (B \cup C) = (A \times B) \cup (A \times C)\)를 증명하시오 (예제 2.3의 합집합판 — 원소 추적, \(\lor\) 처리).

힌트

예제 2.3과 같은 두 파트 구조이고 다른 것은 “이고”가 “또는”으로 바뀐 것뿐이다.

“또는”이 가정 쪽에 나타나면 경우로 쪼갠다(S15주차). 두 경우 각각에서 도착점에

이르는지 확인하고, 경우들이 전체를 덮는지도 한 줄로 밝힌다.

14. 나눗셈 무대의 대우 증명: “정수 \(n\)에 대해, \(3 \nmid n^2\)이면 \(3 \nmid n\)”을 증명하시오. 그 기법을 고른 이유도 함께 적으시오.

힌트

원명제를 직접 시도하면 걸음 ②에서 막힌다 — “\(3 \nmid n^2\)”은 부정형이라 꺼낼

등식이 없다. 대우를 적으면 가정이 긍정형이 되어 정의가 즉시 풀린다.

S12주차의 판정 신호(“가정과 결론이 모두 부정형이면 대우”)를 인용해 기법 선택의

이유까지 쓴다.

도전 ●●●#

이 문제들이 빌려 쓰는 사실

문제 15는 “정수 \(x\)에 대해 \(2 \mid x\)이고 \(3 \mid x\)이면 \(6 \mid x\)”를 쓴다. 이 명제는 1권 20주차 문제 13에서 증명되었으므로 근거 ④로 인용한다. 일반적으로 “\(m \mid x\)이고 \(n \mid x\)이면 \(mn \mid x\)”는 거짓이다(\(m = n = 2\), \(x = 2\)가 반례다). 2와 3이 서로소라는 조건이 필요하고, 그 일반형은 C15주차의 몫이다.

15. (합동 대작) \(n\)이 양의 정수일 때 \(n^3 \equiv n \pmod 6\)임을 증명하시오.

힌트

도착점은 \(6 \mid (n^3 - n)\)이다. \(n^3 - n\)을 인수분해해 연속 세 정수의 곱으로

만든 뒤, 2의 배수임과 3의 배수임을 따로 확보한다. 3의 배수 쪽은 나눗셈 정리로

\(n\)을 세 경우로 나누면 매 경우 셋 중 누가 3의 배수인지 지목할 수 있다

(S15주차 문제 19).

십진 전개 표기 — 문제 16을 위한 도입

자연수 \(n\)의 십진 표기가 \(d_m d_{m-1} \cdots d_1 d_0\)이라는 것은 \(n = \sum_{i=0}^{m} d_i 10^i\)이라는 뜻이고, 각 \(d_i\)는 0 이상 9 이하의 정수다. 예를 들어 \(n = 4703\)이면 \(4703 = 4 \cdot 10^3 + 7 \cdot 10^2 + 0 \cdot 10^1 + 3 \cdot 10^0\)이다. 유한 개의 합에 (C4)를 반복 적용하는 것은 항의 개수에 대한 귀납이 필요하고, 그 형태의 반복은 1권 31주차에서 정당화되었으므로 여기서는 인용해 쓴다.

16. (자리합 판정 일반화) “정수 \(n = \sum_{i} d_i 10^i\) (십진 전개)에 대해 \(n \equiv \sum_i d_i \pmod 9\)”를 증명하시오. 이어서 “\(n\)이 9의 배수인 것과 자리합이 9의 배수인 것은 동치이다”를 증명하시오.

힌트

세 겹이다. 먼저 \(10 \equiv 1 \pmod 9\)을 정의로 확인하고, 거듭제곱 보존으로

\(10^i \equiv 1\)을 얻고, (C5)로 \(d_i 10^i \equiv d_i\)를 얻은 뒤 (C4)로 합친다.

마지막 “따라서” 문장은 별도의 논증이 필요하다 — \(n\)과 자리합의 차가 9의 배수라는

사실에서 두 배수 판정이 서로를 결정한다는 것은 예제 2.1의 (D2)로 나온다.

17. (집합 대수 종합) \((A - B) \times C = (A \times C) - (B \times C)\)를 증명하시오 (차집합\(\cdot\)곱의 상호작용 — 원소 추적에서 “\(x \in A\) \(\land\) \(x \notin B\)”와 순서쌍 결합).

힌트

(\(\supseteq\)) 방향이 이 문제의 전부다. \((x,y) \notin B \times C\)를 정의 6.3으로

풀면 “\(x \notin B\) 또는 \(y \notin C\)”가 나온다(1권 11주차의 부정 규칙). 그런데

같은 줄에서 이미 \(y \in C\)를 확보했으므로 “또는”의 한쪽이 지워진다.

18. (진단 종합) 다음 제시된 증명을 평가하시오.

Result. 정수 \(a, b, c\)에 대해, \(a \mid bc\)이면 \(a \mid b\) 또는 \(a \mid c\).

제시된 증명. \(a \mid bc\)이므로 \(bc = ak\). 따라서 \(a\)가 \(b\)나 \(c\) 중 하나를 나눈다.

힌트

증명의 줄을 검사하기 전에 평가 절차 ①을 먼저 돌린다. 명제가 거짓이면 어떤 논증도

옳을 수 없으므로, 반례 하나가 평가를 끝낸다. 반례를 찾을 때는 \(bc\)가 \(a\)의 배수가

되면서 \(b\)와 \(c\) 각각은 \(a\)보다 작은 경우를 노린다.

19. (설계) “정수 \(a\)에 대해 \(a^2 \equiv 0\) 또는 \(1 \pmod 4\)”를 합동으로 증명하시오. 이를 이용해 “\(x^2 + y^2 = 3\)인 정수 해가 없음”을 증명하시오.

힌트

앞부분은 네 경우를 나눈 뒤 각 경우에 거듭제곱 보존을 쓰면 끝난다. 경우가 전체를

덮는 근거는 나눗셈 정리다. 뒷부분은 등식 \(x^2 + y^2 = 3\)의 양변을 법 4에서 읽는

것이 전부다 — 같은 수는 어느 법에서도 자기 자신과 합동이므로((C1)), 좌변이 가질

수 있는 값의 집합과 우변의 값을 비교한다.

20. (서술) (a) 합동이 “등식처럼” 다뤄질 수 있는 이유(대수 보존 법칙)를 예제 2.2로 뒷받침하고, 그 덕에 큰 수 계산이 작은 대표로 환원됨을 세 문장 이내로. (b) “무대가 바뀌어도 엔진은 같다”(직접\(\cdot\)대우 + 정의 전개)를 나눗셈\(\cdot\)합동\(\cdot\)곱 세 무대로 두 문장 이내 설명하시오.

힌트

(a)는 “무엇이 보존되고 무엇이 보존되지 않는가”를 함께 적어야 완결이다 — 확인 8이

그 경계다. (b)는 §1.6의 대조표에서 어느 칸이 무대마다 달라지고 어느 칸이 같은지를

한 문장으로 압축하면 나온다.

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

이번 주의 5일 루틴. 원서와 교안을 번갈아 쓰는 순서다.

요일

할 일

1일차

원서 Chartrand 4장 통독 (모르는 문장은 표시만 하고 통과)

2일차

교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다

3일차

원서 재독 — 1일차에 표시한 문장을 해결하고, 원서 4장의 연습문제 몇 개를 직접 시도

4일차

교안 §3 빈칸 사다리 + §4 연습문제 20문항

5일차

백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트

원서 4장은 절이 여럿이고 소재가 무대별로 흩어져 있다. 3일차 재독에서는 각 절의 Result마다 “이것은 §1.6 대조표의 어느 행인가”를 여백에 표시하며 읽는다. 표시가 끝나면 장 전체가 다섯 무대의 목록으로 정리된다.

1차 시도 — 틀 카드 허용. 다음 세 상자만 옮겨 적은 카드를 펴 놓는다: 정의 6.1, 정의 6.2, 무대 이동 절차 다섯 걸음. 그 상태에서 예제 2.1과 예제 2.2를 처음부터 끝까지 적는다. 예제 본문과 확인 상자는 보지 않는다.

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

  • 정의 6.1\(\cdot\)6.2\(\cdot\)6.3을 조각 그대로 백지에 썼다 (“정수 \(k\)가 존재한다”와 “양의 정수 \(n\)”까지).

  • (D1)~(D3)과 (C1)~(C5)를 쓰고, 각각이 이번 주 어디에서 증명되는지 표시했다.

  • 무대 이동 절차 다섯 걸음을 쓰고, 걸음 ③을 뺐을 때 무엇을 판정할 수 없게 되는지 한 사례로 적었다.

  • 예제 2.1(선형결합)\(\cdot\)2.2(곱 보존)\(\cdot\)2.3(곱의 분배)을 처음부터 끝까지 재현했다.

  • \(7^{100} \pmod 4\)를 계산하고, 어느 줄에서 (C5)나 거듭제곱 보존을 인용했는지 밝혔다.

  • 합동식에서 허용되는 조작과 허용되지 않는 조작을 각각 한 예로 들었다 (확인 8).

  • §1.6의 다섯 무대 대조표를 빈칸 없이 재현했다.

  • 원서 4장을 완독했고, 1일차에 표시한 문장이 전부 해결되었다.

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

막힌 지점

처방

합동 문제에서 첫 줄 다음이 나오지 않는다

§1.3 해부 표 — 정의가 두 겹이다. 6.2로 한 겹, 6.1로 한 겹 더 푼다

식은 변형했는데 끝났는지 알 수 없다

§1.4 걸음 ③ — 도착점을 먼저 적었는지 확인한다

예제 2.2의 “더하고 빼기”가 떠오르지 않는다

확인 18 — 도착점과 재료를 나란히 적으면 무엇이 부족한지가 계산으로 나온다

합동식을 나누거나 약분하게 된다

확인 8 — (C4)(C5)가 보장하는 것은 더하기와 곱하기뿐이다

집합 상등 증명에서 두 파트가 뒤섞인다

예제 2.3과 1권 27주차 §1.4의 서식 표 — 파트마다 자기 첫 문장으로 연다

곱 무대에서 무엇을 추적할지 모르겠다

정의 6.3 — 추적 대상은 원소이고, 이 무대의 원소는 순서쌍이다

대우로 갈지 직접으로 갈지 판단이 안 된다

문제 14의 힌트와 S12주차의 판정 신호 — 가정이 부정형이면 꺼낼 등식이 없다

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) 곱셈 (2) \(4\) (3) (C3) 추이 (4) 등식 (5) \(4\)

※ (3)이 이 훈련의 핵심이다. \(a^2 \equiv 9\)와 \(9 \equiv 4\)라는 두 합동식을 이어 \(a^2 \equiv 4\)를 얻는 일은 자동이 아니라 (C3)의 인용이다. 등식이라면 아무 말 없이 이었을 자리에서, 합동은 인용할 번호가 정해져 있다. (1)에서 “거듭제곱”이라고만 적었다면 절반이다 — 거듭제곱 보존은 (C5) 곱셈 보존을 반복 적용해 얻은 것이고, 그 출처(1권 31주차 문제 13)까지 대는 것이 완결이다.

빈칸 사다리 — 훈련 2#

(1) \(n \mid (a - b)\) (2) ② (3) ① 정의 (4) \(ns(a+b)\) (5) ② 닫힘성 (6) ④ 이미 증명한 명제 (7) 이미 증명되어 있을 것 (1권 20주차 문제 17과 이 주차 예제 2.2)

※ (4)에서 인수분해 \(a^2 - b^2 = (a-b)(a+b)\)를 떠올리는 것이 걸음 ④의 전부다. 도착점이 “\(a^2 - b^2\)이 \(n\)의 배수”이고 재료가 “\(a - b = ns\)”이므로, \(a^2 - b^2\) 안에서 \(a - b\)를 만들어 내는 변형을 찾게 된다. (6)(7)이 이 훈련에서 새로 요구되는 판정이다 — 같은 명제를 두 경로로 증명할 수 있을 때, 어느 경로를 택하든 인용하는 정리가 증명 완료 상태인지 확인하는 책임은 사라지지 않는다.

빈칸 사다리 — 훈련 3#

(1) 무대는 데카르트 곱과 차집합이고, 원소의 자료형은 순서쌍 \((x, y)\)다. 좌변 \((x,y) \in A \times (B - C)\)는 “\(x \in A\) 이고 (\(y \in B\) 이고 \(y \notin C\))”로, 우변 \((x,y) \in (A \times B) - (A \times C)\)는 “(\(x \in A\) 이고 \(y \in B\)) 이고 (\(x \notin A\) 또는 \(y \notin C\))”로 번역된다. 우변의 뒷부분이 “또는”인 것은 \((x,y) \notin A \times C\)를 부정 규칙으로 푼 결과다.

(2) (\(\subseteq\)) \((x, y) \in A \times (B - C)\)라 하자. 정의 6.3에 의해 \(x \in A\)이고 \(y \in B - C\)이다. 차집합의 정의에 의해 \(y \in B\)이고 \(y \notin C\)이다. \(x \in A\)이고 \(y \in B\)이므로 정의 6.3에 의해 \((x,y) \in A \times B\)이다. 또 \(y \notin C\)이므로 \((x, y) \in A \times C\)일 수 없다 — 만약 그렇다면 정의 6.3에 의해 \(y \in C\)가 되어 모순이다. 따라서 \((x,y) \in (A \times B) - (A \times C)\)이다.

(3) (\(\supseteq\)) \((x, y) \in (A \times B) - (A \times C)\)라 하자. 차집합의 정의에 의해 \((x,y) \in A \times B\)이고 \((x,y) \notin A \times C\)이다. 앞쪽에서 정의 6.3에 의해 \(x \in A\)이고 \(y \in B\)이다. 뒤쪽을 정의 6.3과 부정 규칙으로 풀면 “\(x \notin A\) 또는 \(y \notin C\)”인데, 이미 \(x \in A\)를 확보했으므로 앞쪽 선택지는 성립할 수 없고 \(y \notin C\)가 남는다. 그러면 \(y \in B\)이고 \(y \notin C\)이므로 \(y \in B - C\)이고, \(x \in A\)이므로 정의 6.3에 의해 \((x,y) \in A \times (B - C)\)이다.

(4) 양방향 포함이 성립하므로 \(A \times (B - C) = (A \times B) - (A \times C)\)이다. \(\blacksquare\)

※ 이 훈련의 값은 (3)의 “또는 하나를 지우는” 걸음에 있다. 이미 손에 든 사실 \(x \in A\)가 선택지 하나와 충돌하므로 남은 하나가 확정된다. 걸음을 두 줄로 적으면 이렇다 — 경우 1: \(x \notin A\) — 이미 확보한 \(x \in A\)와 모순이므로 이 경우는 일어나지 않는다. 경우 2: \(y \notin C\) — 목표에 도달한다. 이 걸음의 이름은 선언 삼단논법이고, S15주차의 분류로는 한 케이스가 모순으로 배제되는 경우법이다. 소거법은 결론의 \(\lor\)에 붙는 도구이므로(S15주차 정의 15.2) 여기에는 쓰지 않는다 — 여기의 \(\lor\)는 결론이 아니라 이미 손에 든 사실, 곧 가정 쪽에 있다.

문제 1#

접근. 다섯 항목을 순서대로 떠올리면 중간에서 끊긴다. 두 묶음으로 나눈다. 무대를 여는 정의(6.1 나눗셈, 6.2 합동, 6.3 곱)와 그 무대에서 인용 가능한 정리((D1)~(D3), (C1)~(C5), 거듭제곱 보존)다. 정의는 약속이라 외우고, 정리는 증명이 끝난 것만 인용한다는 구분까지가 이 문제의 답이다.

풀이. 정의 6.1: 정수 \(a, b\)에 대해 \(a \mid b\)란 \(b = ak\)인 정수 \(k\)가 존재한다는 뜻이다. 성질 (D1) 추이 — \(a \mid b\), \(b \mid c\)이면 \(a \mid c\). (D2) 선형결합 — \(a \mid b\), \(a \mid c\)이면 임의의 정수 \(x, y\)에 대해 \(a \mid (bx+cy)\). (D3) 크기 — \(a \mid b\), \(b \neq 0\)이면 \(\lvert a \rvert \le \lvert b \rvert\). 정의 6.2: 정수 \(a, b\)와 양의 정수 \(n\)에 대해 \(a \equiv b \pmod n\)이란 \(n \mid (a - b)\)라는 뜻이다. 대수 (C1) 반사, (C2) 대칭, (C3) 추이, (C4) 합 보존 (\(a \equiv b\), \(c \equiv d\)이면 \(a + c \equiv b + d\)), (C5) 곱 보존 (같은 가정에서 \(ac \equiv bd\)), 그리고 거듭제곱 보존 (\(a \equiv b\)이면 모든 자연수 \(m\)에 대해 \(a^m \equiv b^m\)). 정의 6.3: \(A \times B = \{(x,y) : x \in A \text{ 이고 } y \in B\}\).

복기. 백지 재현에서 빠지기 쉬운 조각은 정의 6.1의 “정수 \(k\)”와 정의 6.2의 “양의 정수 \(n\)”이다. 앞의 것은 빠지면 정의가 무너지고(확인 4), 뒤의 것은 빠지면 정의가 퇴화하거나 중복된다(§1.3의 삭제 실험 (가)~(다)). 조각이 하는 일을 이유와 함께 외우면 백지에서 복구가 가능하다.

문제 2#

접근. 세 문제 모두 절차가 같다. 큰 수를 합동인 작은 대표로 갈아 끼운 뒤 (C5)나 거듭제곱 보존을 인용한다. 대표는 나머지일 필요가 없고 계산이 쉬운 쪽을 고른다 — 거듭제곱에서는 \(-1\)이 가장 쉽다. (c)의 “일의 자리”는 법 10의 나머지라는 번역부터 해야 합동 문제가 된다.

풀이. (a) \(3 - (-1) = 4\)이고 \(4 \mid 4\)이므로 \(3 \equiv -1 \pmod 4\)이다. 거듭제곱 보존에 의해 \(3^{50} \equiv (-1)^{50} \pmod 4\)이고 \((-1)^{50} = 1\)이므로 \(3^{50} \equiv 1 \pmod 4\)이다. 검산: \(3^2 = 9 = 4 \times 2 + 1\)이므로 \(3^2 \equiv 1\)이고, \(3^{50} = (3^2)^{25} \equiv 1^{25} = 1 \pmod 4\) ✓. (b) \(2 - (-1) = 3\)이고 \(3 \mid 3\)이므로 \(2 \equiv -1 \pmod 3\)이다. 거듭제곱 보존에 의해 \(2^{10} \equiv (-1)^{10} = 1 \pmod 3\)이다. 검산: \(2^{10} = 1024\)이고 \(1024 = 3 \times 341 + 1\)이므로 나머지 1 ✓. (c) 일의 자리는 법 10의 나머지다. \(123 - 3 = 120 = 10 \times 12\)이므로 \(123 \equiv 3 \pmod{10}\)이고, \(456 - 6 = 450 = 10 \times 45\)이므로 \(456 \equiv 6 \pmod{10}\)이다. (C5)에 의해 \(123 \times 456 \equiv 3 \times 6 = 18 \pmod{10}\) 이고, \(18 - 8 = 10\)이므로 (C3)에 의해 \(123 \times 456 \equiv 8 \pmod{10}\)이다. 곧 일의 자리는 8이다. 검산: \(123 \times 456 = 56088\) ✓.

복기. 세 계산 모두 “큰 수 \(\to\) 작은 대표 \(\to\) 계산 \(\to\) 다시 줄이기”의 네 박자다. 마지막 “다시 줄이기”에서 (C3)을 인용하는 것을 빠뜨리기 쉽다.

문제 3#

접근. 다섯 걸음의 이름을 세로로 적고 칸을 채우는 것부터 한다. 재현이 막히는 자리는 대개 걸음 ③이다 — 도착점 “\(bx + cy = a \times (\text{정수})\)”를 적어 두지 않으면 걸음 ④에서 무엇으로 묶을지가 나오지 않는다.

풀이. 정수 \(a, b, c\)에 대해 \(a \mid b\)이고 \(a \mid c\)라 하자. 또 \(x, y\)를 임의의 정수라 하자. 정의 6.1에 의해 \(b = ak\)인 정수 \(k\)가 존재하고 \(c = al\)인 정수 \(l\)이 존재한다. 목표는 \(bx + cy\)를 “\(a \times (\text{정수})\)” 꼴로 만드는 것이다. 그러면

\[ bx + cy = (ak)x + (al)y = akx + aly = a(kx + ly) \]

이고, \(k, l, x, y\)가 정수이므로 정수의 곱과 합인 \(kx + ly\)도 정수이다. 따라서 정의 6.1에 의해 \(a \mid (bx + cy)\)이다. \(\blacksquare\)

복기. 몫에 서로 다른 문자 \(k, l\)을 쓴 것이 이 증명의 설정 단계다. 같은 문자를 쓰면 \(b = c\)를 몰래 가정한 것이 되어 명제보다 좁은 것만 증명하게 된다. 검산: \(a = 3\), \(b = 6\), \(c = 9\), \(x = 2\), \(y = -1\)이면 \(bx + cy = 12 - 9 = 3\)이고 \(3 \mid 3\) ✓.

문제 4#

접근. 세 훈련은 지지대의 크기만 다르고 같은 절차를 돌린다. 훈련 1은 인용할 성질의 번호를 묻고, 훈련 2는 걸음 번호와 근거 번호를 함께 묻고, 훈련 3은 절차 전체를 통째로 요구한다. 훈련 3에서 막히면 ①만 먼저 적는다 — 양변을 논리식으로 옮겨 나란히 두면 두 파트에서 각각 무엇을 도출해야 하는지가 보인다.

풀이. 훈련 1의 답은 (1) 곱셈 (2) \(4\) (3) (C3) 추이 (4) 등식 (5) \(4\)이고, 핵심은 두 합동식을 잇는 자리에 (C3)을 인용해야 한다는 것이다. 훈련 2의 답은 (1) \(n \mid (a-b)\) (2) ② (3) ① 정의 (4) \(ns(a+b)\) (5) ② 닫힘성 (6) ④ (7) 증명 완료 상태이며, 핵심은 \(a^2 - b^2 = (a-b)(a+b)\)라는 인수분해가 “재료 \(a-b\)를 도착점 안에서 만들어 내는” 변형이라는 점이다. 훈련 3의 답은 위 사다리 해설의 (1)~(4)이고, 핵심은 (\(\supseteq\)) 방향에서 “\(x \notin A\) 또는 \(y \notin C\)” 중 앞쪽을 \(x \in A\)로 지우는 선언 삼단논법의 걸음이다.

복기. 세 훈련의 채점은 빈칸의 값이 아니라 인용한 번호로 한다. 값이 맞아도 근거 번호가 비어 있으면 백지 재현에서 그 줄이 복구되지 않는다.

문제 5#

접근. 재현에서 막히는 곳은 언제나 “\(bc\)를 더하고 빼기”다. 그 조작을 외우지 말고, 도착점 \(ac - bd\)와 재료 \(a - b\), \(c - d\)를 나란히 적어 본다. 두 재료를 한 번씩 쓰려면 \(ac\)와 \(bd\) 사이에 다리가 되는 항이 필요하고, 그 항은 \(a\)와 \(c\) 중 하나를 \(b\)나 \(d\)로 바꾼 \(bc\)(또는 \(ad\))다.

풀이. \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이라 하자. 정의 6.2에 의해 \(n \mid (a - b)\)이고 \(n \mid (c - d)\)이며, 정의 6.1에 의해 \(a - b = ns\), \(c - d = nt\)인 정수 \(s, t\)가 존재한다. 목표는 \(ac - bd\)를 “\(n \times (\text{정수})\)” 꼴로 만드는 것이다. 그러면

\[ ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = c(ns) + b(nt) = n(cs + bt) \]

이고, \(b, c, s, t\)가 정수이므로 \(cs + bt\)도 정수이다. 따라서 \(n \mid (ac - bd)\)이고, 정의 6.2에 의해 \(ac \equiv bd \pmod n\)이다. \(\blacksquare\) 계산: \(7 - (-1) = 8 = 4 \times 2\)이므로 \(7 \equiv -1 \pmod 4\)이다. 거듭제곱 보존에 의해 \(7^{100} \equiv (-1)^{100} = 1 \pmod 4\)이다.

복기. 같은 자리에 \(ad\)를 더하고 빼도 된다 — \(ac - bd = ac - ad + ad - bd = a(c-d) + d(a-b)\)이고 결론은 같다. 다리의 선택지가 둘이라는 것은, 그 조작이 기교가 아니라 도착점이 요구한 계산이라는 증거다. 검산: \(n = 5\), \(a = 7 \equiv 2\), \(b = 2\), \(c = 8 \equiv 3\), \(d = 3\)이면 \(ac = 56 \equiv 1\), \(bd = 6 \equiv 1 \pmod 5\) ✓.

문제 6#

접근. 무대는 나눗셈이고 정의를 두 번 푼다. 열쇠는 두 등식의 좌변이 다르다는 것이다 — \(b = ak\)이고 \(c = bl\)이므로 둘째 등식 안의 \(b\)에 첫째 등식을 대입할 자리가 있다. 도착점은 “\(c = a \times (\text{정수})\)”이므로 대입 후 \(a\)로 묶으면 끝난다.

풀이. 정수 \(a, b, c\)에 대해 \(a \mid b\)이고 \(b \mid c\)라 하자. 정의 6.1에 의해 \(b = ak\)인 정수 \(k\)가 존재하고, \(c = bl\)인 정수 \(l\)이 존재한다. 목표는 \(c\)를 “\(a \times (\text{정수})\)” 꼴로 만드는 것이다. 그러면

\[ c = bl = (ak)l = a(kl) \]

이고, \(k, l\)이 정수이므로 \(kl\)도 정수이다. 따라서 정의 6.1에 의해 \(a \mid c\)이다. \(\blacksquare\) 이로써 (D1)이 증명되었으므로 이후 근거 ④로 인용할 수 있다.

복기. 이 증명에는 숫자가 하나도 나오지 않는다. 1권 2주차 예제 2.1이 이것을 “첫 추상 증명”이라 부른 이유가 그것이고, S3주차 문제 7은 같은 명제를 전진\(\cdot\)후진의 만남 지점을 표시하며 분석했다. 검산: \(a = 2\), \(b = 6\), \(c = 18\)이면 \(2 \mid 6\), \(6 \mid 18\), 그리고 \(18 = 2 \times 9\)이므로 \(2 \mid 18\) ✓.

문제 7#

접근. 도착점은 \((a+c) - (b+d)\)가 “\(n \times (\text{정수})\)” 꼴임을 보이는 것이다. 예제 2.2와 달리 항을 더하고 뺄 필요가 없다 — 도착점의 차를 재배열하기만 하면 재료 \(a - b\)와 \(c - d\)가 그대로 나온다. 덧셈은 항끼리 자유롭게 모을 수 있지만 곱셈은 그렇지 않다는 것이, 곱 보존에서만 다리가 필요했던 이유다.

풀이. \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이라 하자. 정의 6.2에 의해 \(n \mid (a-b)\)이고 \(n \mid (c-d)\)이며, 정의 6.1에 의해 \(a - b = ns\), \(c - d = nt\)인 정수 \(s, t\)가 존재한다. 목표는 \((a+c) - (b+d)\)를 “\(n \times (\text{정수})\)” 꼴로 만드는 것이다. 그러면

\[ (a + c) - (b + d) = (a - b) + (c - d) = ns + nt = n(s + t) \]

이고, \(s, t\)가 정수이므로 \(s + t\)도 정수이다. 따라서 \(n \mid ((a+c) - (b+d))\)이고, 정의 6.2에 의해 \(a + c \equiv b + d \pmod n\)이다. \(\blacksquare\)

복기. 같은 결론을 (D2)로 얻을 수도 있다 — \(n \mid (a-b)\)이고 \(n \mid (c-d)\)이므로 \(x = y = 1\)인 선형결합에 의해 \(n \mid ((a-b) + (c-d))\)이다. 나눗셈의 정리 하나가 합동의 정리 하나를 바로 낳는 것은 합동의 정의가 나눗셈으로 되어 있기 때문이다. 검산: \(n = 5\), \(7 \equiv 2\), \(8 \equiv 3\)이면 \(15 \equiv 5 \equiv 0 \pmod 5\) ✓.

문제 8#

접근. 무대는 합동이지만 가정은 홀수라는 짝수\(\cdot\)홀수 무대의 이름이다. 그러므로 걸음 ②는 홀수의 정의를 풀고, 걸음 ③은 합동의 정의를 풀어 “\(a^2 - 1\)이 8의 배수”로 도착점을 옮긴다. 전개 후 4를 묶으면 \(4k(k+1)\)이 되고, 남은 일은 \(k(k+1)\)이 짝수임을 대는 것이다.

풀이. \(a\)를 홀수라 하자. 정의에 의해 \(a = 2k + 1\)인 정수 \(k\)가 존재한다. 목표는 \(a^2 - 1\)이 “\(8 \times (\text{정수})\)” 꼴임을 보이는 것이다. 그러면

\[ a^2 - 1 = (2k+1)^2 - 1 = 4k^2 + 4k + 1 - 1 = 4k^2 + 4k = 4k(k+1) \]

이다. 연속한 두 정수의 곱 \(k(k+1)\)은 짝수이므로(1권 1주차 문제 16 — 근거 ④), \(k(k+1) = 2m\)인 정수 \(m\)이 존재한다. 따라서

\[ a^2 - 1 = 4 \cdot 2m = 8m \]

이고 \(m\)은 정수이므로 정의 6.1에 의해 \(8 \mid (a^2 - 1)\)이다. 곧 정의 6.2에 의해 \(a^2 \equiv 1 \pmod 8\)이다. \(\blacksquare\)

복기. 4를 묶은 뒤 “\(k(k+1)\)에서 2가 하나 더 나온다”를 알아채는 것이 이 증명의 전부다. 같은 리듬이 1권 1주차 문제 17(홀수의 제곱에서 1을 뺀 것이 8의 배수)에서 이미 쓰였고, 1권 17주차 문제 15는 같은 결과를 “나머지가 1”이라는 나눗셈의 언어로 적었다 — 이번 문제는 그것을 합동 표기로 옮긴 것이다. 1권 20주차 문제 18은 이 결과를 합동 언어로 재진술해 두 홀수의 제곱합이 법 8에서 2와 합동임을 얻는다. 검산: \(a = 5\)이면 \(a^2 - 1 = 24 = 8 \times 3\) ✓. \(a = 7\)이면 \(48 = 8 \times 6\) ✓.

문제 9#

접근. 목표가 포함 하나이므로 파트는 하나이고, 첫 문장은 “\((x, y) \in A \times C\)라 하자”다. 가정 \(A \subseteq B\)는 명제가 아니라 원소 하나에 발동하는 재료다 — \(x \in A\)를 손에 넣은 줄 바로 다음에 발동한다(S7주차의 특수화).

풀이. \(A \subseteq B\)라 하자. \((x, y) \in A \times C\)를 임의로 잡자. 정의 6.3에 의해 \(x \in A\)이고 \(y \in C\)이다. \(A \subseteq B\)이므로 \(x \in A\)에서 \(x \in B\)를 얻는다. 그러면 \(x \in B\)이고 \(y \in C\)이므로, 정의 6.3에 의해 \((x, y) \in B \times C\)이다. 임의로 잡은 원소가 \(B \times C\)에 속했으므로 \(A \times C \subseteq B \times C\)이다. \(\blacksquare\)

복기. 이 명제의 역(”\(A \times C \subseteq B \times C\)이면 \(A \subseteq B\)”)은 일반적으로 거짓이다 — \(C = \emptyset\)이면 양변이 모두 공집합이라 포함이 공짜로 성립하지만 \(A \subseteq B\)일 이유가 없다. 1권 28주차 문제 17이 이 쌍을 다룬다. 곱 무대에서 공집합이 만드는 예외는 이후에도 반복해서 등장한다.

문제 10#

접근. C5주차의 평가 절차를 순서대로 돌린다. ① 명제 자체는 참인가 — 참이다 (훈련 2에서 증명했다). 명제가 참이므로 결함은 논증에 있고, ② 각 줄이 앞 줄에서 따라오는지를 검사하면 첫 줄에서 결함이 발견된다. 판정은 “틀림(어느 줄, 왜)”이며, 반례로 그 줄이 성립하지 않음을 뒷받침한 뒤 올바른 증명을 제시한다.

풀이. 틀림 — 첫 줄이 오류다. “\(a \equiv b \pmod n\)이므로 \(a = b\)이다”는 근거 없는 비약이다. 합동은 상등이 아니라 “차가 \(n\)의 배수”라는 관계이므로 \(a \neq b\)인 합동 쌍이 얼마든지 있다 — \(3 \equiv 8 \pmod 5\)이지만 \(3 \neq 8\)이다. 이 줄이 성립한다면 법 \(n\)의 합동은 상등과 같아지고 §1.2의 나머지 계산도 무의미해진다. 명제 자체는 참이므로 판정은 “명제는 참이나 제시된 증명은 틀림”이다. 올바른 증명: \(a, b\)를 정수, \(n\)을 양의 정수라 하고 \(a \equiv b \pmod n\)이라 하자. 정의 6.2와 6.1에 의해 \(a - b = ns\)인 정수 \(s\)가 존재한다. 그러면

\[ a^2 - b^2 = (a - b)(a + b) = ns(a+b) \]

이고 \(s(a+b)\)는 정수이므로 \(n \mid (a^2 - b^2)\), 곧 \(a^2 \equiv b^2 \pmod n\)이다. \(\blacksquare\) (또는 (C5)에 \(c = a\), \(d = b\)를 대입해 한 줄로 얻는다.)

복기. 결론이 참인 증명에도 틀린 줄이 있을 수 있다. 평가 절차 ①에서 “명제가 참”이 나왔다고 평가가 끝나는 것이 아니라, 거기서부터 줄 검사가 시작된다.

문제 11#

접근. 정의를 풀면 \(b = ak\)가 나오고 절댓값을 씌우면 \(\lvert b \rvert = \lvert a \rvert \lvert k \rvert\)이다. 이 문제의 진짜 걸음은 “\(k \neq 0\)”을 확보하는 자리다 — \(b \neq 0\)이라는 가정이 여기서 소비된다. 그리고 “0이 아닌 정수의 절댓값은 1 이상”이라는 사실은 \(k\)가 정수라는 자격에서 온다.

풀이. 정수 \(a, b\)에 대해 \(a \mid b\)이고 \(b \neq 0\)이라 하자. 정의 6.1에 의해 \(b = ak\)인 정수 \(k\)가 존재한다. 만약 \(k = 0\)이면 \(b = a \cdot 0 = 0\)이 되어 가정 \(b \neq 0\)에 어긋나므로 \(k \neq 0\)이다. \(k\)는 0이 아닌 정수이므로 \(\lvert k \rvert \ge 1\)이다. 여기서 쓰는 절댓값의 곱셈 성질 \(\lvert xy \rvert = \lvert x \rvert \lvert y \rvert\)는 §1.7의 네 칸 어디에도 없는 실수의 기본 성질이므로, 근거 목록을 늘리지 않고 이 한 줄에서 인정하고 쓴다. 그러면

\[ \lvert b \rvert = \lvert ak \rvert = \lvert a \rvert \lvert k \rvert \ge \lvert a \rvert \cdot 1 = \lvert a \rvert \]

이다. 따라서 \(\lvert a \rvert \le \lvert b \rvert\)이다. \(\blacksquare\)

복기. 부등식으로 넘어가는 마지막 줄에서 \(\lvert a \rvert \ge 0\)이 필요하다 — \(\lvert a \rvert \lvert k \rvert \ge \lvert a \rvert \cdot 1\)은 음이 아닌 수를 곱할 때만 방향이 보존되기 때문이다. 이 성질은 (D3)이 되었으므로 이후 인용할 수 있다. 쓸모: 어떤 수의 약수를 찾을 때 그 수보다 큰 후보를 검사할 필요가 없다는 보장이 여기서 나온다. 검산: \(3 \mid 12\)이고 \(3 \le 12\) ✓. \(-4 \mid 8\)이고 \(4 \le 8\) ✓.

문제 12#

접근. 다섯 값을 각각 계산하되, 계산마다 “몇에서 몇을 빼면 5의 배수인가”를 함께 적는다. 그것이 정의 6.2를 실제로 확인하는 줄이다. \(4^5\)은 값이 크므로 \(4 \equiv -1 \pmod 5\)로 갈아 끼우면 값을 구하지 않고 답이 나온다.

풀이. \(a = 0\): \(0^5 = 0\)이고 \(0 - 0 = 0 = 5 \times 0\)이므로 \(0^5 \equiv 0 \pmod 5\). \(a = 1\): \(1^5 = 1\)이고 \(1 - 1 = 0\)이므로 \(1^5 \equiv 1 \pmod 5\). \(a = 2\): \(2^5 = 32\)이고 \(32 - 2 = 30 = 5 \times 6\)이므로 \(2^5 \equiv 2 \pmod 5\). \(a = 3\): \(3^5 = 243\)이고 \(243 - 3 = 240 = 5 \times 48\)이므로 \(3^5 \equiv 3 \pmod 5\). \(a = 4\): \(4 - (-1) = 5\)이므로 \(4 \equiv -1 \pmod 5\)이고, 거듭제곱 보존에 의해 \(4^5 \equiv (-1)^5 = -1 \equiv 4 \pmod 5\)이다. 값으로 확인하면 \(4^5 = 1024\)이고 \(1024 - 4 = 1020 = 5 \times 204\)이다. 다섯 나머지 전부에서 \(a^5 \equiv a \pmod 5\)가 성립한다. \(\blacksquare\)

복기. 임의의 정수 \(a\)는 법 5에서 이 다섯 값 중 하나와 합동이므로(나눗셈 정리), 다섯 경우의 확인이 곧 모든 정수에 대한 확인이 된다 — 유한 개의 경우로 무한 개를 덮는 것이 합동 계산의 실제 이득이다. 다만 그 이월에도 인용할 번호가 있다: \(a \equiv r \pmod 5\)이면 거듭제곱 보존에 의해 \(a^5 \equiv r^5\)이고, 위에서 확인한 \(r^5 \equiv r\)과 (C3)으로 이어 \(a^5 \equiv r\)을 얻으며, (C2)로 \(r \equiv a\)를 붙인 뒤 다시 (C3)을 쓰면 \(a^5 \equiv a\)가 된다. 일반형 “\(a^p \equiv a \pmod p\)”(페르마의 소정리)는 C15주차의 몫이다. \(a = 4\)의 처리가 보여 주듯, 대표를 음수로 잡으면 거듭제곱이 부호 계산으로 줄어든다.

문제 13#

접근. 예제 2.3과 두 파트 구조가 같고 다른 것은 “이고”가 “또는”으로 바뀐 것뿐이다. “또는”이 가정 쪽에 나타나면 경우로 쪼갠다(S15주차의 경우법). 두 경우 각각에서 도착점에 이르는지 확인하고, 경우들이 전체를 덮는지도 한 줄로 밝힌다.

풀이. (\(\subseteq\)) \((x, y) \in A \times (B \cup C)\)라 하자. 정의 6.3에 의해 \(x \in A\)이고 \(y \in B \cup C\)이므로, 합집합의 정의에 의해 \(y \in B\) 또는 \(y \in C\)이다. 경우 1: \(y \in B\). 그러면 \(x \in A\)이고 \(y \in B\)이므로 정의 6.3에 의해 \((x,y) \in A \times B\)이다. 경우 2: \(y \in C\). 그러면 \(x \in A\)이고 \(y \in C\)이므로 정의 6.3에 의해 \((x,y) \in A \times C\)이다. 두 경우가 전체를 덮고 어느 경우든 \((x,y)\)가 두 집합 중 하나에 속하므로 \((x,y) \in (A \times B) \cup (A \times C)\)이다. (\(\supseteq\)) \((x, y) \in (A \times B) \cup (A \times C)\)라 하자. 합집합의 정의에 의해 \((x,y) \in A \times B\) 또는 \((x,y) \in A \times C\)이다. 앞의 경우 정의 6.3에 의해 \(x \in A\)이고 \(y \in B\)이므로 \(y \in B \cup C\)이고, 뒤의 경우 \(x \in A\)이고 \(y \in C\)이므로 역시 \(y \in B \cup C\)이다. 어느 경우든 \(x \in A\)이고 \(y \in B \cup C\)이므로 정의 6.3에 의해 \((x,y) \in A \times (B \cup C)\)이다. 양방향 포함이 성립하므로 \(A \times (B \cup C) = (A \times B) \cup (A \times C)\)이다. \(\blacksquare\)

복기. 경우 나누기의 채점 기준은 두 가지다 — ① 경우들이 전체를 빠짐없이 덮는가 ② 각 경우가 각각 완결되는가. 여기서는 합집합의 정의가 “또는”을 그대로 주므로 ①이 공짜이고, ②만 확인하면 된다. 예제 2.3에서 “이고”였던 자리가 “또는”이 되자 파트마다 경우가 둘로 늘었을 뿐 걸음의 배치는 그대로다.

문제 14#

접근. 원명제를 직접 시도하면 걸음 ②에서 막힌다 — “\(3 \nmid n^2\)”은 부정형이라 꺼낼 등식이 없다. S12주차의 판정 신호에 따라 대우로 돌린다. 대우 “\(3 \mid n\)이면 \(3 \mid n^2\)”은 가정이 긍정형이라 정의가 즉시 풀린다.

풀이. 원명제의 대우는 “\(3 \mid n\)이면 \(3 \mid n^2\)”이다. 이것을 직접 증명한다. \(3 \mid n\)이라 하자. 정의 6.1에 의해 \(n = 3k\)인 정수 \(k\)가 존재한다. 목표는 \(n^2\)을 “\(3 \times (\text{정수})\)” 꼴로 만드는 것이다. 그러면

\[ n^2 = (3k)^2 = 9k^2 = 3(3k^2) \]

이고 \(3k^2\)은 정수이므로 정의 6.1에 의해 \(3 \mid n^2\)이다. 대우가 증명되었고 조건문은 대우와 논리적으로 동치이므로(C3주차), 원명제 “\(3 \nmid n^2\)이면 \(3 \nmid n\)”이 성립한다. \(\blacksquare\)

복기. 기법 선택의 이유를 답안에 적는 것까지가 이 문제의 요구다. 가정이 부정형이면 걸음 ②의 공급처가 비어 있고, 대우를 취하면 부정이 결론 쪽으로 옮겨 가면서 가정 자리에 긍정형이 들어온다. 같은 신호가 1권 19주차와 S12주차에서 반복해서 쓰였다.

문제 15#

접근. 도착점은 \(6 \mid (n^3 - n)\)이다. \(n^3 - n\)을 인수분해해 연속 세 정수의 곱으로 만든 뒤, 2의 배수임과 3의 배수임을 따로 확보하고 마지막에 합친다. 3의 배수 쪽은 나눗셈 정리로 \(n\)을 세 경우로 나누면 매 경우 셋 중 누가 3의 배수인지 지목할 수 있다.

풀이. \(n\)을 양의 정수라 하자. 목표는 \(n^3 - n\)이 “\(6 \times (\text{정수})\)” 꼴임을 보이는 것이다. 먼저 인수분해하면

\[ n^3 - n = n(n^2 - 1) = (n-1)n(n+1) \]

이다. 2의 배수임. \(n(n+1)\)은 연속한 두 정수의 곱이므로 짝수이고(1권 1주차 문제 16), \(n(n+1) = 2u\)인 정수 \(u\)가 존재한다. 그러면 \((n-1)n(n+1) = (n-1) \cdot 2u = 2\big((n-1)u\big)\) 이고 \((n-1)u\)는 정수이므로 \(2 \mid (n^3 - n)\)이다. 3의 배수임. 나눗셈 정리에 의해 \(n = 3q\), \(n = 3q+1\), \(n = 3q+2\) 중 하나인 정수 \(q\)가 존재한다. \(n = 3q\)이면 \(n\) 자신이 3의 배수이고, \(n = 3q+1\)이면 \(n - 1 = 3q\)가 3의 배수이며, \(n = 3q+2\)이면 \(n + 1 = 3q + 3 = 3(q+1)\)이 3의 배수다 (S15주차 문제 19). 어느 경우든 세 인수 중 하나가 \(3 \times (\text{정수})\) 꼴이므로, 그 인수를 대입해 나머지 두 인수와 묶으면 \((n-1)n(n+1) = 3 \times (\text{정수})\)가 되어 \(3 \mid (n^3 - n)\)이다. 합치기. \(2 \mid (n^3-n)\)이고 \(3 \mid (n^3-n)\)이므로, 1권 20주차 문제 13에 의해 \(6 \mid (n^3 - n)\)이다. 따라서 정의 6.2에 의해 \(n^3 \equiv n \pmod 6\)이다. \(\blacksquare\)

복기. S17주차 문제 13이 같은 명제를 “\(n^3 - n\)이 6의 배수”라는 나눗셈의 언어로 다뤘고, 이번 문제는 그것을 합동으로 재서술한 것이다. “2의 배수이고 3의 배수이면 6의 배수”는 2와 3이 서로소이기에 성립하는 것이지 일반 법칙이 아니다(§4 도입 상자). 이 문제의 뼈대 — 큰 법을 서로소인 작은 법들로 쪼개 각각에서 확인하고 합치기 — 는 C15주차에서 중국인 나머지 정리라는 이름을 얻는다. 검산: \(n = 4\)이면 \(n^3 - n = 60 = 6 \times 10\) ✓. \(n = 5\)이면 \(120 = 6 \times 20\) ✓.

문제 16#

접근. 세 겹이다. 먼저 \(10 \equiv 1 \pmod 9\)을 정의로 확인하고, \(i \ge 1\)에서는 거듭제곱 보존으로 \(10^i \equiv 1\)을 얻고(\(i = 0\)은 (C1)로 따로 처리한다), (C5)로 \(d_i 10^i \equiv d_i\)를 얻은 뒤 (C4)로 항을 합친다. 마지막 “따라서 9의 배수 판정” 문장은 별도의 논증이 필요하다 — 합동식 하나에서 두 배수 판정이 서로를 결정한다는 것은 (D2)로 나온다.

풀이. \(n = \sum_{i=0}^{m} d_i 10^i\)이라 하자. ① \(10 - 1 = 9\)이고 \(9 \mid 9\)이므로 정의 6.2에 의해 \(10 \equiv 1 \pmod 9\)이다. ② \(i = 0\)일 때는 \(10^0 = 1\)이므로 (C1)에 의해 \(10^0 \equiv 1 \pmod 9\)이다. \(i \ge 1\)일 때는 거듭제곱 보존에 의해 \(10^i \equiv 1^i = 1 \pmod 9\)이다. 두 경우를 나누는 이유는 §1.5의 거듭제곱 보존이 자연수 지수에 대한 진술이고 이 과정의 자연수는 0을 제외하기 때문이다(1권 3주차의 기호 표). 십진 전개에는 \(d_0 \cdot 10^0\) 항이 반드시 있으므로 \(i = 0\)은 실제로 쓰이는 경우다. ③ (C1)에 의해 \(d_i \equiv d_i \pmod 9\)이므로, ②와 함께 (C5)를 적용하면 \(d_i 10^i \equiv d_i \cdot 1 = d_i \pmod 9\)이다. ④ ③의 합동식 \(m+1\)개에 (C4)를 반복 적용하면

\[ n = \sum_{i=0}^{m} d_i 10^i \equiv \sum_{i=0}^{m} d_i \pmod 9 \]

이다. 곧 \(9 \mid \left(n - \sum_i d_i\right)\)이다. ⑤ 자리합을 \(S = \sum_i d_i\)라 두자. \(9 \mid (n - S)\)이다. \(9 \mid n\)이면 \(9 \mid n\)과 \(9 \mid (n-S)\)에 (D2)를 \(x = 1\), \(y = -1\)로 적용해 \(9 \mid \big(n - (n - S)\big) = S\)를 얻는다. 거꾸로 \(9 \mid S\)이면 \(9 \mid S\)와 \(9 \mid (n-S)\)에 (D2)를 \(x = y = 1\)로 적용해 \(9 \mid n\)을 얻는다. 따라서 \(n\)이 9의 배수인 것과 자리합이 9의 배수인 것은 서로 동치이다. \(\blacksquare\)

복기. 판정법의 엔진은 \(10 \equiv 1 \pmod 9\) 한 줄이다. 법 3에서도 \(10 \equiv 1\)이 성립하므로 같은 논증이 3의 배수 판정법을 준다 — C4주차 문제 19가 두 자리 수에서 증명한 특성화의 일반형이 이것이다. 법 11에서는 \(10 \equiv -1\)이므로 자리합 대신 교대합 판정법이 나온다. 검산: \(n = 4703\)이면 자리합은 \(4+7+0+3 = 14\)이고 둘 다 9의 배수가 아니다. \(n = 4707\)이면 자리합 18이 9의 배수이고 \(4707 = 9 \times 523\) ✓.

문제 17#

접근. (\(\supseteq\)) 방향이 이 문제의 전부다. \((x,y) \notin B \times C\)를 정의 6.3으로 풀면 “\(x \in B\)이고 \(y \in C\)”의 부정이므로, 부정 규칙에 의해 “\(x \notin B\) 또는 \(y \notin C\)”가 나온다. 그런데 같은 줄에서 이미 \(y \in C\)를 확보했으므로 “또는”의 뒤쪽이 지워지고 \(x \notin B\)가 확정된다.

풀이. (\(\subseteq\)) \((x, y) \in (A - B) \times C\)라 하자. 정의 6.3에 의해 \(x \in A - B\)이고 \(y \in C\)이며, 차집합의 정의에 의해 \(x \in A\)이고 \(x \notin B\)이다. \(x \in A\)이고 \(y \in C\)이므로 정의 6.3에 의해 \((x,y) \in A \times C\)이다. 또 \((x,y) \in B \times C\)라면 정의 6.3에 의해 \(x \in B\)가 되어 \(x \notin B\)에 어긋나므로 \((x,y) \notin B \times C\)이다. 따라서 차집합의 정의에 의해 \((x,y) \in (A \times C) - (B \times C)\)이다. (\(\supseteq\)) \((x, y) \in (A \times C) - (B \times C)\)라 하자. 차집합의 정의에 의해 \((x,y) \in A \times C\)이고 \((x,y) \notin B \times C\)이다. 앞쪽에서 정의 6.3에 의해 \(x \in A\)이고 \(y \in C\)이다. 뒤쪽을 정의 6.3과 부정 규칙으로 풀면 “\(x \notin B\) 또는 \(y \notin C\)”인데, 이미 \(y \in C\)이므로 뒤쪽 선택지는 성립할 수 없고 \(x \notin B\)가 남는다. 그러면 \(x \in A\)이고 \(x \notin B\)이므로 \(x \in A - B\)이고, \(y \in C\)이므로 정의 6.3에 의해 \((x,y) \in (A - B) \times C\)이다. 양방향 포함이 성립하므로 \((A - B) \times C = (A \times C) - (B \times C)\)이다. \(\blacksquare\)

복기. “또는”에서 한쪽을 지워 다른 쪽을 확정하는 걸음의 이름은 선언 삼단논법이고, S15주차의 분류로는 한 케이스가 모순으로 배제되는 경우법이다. 걸음을 두 줄로 적으면 이렇다 — 경우 1: \(x \notin B\) — 목표에 도달한다. 경우 2: \(y \notin C\) — 이미 확보한 \(y \in C\)와 모순이므로 이 경우는 일어나지 않는다. S15주차의 소거법은 결론의 \(\lor\)에 붙는 도구이므로 여기에는 쓰지 않는다(정의 15.2) — 여기의 \(\lor\)는 결론이 아니라 이미 손에 든 사실이다. 집합 무대에서 부정이 등장하면 거의 언제나 이 걸음이 따라온다. 검산: \(A = \{1,2\}\), \(B = \{2\}\), \(C = \{9\}\)이면 좌변은 \(\{(1,9)\}\)이고, 우변은 \(\{(1,9),(2,9)\} - \{(2,9)\} = \{(1,9)\}\) ✓.

문제 18#

접근. 증명의 줄을 검사하기 전에 평가 절차 ①을 먼저 돌린다. 명제가 거짓이면 어떤 논증도 옳을 수 없으므로 반례 하나가 평가를 끝낸다. 반례는 \(bc\)가 \(a\)의 배수가 되면서 \(b\)와 \(c\) 각각은 \(a\)보다 작은 경우를 노리면 나온다 — (D3)에 의해 \(a\)보다 작은 0이 아닌 수는 \(a\)로 나누어지지 않기 때문이다.

풀이. 틀림 — 명제 자체가 거짓이다. 평가 절차 ①에서 이미 탈락한다. 반례: \(a = 4\), \(b = 2\), \(c = 2\). 이때 \(bc = 4\)이고 \(4 = 4 \times 1\)이므로 \(4 \mid bc\)가 성립한다. 그러나 \(2 = 4k\)인 정수 \(k\)는 없으므로(\(k = 0.5\)는 정수가 아니다) \(4 \nmid 2\)이고, \(b\)와 \(c\) 어느 쪽도 4로 나누어지지 않는다. 따라서 명제는 거짓이다. 제시된 증명의 결함도 지적할 수 있다. 첫 줄 “\(a \mid bc\)이므로 \(bc = ak\)”는 정의 6.1의 정확한 적용이라 옳다. 둘째 줄 “따라서 \(a\)가 \(b\)나 \(c\) 중 하나를 나눈다”가 근거 없는 비약이다 — \(bc = ak\)라는 등식은 \(a\)의 인수가 \(b\)와 \(c\)에 어떻게 흩어져 있는지에 대해 아무것도 말하지 않는다. 반례에서는 \(a = 4\)의 인수 2가 \(b\)와 \(c\)에 하나씩 나뉘어 들어가 있어 어느 쪽도 4를 채우지 못한다. 이 성질은 \(a\)가 소수일 때만 참이고, 그것이 유클리드 보조정리다 (S15주차 문제 10). 제시된 명제는 그 조건이 누락된 형태다.

복기. 조건이 하나 빠진 거짓 명제는 참인 정리와 겉모습이 거의 같아서 반례를 찾기 전에는 그럴듯해 보인다. 평가 절차 ①이 맨 앞에 있는 이유가 이것이다 — 줄 검사에 들어가기 전에 작은 수 몇 개로 명제를 두들겨 보는 것이 가장 싸다.

문제 19#

접근. 앞부분은 네 경우를 나눈 뒤 각 경우에 거듭제곱 보존을 쓰면 끝난다. 경우가 전체를 덮는 근거는 나눗셈 정리다. 뒷부분은 등식 \(x^2 + y^2 = 3\)의 양변을 법 4에서 읽는 것이 전부다 — 같은 수는 어느 법에서도 자기 자신과 합동이므로((C1)), 좌변이 가질 수 있는 값의 집합과 우변의 값을 비교하면 충돌이 드러난다.

풀이. 앞부분. \(a\)를 정수라 하자. 나눗셈 정리에 의해 \(a = 4q + r\)이고 \(r \in \{0,1,2,3\}\)인 정수 \(q, r\)이 존재하므로, \(a \equiv 0, 1, 2, 3 \pmod 4\) 중 하나가 성립한다. 각 경우에 거듭제곱 보존을 적용한다. \(a \equiv 0\)이면 \(a^2 \equiv 0^2 = 0 \pmod 4\). \(a \equiv 1\)이면 \(a^2 \equiv 1^2 = 1 \pmod 4\). \(a \equiv 2\)이면 \(a^2 \equiv 2^2 = 4 \equiv 0 \pmod 4\). \(a \equiv 3\)이면 \(a^2 \equiv 3^2 = 9 \equiv 1 \pmod 4\). 네 경우가 전체를 덮고 어느 경우든 \(a^2 \equiv 0\) 또는 \(a^2 \equiv 1 \pmod 4\)이다. \(\blacksquare\) 뒷부분. \(x^2 + y^2 = 3\)인 정수 \(x, y\)가 존재한다고 하자. 앞부분에 의해 \(x^2 \equiv 0\) 또는 \(1\)이고 \(y^2 \equiv 0\) 또는 \(1 \pmod 4\)이다. (C4)에 의해 \(x^2 + y^2\)은 법 4에서 \(0 + 0 = 0\), \(0 + 1 = 1\), \(1 + 0 = 1\), \(1 + 1 = 2\) 중 하나와 합동이므로, \(x^2 + y^2 \equiv 0\), \(1\), 또는 \(2 \pmod 4\)이다. 한편 \(x^2 + y^2 = 3\)이고 (C1)에 의해 \(3 \equiv 3 \pmod 4\)이므로 \(x^2 + y^2 \equiv 3 \pmod 4\)여야 한다. 그런데 \(3\)은 \(0, 1, 2\) 중 어느 것과도 법 4에서 합동이 아니다(\(3-0=3\), \(3-1=2\), \(3-2=1\) 중 어느 것도 4의 배수가 아니다). 이는 모순이므로 그런 정수 \(x, y\)는 존재하지 않는다. \(\blacksquare\)

복기. 부재를 보이는 표준 수법이다 — 해가 있다고 가정한 뒤 적당한 법에서 양변을 읽어 가능한 값의 집합을 충돌시킨다. 법을 무엇으로 잡는지가 전부이고, 제곱이 등장하면 법 4나 법 8이 첫 후보다(제곱이 법 4에서 두 값, 법 8에서 세 값만 갖기 때문이다). S11주차 예제 2.2가 같은 종류의 부재 증명을 다른 소재로 다뤘고, 그때 경우 나누기로 처리한 자리를 여기서는 합동 한 줄이 대신한다.

문제 20#

접근. (a)는 “무엇이 보존되고 무엇이 보존되지 않는가”를 함께 적어야 완결이다 — 확인 8이 그 경계다. 예제 2.2가 증명한 것이 정확히 무엇인지부터 적고, 그 결과로 가능해진 계산을 하나 들면 세 문장이 채워진다. (b)는 §1.6의 대조표에서 어느 칸이 무대마다 달라지고 어느 칸이 같은지를 압축한다.

풀이. (예시 답안) (a) 예제 2.2에서 곱 보존 (C5)를, 문제 7에서 합 보존 (C4)를 증명했고, 이 둘 덕분에 합동식은 등식처럼 양변에 더하고 곱할 수 있다 — \(a \equiv b\)이면 계산의 어느 자리에서든 \(a\)를 \(b\)로 갈아 끼워도 법 \(n\)에서의 결과가 바뀌지 않는다. 그래서 \(7^{100} \pmod 4\) 같은 계산은 \(7\)을 그와 합동인 작은 대표 \(-1\)로 바꿔 \((-1)^{100} = 1\)로 즉시 끝나고, 85자리 수를 한 번도 적지 않는다. 다만 보존되는 것은 덧셈과 곱셈뿐이며 나눗셈은 보존되지 않으므로(\(6 \equiv 2 \pmod 4\)의 양변을 2로 나누면 거짓이 된다), 합동을 등식처럼 다룰 권리는 (C4)(C5)가 증명해 둔 만큼만 주어진다. (b) 나눗셈에서는 “\(b = ak\) 꼴”을, 합동에서는 “\(a - b = ns\) 꼴”을, 곱에서는 “순서쌍을 두 좌표로 분해”를 각각 걸음 ②에서 받고 걸음 ③에서 만들어야 할 꼴로 적는데, 이 두 칸의 내용만 무대마다 다르고 걸음의 배치 자체는 다섯 걸음 그대로다. 곧 무대를 옮길 때 갈아 끼우는 것은 ①에서 지목하는 정의와 ④에서 쓰는 대수의 종류뿐이며, 가정을 정의로 풀어 재료를 얻고 목표를 정의 꼴로 제작한다는 엔진은 다섯 무대에서 같다.

복기. (a)와 (b)는 같은 물음의 두 층이다 — (a)는 한 무대 안에서 무엇이 보존되는지를 묻고, (b)는 무대를 옮길 때 무엇이 보존되는지를 묻는다. 서술 문제의 채점은 주장의 수가 아니라 그 주장을 떠받치는 자리(예제 2.2, 확인 8, §1.6의 대조표)를 지목했는지로 한다.

다음 주 예고 (C7주차): Chartrand 5장 — 반례\(\cdot\)귀류\(\cdot\)존재. 이번 주 문제 18에서 반례 하나로 명제를 무너뜨린 작업과 문제 19에서 부재를 보인 작업이 각각 정식 기법으로 승격된다. 1권 21\(\cdot\)26\(\cdot\)29주차와 1학기 S5주차(구성법)\(\cdot\)S11주차(귀류)를 Chartrand의 언어로 재조직하고, prove-or-disprove의 전주곡으로 반례 만들기를 익힌 뒤, 존재 증명(구성적\(\cdot\)비구성적)과 유일성을 다룬다. 무대 이동 절차는 그대로 남고 걸음 ③의 도착점이 “모순”이나 “증인”으로 갈릴 뿐이다. 원서 5장을 통독하고 온다.