# C6주차 — 직접 증명 심화: 나눗셈·합동·실수·집합·곱 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 무대가 바뀌어도 증명의 엔진은 그대로다 — 갈아 끼우는 것은 펼칠 정의 하나뿐이고, 합동은 그 갈아 끼우기가 계산 도구까지 되는 첫 무대다. **이 주의 위치**: 2학기 20주의 C6주차. C5주차는 짝수$\cdot$홀수라는 한 무대에서 직접 증명과 대우 증명을 한 무대에서 세웠고, 이번 주는 같은 기법을 다섯 무대(나눗셈$\cdot$합동$\cdot$실수$\cdot$집합$\cdot$곱)로 옮겨 심는다. 1권 2주차의 나누어떨어짐, 1권 20주차의 합동과 (C1)~(C5), 1권 27~28주차의 원소 추적, 1권 6주차의 데카르트 곱은 그때 무대마다 따로 외운 서식이었다. 여기서 그 넷이 하나의 절차로 묶이고 그 절차가 이름을 얻는다. 이번 주에 세워지는 합동 산술은 C11주차의 동치관계와 C15주차의 정수론이 그대로 물려받는다. **원서 대응**: Chartrand 4장 (More on Direct Proof and Proof by Contrapositive). 주간 루틴 1일차에 원서 4장을 통독한 뒤 이 문서로 온다. ::: ## 이번 주 목표 1. 나누어떨어짐 $a \mid b$의 정의와 세 성질(추이$\cdot$선형결합$\cdot$크기)을 백지에 쓰고 각각을 직접 증명으로 세울 수 있다. 1. 합동 $a \equiv b \pmod n$의 정의를 조각 단위로 해부하고, 합동의 대수 (C1)~(C5)를 계산 도구로 인용해 큰 수의 나머지를 작은 대표로 갈아 끼울 수 있다. 1. **무대 이동 절차**의 다섯 걸음을 쓰고, 각 걸음을 뺐을 때 무엇이 무너지는지 사례로 설명할 수 있다. 1. 나눗셈$\cdot$합동$\cdot$실수 부등식$\cdot$집합 포함$\cdot$데카르트 곱의 다섯 무대에서, 펼칠 정의만 갈아 끼워 같은 절차를 돌릴 수 있다. 1. 제시된 증명을 C5주차의 증명 평가 절차로 판정하고, 명제 자체가 거짓인 경우와 논증만 결함인 경우를 구분할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (C5주차 · 1권 2주차 · 1권 20주차 복습) 노트에 먼저 적은 뒤 아래를 읽는다. 1. C5주차의 증명 평가 절차 다섯 걸음과, 자명한 증명$\cdot$공허한 증명의 정의를 쓰시오. 1. 1권 2주차 정의 2.1(나누어떨어짐)과 1권 20주차 정의 20.1(합동)을 조각 그대로 쓰시오. 1. 1권 20주차 §1.5의 합동 기본 성질 (C1)~(C5) 다섯 줄과, 1권 27주차 §1.4의 세 가지 증명 목표와 서식 표를 재현하시오. 1. 다음 두 명제의 증명을 각각 끝까지 적고, 두 증명이 어디까지 같고 어디서 갈라지는지 표시하시오. (가) 정수 $a, b, c$에 대해 $a \mid b$이고 $a \mid c$이면 $a \mid (b + c)$이다. (나) 정수 $a, b, c, d$와 양의 정수 $n$에 대해 $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이면 $a + c \equiv b + d \pmod n$이다. ### 자주 나오는 세 가지 답 4번에서 두 증명을 적는 것까지는 대개 성공하고, "어디까지 같은가"를 물으면 다음 세 유형 중 하나로 답한다. 셋 다 자연스러운 답이고, 셋 다 이번 주가 메울 정확한 간격이 있다. - **유형 1 — 둘은 다른 정리라 비교할 것이 없다.** "(가)는 나눗셈의 정리이고 (나)는 합동의 정리이므로 각각 외운다." 옳은 부분은 분명하다. 두 명제의 진술은 실제로 다르고, 다른 정리로 인용된다. 간격은 **진술을 비교하고 증명을 비교하지 않았다**는 데 있다. 두 증명을 줄 단위로 나란히 놓으면 첫 줄, 둘째 줄, 셋째 줄이 각각 같은 일을 하고 있고, 다른 것은 그 자리에 들어간 정의의 이름뿐이다. 정리를 하나씩 외우는 방식은 무대가 다섯 개가 되는 순간 다섯 배로 늘어난다. - **유형 2 — 합동이 나눗셈의 특수한 경우라 당연히 같다.** "합동의 정의가 $n \mid (a - b)$이므로 (나)는 (가)를 다시 쓴 것이다." 관찰은 옳다. 실제로 (나)의 증명은 합동을 나눗셈으로 한 겹 풀면서 시작한다. 간격은 "같다"가 무엇의 같음인지에 있다. 소재가 겹쳐서 같은 것이라면, 소재가 하나도 겹치지 않는 집합$\cdot$곱 무대에서는 달라져야 한다. 그런데 §2의 예제 2.3에서 보듯 그 무대에서도 걸음의 배치는 같다. 같은 것은 소재가 아니라 **걸음의 배치**다. - **유형 3 — 어느 정의를 어느 방향으로 펼지 판단이 서지 않는다.** 증명은 적었지만 "왜 가정 쪽은 등식으로 풀고 결론 쪽은 꼴을 만드는가"를 물으면 막힌다. 이 답이 이번 주의 어려움을 가장 정확히 짚는다. 실제로 다섯 무대에서 헷갈리는 것의 전부가 그 판단이다. 간격은 그 판단이 임기응변이라고 여기는 데 있다 — §1.4에서 보듯 그것은 다섯 걸음으로 고정된 절차이고, 걸음마다 빼면 무너지는 것이 정해져 있다. ## 개념 — 무대와 엔진 ### 1 나눗셈 정의만으로 밀어붙이면 어디서 막히는가 이번 주의 도구가 왜 필요한지부터 확인한다. 손에 있는 것은 1권 2주차의 나눗셈 정의와 1권 33주차의 나눗셈 정리다. 그것만으로 다음 과제를 밀어붙여 보자. :::{admonition} 시도 — 나눗셈 정리만으로 큰 수의 나머지 구하기 :class: quotebox 과제: $7^{100}$을 4로 나눈 나머지를 구한다. "나눗셈 정리에 의해 $7^{100} = 4q + r$이고 $0 \le r < 4$인 정수 $q, r$이 존재한다. 그런 $q, r$이 있다는 것은 알겠는데, $r$의 값을 알려면 $7^{100}$이 얼마인지 알아야 한다. $7^{100} = 7 \times 7 \times \cdots$ … " ::: 여기서 멈춘다. $7^{100}$은 85자리 수이고, 곱셈을 99번 한 뒤에야 나눗셈이 시작된다. :::{container} quotebox **확인 1.** 멈춘 자리에서 계산을 끝내려면 어떤 **종류**의 규칙이 필요한가. "…를 계산하지 않고도 …만 따로 계산할 수 있다" 꼴로 한 구절 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown "**값을 계산하지 않고도 나머지만 따로 계산할 수 있다**"는 규칙이다. 곧 곱셈이 나머지의 세계에서도 작동해야 한다 — $7 \times 7$의 나머지가 7의 나머지끼리 곱한 것의 나머지와 같다는 보장이 있어야 99번의 곱셈을 한 자리 수의 곱셈으로 갈아 끼울 수 있다. "나머지가 반복될 것 같다"고 답했다면 그 관찰은 옳다. 문제는 그것이 아직 관찰일 뿐 인용할 수 있는 정리가 아니라는 것이다. ::: :::{admonition} 이 주 전반부의 기준 :class: quotebox 나눗셈 정리는 나머지가 **존재한다**는 것만 보장한다. 나머지를 **계산**하려면 나머지의 세계에 덧셈과 곱셈이 옮겨 실린다는 별도의 보장이 필요하고, 그 보장을 묶어 놓은 것이 합동의 대수다. ::: ### 2 나머지의 세계를 표로 확인하기 멈춘 자리에서 관찰만 해 보자. 4로 나눈 나머지가 3으로 같은 두 수 7과 3을 나란히 두고, 거듭제곱의 나머지를 계산해 표를 채운다. | **$k$** | **$7^k$** | **$7^k$을 4로 나눈 나머지** | **$3^k$을 4로 나눈 나머지** | |---|---|---|---| | $1$ | $7$ | $3$ | $3$ | | $2$ | $49$ | $\underline{\quad(1)\quad}$ | $1$ | | $3$ | $343$ | $\underline{\quad(2)\quad}$ | $\underline{\quad(3)\quad}$ | | $4$ | $2401$ | $1$ | $1$ | :::{container} quotebox **확인 2.** 표의 빈칸 (1)(2)(3)을 채우고, 셋째 열과 넷째 열을 비교해 한 문장으로 관찰을 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $49 = 4 \times 12 + 1$이므로 $1$. (2) $343 = 4 \times 85 + 3$이므로 $3$. (3) $27 = 4 \times 6 + 3$이므로 $3$. 셋째 열과 넷째 열이 완전히 같다. 관찰: **처음 두 수의 나머지가 같으면 거듭제곱의 나머지도 같다.** 7과 3은 크기가 전혀 다르지만 4로 나눈 나머지가 3으로 같고, 그 뒤로는 나머지 열이 갈라지지 않는다. ::: :::{container} quotebox **확인 3.** 위 관찰을 인정하면 $7^{100}$을 4로 나눈 나머지를 계산할 수 있는가. 계산해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 계산할 수 있다. 셋째 열이 $3, 1, 3, 1, \dots$로 반복하므로 지수가 짝수일 때 나머지는 1이다. $100$은 짝수이므로 $7^{100}$을 4로 나눈 나머지는 $1$이다. 85자리 수를 한 번도 적지 않고 답이 나왔다. 남은 일은 "반복하는 것처럼 보인다"를 인용 가능한 정리로 바꾸는 것이다. ::: 이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 "나머지가 같다"라고 부른 관계에 기호를 주고, 그 관계가 곱셈$\cdot$덧셈과 어떻게 어울리는지를 정리로 못 박을 뿐이다. 먼저 두 정의를 이번 주의 형태로 다시 세운다. ### 정의 6.1 — 나누어떨어짐 (divides) [백지 암기 대상] :::{container} quotebox 정수 $a, b$에 대해, **$a$가 $b$를 나눈다**($a \mid b$로 표기)는 것은 $b = ak$인 정수 $k$가 존재한다는 뜻이다. 이때 $a$를 $b$의 **약수**, $b$를 $a$의 **배수**라 한다. 나누지 않으면 $a \nmid b$로 쓴다. ::: 기호 $a \mid b$는 "$a$는 $b$를 나눈다"로 읽는다. 세로 막대는 나눗셈 기호가 아니라 **명제를 만드는 기호**다 — $a \mid b$는 수가 아니라 참$\cdot$거짓이 정해지는 문장이다 (1권 2주차 §1.4). $\nmid$는 막대에 빗금을 그은 것으로 "나누지 않는다"이다. :::{admonition} 백지 암기 대상 :class: keybox **나눗셈의 기본 성질** 정수 $a, b, c$에 대해 — (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$이다. ::: 셋 다 이번 주 안에서 증명된다 — (D2)는 예제 2.1, (D1)은 문제 6, (D3)은 문제 11이다. 증명되기 전에는 인용하지 않는다. ### 정의 6.2 — 합동 (congruent modulo n) [백지 암기 대상] :::{container} quotebox 정수 $a, b$와 양의 정수 $n$에 대해, **$a$가 $b$와 법 $n$에 대해 합동**이라는 것은 $n \mid (a - b)$라는 뜻이고, $a \equiv b \pmod n$으로 쓴다. ::: $a \equiv b \pmod n$은 "에이는 비와 법 엔에 대해 합동이다"로 읽는다. 괄호 안의 $\bmod n$은 $a$나 $b$에 붙은 연산이 아니라 **어느 법에서 재는지의 선언**이다. $\equiv$는 등호에 줄이 하나 더 있는 기호로, 나머지의 세계에서 등호가 맡던 자리를 대신한다(1권 20주차 핵심 문장). 합동이 아니면 $a \not\equiv b \pmod n$으로 쓴다. :::{admonition} 백지 암기 대상 :class: keybox **합동의 대수 (C1)~(C5)** 정수 $a, b, c, d$와 양의 정수 $n$에 대해 — (C1) **반사**: $a \equiv a \pmod n$ (C2) **대칭**: $a \equiv b$이면 $b \equiv a \pmod n$ (C3) **추이**: $a \equiv b$이고 $b \equiv c$이면 $a \equiv c \pmod n$ (C4) **합 보존**: $a \equiv b$, $c \equiv d$이면 $a + c \equiv b + d \pmod n$ (C5) **곱 보존**: $a \equiv b$, $c \equiv d$이면 $ac \equiv bd \pmod n$ ::: 다섯 줄의 번호는 1권 20주차 §1.5의 것을 그대로 쓴다. 다섯 줄 전부가 그 주차에서 증명되었으므로 근거 ④로 인용할 수 있다. 이번 주는 그 증명을 Chartrand의 언어로 다시 세우고((C4)는 문제 7, (C5)는 예제 2.2), 그것을 **계산 도구**로 운용한다. ### 정의 6.3 — 데카르트 곱 (Cartesian product) [백지 암기 대상] :::{container} quotebox 집합 $A, B$에 대해 $A \times B = \{(x, y) : x \in A \text{ 이고 } y \in B\}$이다. 곧 $(x, y) \in A \times B$인 것과 "$x \in A$이고 $y \in B$"인 것이 같다. ::: $A \times B$는 "에이 크로스 비"로 읽는다. 원소가 수가 아니라 **순서쌍**이라는 것이 이 무대의 특징이고, 그래서 증명의 첫 문장이 "$x \in \cdots$라 하자"가 아니라 "$(x, y) \in \cdots$라 하자"가 된다(1권 28주차 핵심 문장). ### 3 정의 해부 — 조각마다 하는 일 합동의 정의 한 줄을 조각으로 나눈다. 조각마다 증명에서 맡는 역할이 다르다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "정수 $a, b$" | 판정 대상의 선언 | 두 대상 사이의 관계이지 한 수의 성질이 아니다 | | "양의 정수 $n$" | 법의 자격 제한 | 이 조각이 빠지면 정의가 퇴화하거나 중복된다 (아래 실험 (가)~(다)) | | "$n \mid (a - b)$" | **등식** 제공 | 한 겹 더 풀면 $a - b = nk$인 정수 $k$가 나오고, 계산은 여기서 시작된다 | | "$a - b$" (차의 순서) | 비교 방식의 고정 | 순서를 바꿔 써도 되는 근거는 (C2)이고, 근거 없이 바꿔 쓰지 않는다 | | "$\pmod n$" 표기 | 법을 식에 달고 다닌다 | 이 표기가 빠지면 참$\cdot$거짓이 정해지지 않는다 (아래 실험 (라)) | **조각 삭제 실험 — 법의 자격을 지우면.** "양의 정수"라는 제한을 풀면 세 갈래가 생기는데, 어느 갈래도 새로운 관계를 만들지 못한다. - **(가) $n < 0$을 허용하면 — 표기만 중복된다.** $a - b = nk$인 정수 $k$가 존재하는 것과 $a - b = (-n)(-k)$인 정수 $-k$가 존재하는 것은 같은 조건이므로, $n \mid (a-b)$와 $(-n) \mid (a-b)$는 동치다. 곧 법 $-n$의 합동은 법 $\lvert n \rvert$의 합동과 완전히 같은 관계이고, 음수 법을 허용해 얻는 것은 같은 관계에 이름이 하나 더 붙는 것뿐이다. - **(나) $n = 0$을 허용하면 — 상등으로 퇴화한다.** $0 \mid (a - b)$는 $a - b = 0 \times k$, 곧 $a = b$를 뜻한다. 법 0의 합동은 상등 그 자체이므로 새로운 것을 하나도 주지 않는다. - **(다) $n = 1$은 허용되지만 — 구별력이 0이다.** $1 \mid (a-b)$가 언제나 참이므로 모든 정수가 서로 합동이 되어 아무것도 **구별하지 못한다**. 법을 2 이상의 정수로 쓰는 관례는 세 갈래를 합친 결과다 — 음수는 중복이고 0과 1은 퇴화다. 셋 중 어느 것도 정의를 무너뜨리지는 않는다는 점을 함께 본다. **(라) 진짜로 무너지는 자리 — "$\pmod n$" 표기를 지우면.** 위 세 갈래에서 정의는 퇴화하거나 중복될 뿐 문장이기를 그만두지는 않는다. 문장 자체가 무너지는 조각은 따로 있다. "$17 \equiv 5$"라고만 쓰면 $n = 1, 2, 3, 4, 6, 12$에서는 참이고 $n = 5, 7, 8$에서는 거짓이라 참$\cdot$거짓이 정해지지 않는다 — 명제가 아니게 된다 (1권 20주차 §1.3의 삭제 실험). 그래서 답안에서는 $\pmod n$을 한 번도 빠뜨리지 않는다. :::{container} quotebox **확인 4.** "$n \mid (a - b)$" 조각에서 나눗셈 정의의 "정수 $k$"를 "실수 $k$"로 바꾸면 정확히 무엇이 무너지는가. $a = 3$, $b = 1$, $n = 5$로 시험해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 임의의 두 정수가 임의의 법에 대해 합동이 된다. $3 - 1 = 2 = 5 \times 0.4$이므로 실수 $k$를 허용하면 $5 \mid 2$가 되고 $3 \equiv 1 \pmod 5$가 성립해 버린다. 일반적으로 $a - b = n \times \frac{a-b}{n}$이므로 **모든** 쌍이 합동이 된다. 합동이라는 말이 아무것도 구별하지 못하면 §1.2에서 관찰한 나머지 열의 일치도 아무 정보가 아니게 된다. "정수"라는 자격이 정의의 생명이다. ::: ### 4 무대 이동 절차 — 걸음 해부와 걸음 삭제 실험 이번 주의 새로운 것은 정의가 아니라 **절차**다. 다섯 무대에서 반복되는 걸음을 다섯 개로 잘라 표로 해부한다. | **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** | |---|---|---| | ① 무대 확인 | 명제에 나오는 이름이 어느 정의의 소관인지 지목한다 | 펼칠 정의를 못 고른 채 식만 만지게 된다 — §1.1의 멈춤이 재연된다 | | ② 전진면 | 가정에 있는 이름을 정의로 풀어 등식 또는 원소 조건을 받아 온다 | 계산에 쓸 재료가 없다. "$a \mid b$이므로"에서 다음 줄이 나오지 않는다 | | ③ 후진면 | 목표에 있는 이름을 정의로 풀어 **만들어야 할 꼴**을 먼저 적는다 | 도착점을 모른 채 변형만 하게 되고, 이미 도착한 줄도 알아보지 못한다 (아래 실험) | | ④ 무대의 대수 | ②의 재료를 ③의 꼴에 맞도록 조립한다 (묶기$\cdot$전개$\cdot$다리 놓기) | 재료와 도착점이 손에 있어도 이어지지 않는다 | | ⑤ 자격 확인과 선언 | 꼴 안의 대상이 요구된 자격(정수$\cdot$원소)을 갖췄음을 밝히고 정의를 인용해 닫는다 | 확인 4의 $5 \times 0.4$ 같은 붕괴(정수 자격이 빠지면 아무거나 나눈다)가 재연되고, 정의 꼴에 도달했다는 선언이 없어 증명이 끝나지 않는다 | **걸음 삭제 실험 — ③을 빼면.** (C5)의 증명에서 도착점을 적지 않고 시작해 보자. 가정에서 $a - b = ns$, $c - d = nt$를 받았다. 도착점을 모르는 상태에서는 손에 잡히는 변형을 아무거나 하게 된다 — $a = b + ns$, $c = d + nt$로 옮겨 적고, $ac = (b + ns)(d + nt) = bd + bnt + nsd + n^2st$까지 전개한다. 여기서 무엇을 했는지 판정할 기준이 없다. 반면 걸음 ③을 먼저 밟아 도착점을 "$ac - bd = n \times (\text{정수})$"로 적어 두면, 방금 전개식에서 $bd$를 왼쪽으로 넘겨 $ac - bd = n(bt + sd + nst)$가 되는 것이 곧바로 보이고 증명이 끝난다. 걸음 ③은 계산을 대신해 주지 않지만 **어느 변형이 진전인지 판정하는 기준**을 준다. 1권 2주차 §1.3, 1권 20주차 §1.3, 1권 27주차 §1.4에서 무대마다 따로 외운 "첫 문장과 마지막 문장"이, 여기서 걸음 ②와 걸음 ⑤라는 하나의 이름을 얻는다. S4주차 §1.4가 그 둘을 **전진면**과 **후진면**이라 부른 것도 같은 자리다 — 이번 주는 그 두 면 사이에 걸음 ④를 끼워 다섯 무대에서 돌린다. :::{container} quotebox **확인 5.** 명제 "$a \mid b$이면 $a \mid b^2$이다"를 다섯 걸음의 이름만으로 설계해 보자. 각 걸음에 무엇이 들어가는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 무대는 나눗셈, 펼칠 정의는 정의 6.1이다. ② 전진면: $a \mid b$에서 $b = ak$인 정수 $k$를 받는다. ③ 후진면: 목표 $a \mid b^2$은 "$b^2 = a \times (\text{정수})$" 꼴을 만드는 일이다. ④ 대수: $b^2 = (ak)^2 = a(ak^2)$. ⑤ 자격 확인: $ak^2$은 정수이므로 정의 6.1에 의해 $a \mid b^2$이다. 다섯 칸이 다 채워지면 증명은 이미 완성되어 있고, 남은 일은 문장으로 옮겨 적는 것뿐이다. ::: :::{container} quotebox **확인 6.** 걸음 ②와 걸음 ③은 같은 정의를 쓰는데도 방향이 반대다. 나눗셈의 정의에서 각각 무엇을 하는지 한 줄씩 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown ②는 "$a \mid b$"라는 이름을 받아 $b = ak$라는 등식과 정수 $k$를 **꺼내 온다**. ③은 "$a \mid c$"라는 이름을 만들어야 할 목표로 삼아 "$c = a \times (\text{정수})$ 꼴을 제작한다"로 **갈아치운다**. 같은 정의가 가정 쪽에서는 재료 공급처이고 목표 쪽에서는 제작 명세서다 (S4주차 §1.4의 전진면$\cdot$후진면). ::: ### 5 합동을 계산 도구로 — 큰 수를 작은 대표로 (C1)~(C5)가 손에 있으면 §1.2의 관찰이 계산 절차가 된다. 한 조각이 더 필요하다. :::{admonition} 거듭제곱 보존 :class: quotebox $a \equiv b \pmod n$이면 모든 자연수 $m$에 대해 $a^m \equiv b^m \pmod n$이다. ::: 이 줄은 (C5)를 자기 자신에 반복 적용해 얻는다 — $a \equiv b$에 (C5)를 한 번 쓰면 $a^2 \equiv b^2$, 그 결과에 다시 쓰면 $a^3 \equiv b^3$이다. 반복 자체를 정당화하려면 귀납법이 필요하고, 그 증명은 1권 31주차 문제 13에서 이미 끝났다. 따라서 근거 ④로 출처와 함께 인용한다. 계산의 요령은 하나다. 큰 수를 그와 합동인 **작은 대표**로 갈아 끼운 뒤 계산한다. :::{container} quotebox **확인 7.** $7 \equiv -1 \pmod 4$인지 정의 6.2로 판정해 보자. 그리고 그 사실로 $7^{100} \pmod 4$를 계산해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $7 - (-1) = 8$이고 $8 = 4 \times 2$이므로 $4 \mid 8$, 곧 $7 \equiv -1 \pmod 4$이다. 거듭제곱 보존에 의해 $7^{100} \equiv (-1)^{100} = 1 \pmod 4$이다. §1.2의 표에서 관찰만 했던 것이 인용 가능한 두 줄로 확정되었다. 대표를 $3$이 아니라 $-1$로 잡은 이유는 부호만 다루면 거듭제곱이 끝나기 때문이다 — 대표는 나머지일 필요가 없고, 합동이기만 하면 계산이 쉬운 쪽을 고른다. ::: :::{container} quotebox **확인 8.** 합동식의 양변을 같은 수로 나누는 것은 허용되는가. $6 \equiv 2 \pmod 4$의 양변을 2로 나눠 시험해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 허용되지 않는다. $6 \equiv 2 \pmod 4$는 참이다($6 - 2 = 4$). 양변을 2로 나누면 $3 \equiv 1 \pmod 4$가 되는데 $3 - 1 = 2$이고 $4 \nmid 2$이므로 거짓이다. (C4)와 (C5)는 더하기와 곱하기만 보장하고 나누기는 보장하지 않는다. 목록에 없는 조작은 쓰지 않는다는 원칙이 여기서 실제로 사고를 막는다. ::: ### 6 다섯 무대 대조표 — 갈아 끼우는 것은 정의 하나 같은 절차가 무대마다 어떤 모습이 되는지 한 표로 모은다. 걸음 ②와 ③의 칸만 무대마다 다르고, 절차 자체는 바뀌지 않는다. | **무대** | **펼칠 정의** | **② 전진면이 주는 것** | **③ 후진면이 요구하는 것** | |---|---|---|---| | 나눗셈 | 정의 6.1 | $b = ak$인 정수 $k$ | "$a \times (\text{정수})$" 꼴의 제작 | | 합동 | 정의 6.2 (+ 정의 6.1) | $a - b = ns$인 정수 $s$ | 차가 "$n \times (\text{정수})$"가 되도록 제작 | | 실수 부등식 | 순서와 제곱의 기본 성질 | 가정 부등식과 $t^2 \ge 0$ | 차 $A - B$가 0 이상임을 보이기 | | 집합 포함 | 부분집합의 정의 | 임의로 잡은 원소 $x \in A$ | $x \in B$의 도출 | | 데카르트 곱 | 정의 6.3 | $(x, y)$에서 $x \in A$, $y \in B$ | 두 좌표 조건을 갖춘 순서쌍임을 보이기 | :::{container} quotebox **확인 9.** 실수 무대의 명제 "실수 $a, b$에 대해 $a^2 + b^2 \ge 2ab$"를 위 표의 ②③ 칸에 맞춰 설계해 보자. ::: :::{admonition} 이 주의 길잡이 :class: keybox **답** ③ 후진면: 목표는 차 $a^2 + b^2 - 2ab$가 0 이상임을 보이는 것이다 (1권 16주차 핵심 문장). ② 전진면: 가정으로 주어진 부등식은 없고, 쓸 수 있는 사실은 "실수의 제곱은 0 이상"뿐이다. ④ 대수: $a^2 + b^2 - 2ab = (a - b)^2$. ⑤ $(a-b)^2 \ge 0$이므로 $a^2 + b^2 \ge 2ab$이다. 실수 무대에서는 걸음 ②의 공급처가 정의가 아니라 순서의 기본 성질이라는 것만 다르고(1권 16주차의 부등식 기본 성질 (W1)~(W6)), 걸음의 배치는 그대로다. ::: ### 7 근거 목록 갱신 — 칸은 늘지 않고 ④의 입주자가 늘어난다 증명에서 쓸 수 있는 근거 목록은 1권 이래 네 칸이다. 이번 주에 칸이 늘지는 않는다. | **근거** | **내용** | **이번 주에 달라지는 것** | |---|---|---| | ① 정의 | 약속된 조건 | 정의 6.1$\cdot$6.2$\cdot$6.3이 여기 들어온다 | | ② 닫힘성 | 정수끼리 더하고 빼고 곱하면 정수 | 그대로. 걸음 ⑤에서 매번 인용된다 | | ③ 등식의 성질 | 대입$\cdot$전개$\cdot$묶기 | 그대로. 합동식에는 등식의 성질을 직접 쓸 수 없다 — 반드시 정의로 풀어 등식으로 만든 뒤에 쓴다 | | ④ 이미 증명한 명제 | 증명이 끝난 정리 | (C1)~(C5)와 거듭제곱 보존(1권 20주차$\cdot$31주차 문제 13)이 입주하고, 이번 주에 (D1)~(D3)이 증명되는 순서대로 들어온다 | :::{container} quotebox **확인 10.** 다음 세 줄이 인용한 근거는 ①~④ 중 무엇인가. 허용되지 않는 줄이 있으면 지적해 보자. (가) "$a \equiv b \pmod n$이므로 $a - b = ns$인 정수 $s$가 존재한다." (나) "$a \equiv b \pmod n$이므로 양변에 $c$를 곱해 $ac \equiv bc \pmod n$이다." (다) "$a \equiv b \pmod n$이므로 $a = b$이다." ::: :::{admonition} 답 :class: quotebox dropdown (가) 근거 ① — 정의 6.2를 풀고 정의 6.1을 한 겹 더 푼 것이다. (나) 근거 ④ — (C5)에 $c \equiv c$((C1))를 함께 넣은 결과다. "양변에 곱한다"는 등식의 성질(근거 ③)처럼 보이지만, 합동식은 등식이 아니므로 근거 ③이 직접 작동하지 않는다. 인용해야 할 것은 (C5)다. (다) 불허 — 합동은 상등이 아니다. $3 \equiv 8 \pmod 5$이지만 $3 \neq 8$이다. 이 줄이 문제 10에서 다시 등장한다. :::