C6주차 — 직접 증명 심화: 나눗셈·합동·실수·집합·곱

C6주차 — 직접 증명 심화: 나눗셈·합동·실수·집합·곱#

이 주의 길잡이

핵심 문장: 무대가 바뀌어도 증명의 엔진은 그대로다 — 갈아 끼우는 것은 펼칠 정의 하나뿐이고, 합동은 그 갈아 끼우기가 계산 도구까지 되는 첫 무대다.

이 주의 위치: 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\)크기)을 백지에 쓰고 각각을 직접 증명으로 세울 수 있다.

  2. 합동 \(a \equiv b \pmod n\)의 정의를 조각 단위로 해부하고, 합동의 대수 (C1)~(C5)를 계산 도구로 인용해 큰 수의 나머지를 작은 대표로 갈아 끼울 수 있다.

  3. 무대 이동 절차의 다섯 걸음을 쓰고, 각 걸음을 뺐을 때 무엇이 무너지는지 사례로 설명할 수 있다.

  4. 나눗셈\(\cdot\)합동\(\cdot\)실수 부등식\(\cdot\)집합 포함\(\cdot\)데카르트 곱의 다섯 무대에서, 펼칠 정의만 갈아 끼워 같은 절차를 돌릴 수 있다.

  5. 제시된 증명을 C5주차의 증명 평가 절차로 판정하고, 명제 자체가 거짓인 경우와 논증만 결함인 경우를 구분할 수 있다.

본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

준비 운동 (C5주차 · 1권 2주차 · 1권 20주차 복습)#

노트에 먼저 적은 뒤 아래를 읽는다.

  1. C5주차의 증명 평가 절차 다섯 걸음과, 자명한 증명\(\cdot\)공허한 증명의 정의를 쓰시오.

  2. 1권 2주차 정의 2.1(나누어떨어짐)과 1권 20주차 정의 20.1(합동)을 조각 그대로 쓰시오.

  3. 1권 20주차 §1.5의 합동 기본 성질 (C1)~(C5) 다섯 줄과, 1권 27주차 §1.4의 세 가지 증명 목표와 서식 표를 재현하시오.

  4. 다음 두 명제의 증명을 각각 끝까지 적고, 두 증명이 어디까지 같고 어디서 갈라지는지 표시하시오.

(가) 정수 \(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주차의 나눗셈 정리다. 그것만으로 다음 과제를 밀어붙여 보자.

시도 — 나눗셈 정리만으로 큰 수의 나머지 구하기

과제: \(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번 한 뒤에야 나눗셈이 시작된다.

확인 1. 멈춘 자리에서 계산을 끝내려면 어떤 종류의 규칙이 필요한가. “…를 계산하지 않고도 …만 따로 계산할 수 있다” 꼴로 한 구절 적어 보자.

답

“값을 계산하지 않고도 나머지만 따로 계산할 수 있다”는 규칙이다. 곧

곱셈이 나머지의 세계에서도 작동해야 한다 — \(7 \times 7\)의 나머지가 7의 나머지끼리

곱한 것의 나머지와 같다는 보장이 있어야 99번의 곱셈을 한 자리 수의 곱셈으로

갈아 끼울 수 있다. “나머지가 반복될 것 같다”고 답했다면 그 관찰은 옳다. 문제는

그것이 아직 관찰일 뿐 인용할 수 있는 정리가 아니라는 것이다.

이 주 전반부의 기준

나눗셈 정리는 나머지가 존재한다는 것만 보장한다. 나머지를 계산하려면 나머지의 세계에 덧셈과 곱셈이 옮겨 실린다는 별도의 보장이 필요하고, 그 보장을 묶어 놓은 것이 합동의 대수다.

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\)

확인 2. 표의 빈칸 (1)(2)(3)을 채우고, 셋째 열과 넷째 열을 비교해 한 문장으로 관찰을 적어 보자.

답

(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으로 같고, 그 뒤로는 나머지 열이 갈라지지 않는다.

확인 3. 위 관찰을 인정하면 \(7^{100}\)을 4로 나눈 나머지를 계산할 수 있는가. 계산해 보자.

답

계산할 수 있다. 셋째 열이 \(3, 1, 3, 1, \dots\)로 반복하므로 지수가 짝수일 때

나머지는 1이다. \(100\)은 짝수이므로 \(7^{100}\)을 4로 나눈 나머지는 \(1\)이다.

85자리 수를 한 번도 적지 않고 답이 나왔다. 남은 일은 “반복하는 것처럼 보인다”를

인용 가능한 정리로 바꾸는 것이다.

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 “나머지가 같다”라고 부른 관계에 기호를 주고, 그 관계가 곱셈\(\cdot\)덧셈과 어떻게 어울리는지를 정리로 못 박을 뿐이다. 먼저 두 정의를 이번 주의 형태로 다시 세운다.

정의 6.1 — 나누어떨어짐 (divides) [백지 암기 대상]#

정수 \(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\)는 막대에 빗금을 그은 것으로 “나누지 않는다”이다.

백지 암기 대상

나눗셈의 기본 성질

정수 \(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) [백지 암기 대상]#

정수 \(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\)으로 쓴다.

백지 암기 대상

합동의 대수 (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) [백지 암기 대상]#

집합 \(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\)을 한 번도 빠뜨리지 않는다.

확인 4. “\(n \mid (a - b)\)” 조각에서 나눗셈 정의의 “정수 \(k\)”를 “실수 \(k\)”로 바꾸면 정확히 무엇이 무너지는가. \(a = 3\), \(b = 1\), \(n = 5\)로 시험해 보자.

답

임의의 두 정수가 임의의 법에 대해 합동이 된다. \(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가 그 둘을 전진면과 후진면이라 부른 것도 같은 자리다 — 이번 주는 그 두 면 사이에 걸음 ④를 끼워 다섯 무대에서 돌린다.

확인 5. 명제 “\(a \mid b\)이면 \(a \mid b^2\)이다”를 다섯 걸음의 이름만으로 설계해 보자. 각 걸음에 무엇이 들어가는가.

답

① 무대는 나눗셈, 펼칠 정의는 정의 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\)이다.

다섯 칸이 다 채워지면 증명은 이미 완성되어 있고, 남은 일은 문장으로 옮겨 적는 것뿐이다.

확인 6. 걸음 ②와 걸음 ③은 같은 정의를 쓰는데도 방향이 반대다. 나눗셈의 정의에서 각각 무엇을 하는지 한 줄씩 적어 보자.

답

②는 “\(a \mid b\)”라는 이름을 받아 \(b = ak\)라는 등식과 정수 \(k\)를 꺼내 온다.

③은 “\(a \mid c\)”라는 이름을 만들어야 할 목표로 삼아 “\(c = a \times (\text{정수})\)

꼴을 제작한다”로 갈아치운다. 같은 정의가 가정 쪽에서는 재료 공급처이고 목표

쪽에서는 제작 명세서다 (S4주차 §1.4의 전진면\(\cdot\)후진면).

5 합동을 계산 도구로 — 큰 수를 작은 대표로#

(C1)~(C5)가 손에 있으면 §1.2의 관찰이 계산 절차가 된다. 한 조각이 더 필요하다.

거듭제곱 보존

\(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에서 이미 끝났다. 따라서 근거 ④로 출처와 함께 인용한다.

계산의 요령은 하나다. 큰 수를 그와 합동인 작은 대표로 갈아 끼운 뒤 계산한다.

확인 7. \(7 \equiv -1 \pmod 4\)인지 정의 6.2로 판정해 보자. 그리고 그 사실로 \(7^{100} \pmod 4\)를 계산해 보자.

답

\(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\)로

잡은 이유는 부호만 다루면 거듭제곱이 끝나기 때문이다 — 대표는 나머지일 필요가

없고, 합동이기만 하면 계산이 쉬운 쪽을 고른다.

확인 8. 합동식의 양변을 같은 수로 나누는 것은 허용되는가. \(6 \equiv 2 \pmod 4\)의 양변을 2로 나눠 시험해 보자.

답

허용되지 않는다. \(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\)

두 좌표 조건을 갖춘 순서쌍임을 보이기

확인 9. 실수 무대의 명제 “실수 \(a, b\)에 대해 \(a^2 + b^2 \ge 2ab\)”를 위 표의 ②③ 칸에 맞춰 설계해 보자.

이 주의 길잡이

답

③ 후진면: 목표는 차 \(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)이 증명되는 순서대로 들어온다

확인 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\)이다.”

답

(가) 근거 ① — 정의 6.2를 풀고 정의 6.1을 한 겹 더 푼 것이다.

(나) 근거 ④ — (C5)에 \(c \equiv c\)((C1))를 함께 넣은 결과다. “양변에 곱한다”는

등식의 성질(근거 ③)처럼 보이지만, 합동식은 등식이 아니므로 근거 ③이 직접

작동하지 않는다. 인용해야 할 것은 (C5)다.

(다) 불허 — 합동은 상등이 아니다. \(3 \equiv 8 \pmod 5\)이지만 \(3 \neq 8\)이다.

이 줄이 문제 10에서 다시 등장한다.