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

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

예제 — 판정과 증명을 함께 만들기#

이번 주의 예제는 세 가지 일을 나눠 맡는다. 예제 2.1은 정의로 판정하는 답안을 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 한 뒤 증명을 산문으로 보며, 예제 2.3은 설계부터 혼자 해 본다.

예제 2.1 — 판정은 정의로#

\(91 \equiv 7 \pmod{12}\)인가? \(58 \equiv 5 \pmod 9\)인가?

설계 — 쓰기 전에 정하는 두 가지. 판정 문제에도 출발점과 도착점이 있다. 출발점은 주어진 세 수이고, 도착점은 “정의가 요구하는 등식이 있는가”라는 물음이다. 물음을 정의로 번역해 표에 먼저 적는다.

주어진 것 (출발점)

정의로 번역한 물음 (도착점)

첫째

\(a = 91\), \(b = 7\), \(n = 12\)

\(12 \mid (91 - 7)\)인가, 곧 \(84 = 12 \times (\text{정수})\)인가

둘째

\(a = 58\), \(b = 5\), \(n = 9\)

\(\underline{\qquad(?)\qquad}\)

확인 12. 둘째 행의 빈칸을 채워 보자. 정의 20.1을 그대로 적용하면 무엇을 확인해야 하는가.

답

\(9 \mid (58 - 5)\)인가, 곧 \(53 = 9 \times (\text{정수})\)인가. 판정에서 할 일은

언제나 이 하나다 — 차를 구하고, 그 차가 법의 배수인지 본다. 두 수의 크기나

부호는 묻지 않는다.

1단계 — 차를 구한다. 정의가 요구하는 것은 \(a - b\)이므로 뺄셈부터 한다.

확인 13. 두 물음의 차 \(a - b\)를 각각 구하고, 그 차를 법의 곱셈 등식으로 적어 보자. “\(84 = 12 \times \underline{\quad}\)”, “\(53 = 9 \times \underline{\quad} + \underline{\quad}\)”.

답

\(91 - 7 = 84\)이고 \(84 = 12 \times 7\) — 곱하는 수 7이 정수이므로 \(12 \mid 84\)이다.

\(58 - 5 = 53\)이고 \(53 = 9 \times 5 + 8\) — 9의 배수는 45와 54로 53을 건너뛰므로

\(53 = 9c\)인 정수 \(c\)는 없고, 따라서 \(9 \nmid 53\)이다.

2단계 — 판정을 문장으로 적는다. 계산 결과만 적으면 답안이 되지 않는다. 글쓰기 규칙 1조와 6조대로, 근거를 앞에 두고 판정을 문장으로 닫는다.

확인 14. 둘째 물음의 결론 문장을 완성해 보자. “따라서 \(\underline{\qquad}\)이므로 \(58 \underline{\quad} 5 \pmod 9\)이다.”

답

“따라서 \(9 \nmid 53\)이므로 \(58 \not\equiv 5 \pmod 9\)이다.” 부정 판정에서는

\(\nmid\)와 \(\not\equiv\)를 짝지어 쓴다. “합동이 아니다”까지 적어야 판정이

닫힌다 — 차를 구해 놓고 멈추면 물음에 답하지 않은 것이다.

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

증명의 한 줄

왜 이 줄을 쓰는가?

정의 20.1에 의해, \(91 \equiv 7 \pmod{12}\)은 \(12 \mid (91 - 7)\)과 같은 뜻이다.

물음을 정의로 번역하는 첫 줄. 판정의 기준을 명시해 두면 이후 계산의 목표가 고정된다.

\(91 - 7 = 84\)이고 \(84 = 12 \times 7\)이며 \(7\)은 정수이므로 \(12 \mid 84\)이다.

차를 구하고 곱 등식으로 적는다(근거 ①). 나눗셈 “\(84 \div 12 = 7\)”은 연습장의 계산이고, 답안에는 곱 등식을 적는다.

따라서 \(91 \equiv 7 \pmod{12}\)이다.

역번역으로 판정을 닫는다.

마찬가지로 \(58 \equiv 5 \pmod 9\)은 \(9 \mid (58 - 5)\)와 같은 뜻인데, \(58 - 5 = 53\)이고 \(53 = 9c\)인 정수 \(c\)는 존재하지 않는다(\(9 \times 5 = 45\), \(9 \times 6 = 54\)).

부정 판정의 근거는 “정수가 없다”를 보이는 것이다. 이웃한 두 배수로 끼워 넣으면 존재하지 않음이 확인된다.

따라서 \(9 \nmid 53\)이므로 \(58 \not\equiv 5 \pmod 9\)이다.

부정 판정도 문장으로 닫는다.

검산. 나머지 관점으로 교차 확인해 보면 — \(91 = 12 \times 7 + 7\)과 \(7 = 12 \times 0 + 7\)은 나머지가 둘 다 7로 같고, \(58 = 9 \times 6 + 4\)와 \(5 = 9 \times 0 + 5\)는 나머지가 4와 5로 다르다. 두 판정이 §1.2 표와 같은 방식으로 일치한다. 검산은 연습장에서 하고, 답안에는 위 다섯 줄만 적는다.

예제 2.2 — 합 보존 (C4)의 증명#

명제. \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이면 \(a + c \equiv b + d \pmod n\)이다.

이번에는 설계만 함께 하고, 증명은 완성된 형태로 본다. 먼저 번역표를 채운다.

말

정의로 번역

가정 (출발점)

\(a \equiv b\), \(c \equiv d \pmod n\)

\(n \mid (a - b)\), \(n \mid (c - d)\)

목표 (도착점)

\(a + c \equiv b + d \pmod n\)

\(n \mid \big(\underline{\qquad(?)\qquad}\big)\)

확인 15. 목표 칸의 빈칸을 채워 보자. 결론을 정의 20.1로 번역하면 어떤 수가 \(n\)의 배수여야 하는가.

답

\(n \mid \big((a + c) - (b + d)\big)\). 결론에 등장하는 두 수가 \(a+c\)와 \(b+d\)이므로,

정의가 요구하는 것은 그 둘의 차다. 출발점은 배수 두 개이고 도착점도 배수

하나 — 남은 일은 도착점의 그 차를 출발점의 두 배수로 만들어 내는 것이다.

확인 16. \((a+c) - (b+d)\)를 괄호를 풀고 다시 묶어, 가정이 붙잡고 있는 두 덩어리 \((a-b)\)와 \((c-d)\)가 드러나게 적어 보자.

답

\((a+c) - (b+d) = a + c - b - d = (a - b) + (c - d)\). 덧셈의 교환\(\cdot\)결합법칙만

썼고 새로 도입한 것은 없다(근거 ③). 그런데 이 꼴이 나오는 순간 2주차

예제 2.2(“배수 두 개의 합은 배수”)가 그대로 적용된다 — 증명이 끝난 것이다.

증명. \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이라 가정하자. 정의 20.1에 의해 \(n \mid (a - b)\)이고 \(n \mid (c - d)\)이다. 2주차 예제 2.2(배수의 합은 배수)에 의해

\[ n \mid \big((a - b) + (c - d)\big) \]

이고, 덧셈의 교환\(\cdot\)결합법칙으로 \((a-b) + (c-d) = (a+c) - (b+d)\)이므로 \(n \mid \big((a+c) - (b+d)\big)\)이다. 따라서 정의 20.1에 의해 \(a + c \equiv b + d \pmod n\)이다. \(\blacksquare\)

네 문장의 구조는 번역 \(\to\) 조합 \(\to\) 역번역이다. 첫 문장이 가정을 선언하고, 둘째 문장이 정의로 번역하고, 셋째 문장이 이미 증명한 정리로 조합하고, 넷째 문장이 정의로 되돌린다. 이번 주 증명의 대부분이 이 네 문장이다.

곱 보존 (C5)는 조합 단계에 변형 하나가 더 필요하다. 같은 설계를 (C5)에 적용하면 도착점은 \(n \mid (ac - bd)\)인데, \(ac - bd\) 안에는 \((a-b)\)도 \((c-d)\)도 보이지 않는다. 가정이 붙잡고 있는 덩어리가 식에 드러나 있지 않은 것이다.

확인 17. \(ac - bd\)의 가운데에 \(-bc + bc\)를 삽입해 보자. 값은 변하지 않는데 식이 어떻게 쪼개지는가.

답

\(ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d)\). \(-bc + bc = 0\)이므로 값은

그대로이고, 대신 가정이 붙잡을 수 있는 두 덩어리 \((a-b)\)와 \((c-d)\)가 각각

인수로 드러난다. 이 “빼고 더하기”는 17주차 문제 16(역삼각부등식에서

\(x = (x-y) + y\)로 쪼갠 자리)에 이어 두 번째 등장이고, 목표에 필요한 덩어리가

식에 없을 때 그 덩어리가 나타나도록 항을 쪼개는 표준 수법이다.

그다음은 2주차의 부품 두 개로 끝난다. \(n \mid (a-b)\)이므로 \(n \mid c(a-b)\)이고 \(n \mid (c-d)\)이므로 \(n \mid b(c-d)\)이며(2주차 훈련 1: 배수에 정수를 곱해도 배수), 두 배수의 합도 배수이므로(2주차 예제 2.2) \(n \mid (ac - bd)\)이다. 완전한 증명문을 쓰는 것은 문제 17이다.

예제 2.3 — 요일 계산#

오늘이 수요일이면 100일 후는 무슨 요일인가?

이번에는 설계부터 혼자 한다. 무엇을 법으로 잡을지, 무엇의 나머지를 구할지 연필로 먼저 적은 뒤 아래 산문과 대조한다.

풀이. 요일은 7일마다 되풀이되므로 요일 계산은 법 7의 세계다. \(100\)을 7로 나누면 \(100 = 7 \times 14 + 2\)이고, \(100 - 2 = 98 = 7 \times 14\)이므로 \(7 \mid (100 - 2)\), 곧 \(100 \equiv 2 \pmod 7\)이다. 따라서 100일 후의 요일은 2일 후의 요일과 같다. 수요일에서 이틀 뒤는 금요일이므로, 답은 금요일이다.

이 풀이에서 실제로 한 일은 번역 하나다 — “요일이 7일마다 반복된다”를 “법 7”로 옮기고, 큰 수 100을 법 7에서 작은 수 2로 갈아 끼웠다. 달력 문제와 주기 문제는 대개 이렇게 적절한 법의 합동으로 번역된다. 법을 무엇으로 잡을지가 유일한 설계 판단이고, 나머지는 §1.6의 갈아 끼우기다.

관찰 — 같은 뼈대#

예제 2.2, 문제 17(곱 보존), 훈련 2(추이성)는 소재가 다르지만 뼈대가 같다. 아래 표의 빈칸을 채워 그 뼈대를 확인해 보자.

단계

예제 2.2 (합 보존)

곱 보존 (C5)

추이 (C3)

① 가정 선언

\(a \equiv b\), \(c \equiv d\)라 가정

\(a \equiv b\), \(c \equiv d\)라 가정

\(a \equiv b\), \(b \equiv c\)라 가정

② 정의로 번역

\(n \mid (a-b)\), \(n \mid (c-d)\)

\(n \mid (a-b)\), \(n \mid (c-d)\)

\(n \mid (a-b)\), \(n \mid \underline{\quad(1)\quad}\)

③ 목표의 차를 아는 배수들로 조합

\((a+c)-(b+d) = (a-b)+(c-d)\)

\(ac - bd = \underline{\qquad(2)\qquad}\)

\(a - c = \underline{\qquad(3)\qquad}\)

④ 정의로 역번역

\(a + c \equiv b + d\)

\(ac \equiv bd\)

\(\underline{\quad(4)\quad}\)

확인 18. 빈칸 (1)~(4)를 채우고, ③ 단계의 세 식에 공통된 일이 무엇인지 한 문장으로 적어 보자.

답

(1) \(b - c\) (2) \(c(a-b) + b(c-d)\) (3) \((a-b) + (b-c)\) (4) \(a \equiv c \pmod n\).

③ 단계의 공통점: **목표가 요구하는 차를, 가정이 이미 배수임을 보장하는

덩어리들의 합(또는 정수배의 합)으로 다시 쓴다.** 세 경우 모두 이 한 줄이

증명의 전부이고, 나머지 세 단계는 번역과 역번역이다.

이번 주에 확인한 것

합동 증명은 번역 \(\to\) 조합 \(\to\) 역번역의 세 박자다. 번역과 역번역은 정의

20.1이 기계적으로 처리하므로, 생각할 곳은 조합 한 곳뿐이다. 조합에서

쓰는 부품은 2주차의 세 정리(배수의 합, 배수에 정수 곱하기, 부호 뒤집기)이고,

덩어리가 식에 보이지 않을 때 꺼내는 수법이 “빼고 더하기”다.

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

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

훈련 1 ●○○ — 수식 빈칸#

명제. \(a \equiv b \pmod n\)이면 임의의 정수 \(c\)에 대해 \(a - c \equiv b - c \pmod n\)이다.

증명. \(a \equiv b \pmod n\)이라 가정하고 \(c\)를 임의의 정수라 하자. 정의에 의해 \(n \mid \underline{\quad(1)\quad}\)이다. 그런데 괄호를 풀어 정리하면

\[ (a - c) - (b - c) = \underline{\quad(2)\quad} \]

이므로 \(n \mid \big((a-c) - (b-c)\big)\)이다. 따라서 정의에 의해 \(\underline{\quad(3)\quad}\)이다. \(\blacksquare\)

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

이번에는 구조 낱말과 근거 문장도 빈칸이다.

명제 ((C3), 추이). \(a \equiv b \pmod n\)이고 \(b \equiv c \pmod n\)이면 \(a \equiv c \pmod n\)이다.

증명. \(a \equiv b\)이고 \(b \equiv c \pmod n\)이라 \(\underline{\quad(1)\quad}\)하자. \(\underline{\quad(2)\quad}\)에 의해 \(n \mid (a - b)\)이고 \(n \mid \underline{\quad(3)\quad}\)이다. \(\underline{\quad(4)\quad}\)에 의해 두 배수의 합도 배수이므로

\[ n \mid \big((a-b) + (b-c)\big), \quad\text{즉}\quad n \mid \underline{\quad(5)\quad} \]

이다. 따라서 정의에 의해 \(\underline{\quad(6)\quad}\)이다. \(\blacksquare\)

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

이번에는 세 박자의 각 칸을 통째로 채운다.

명제. \(a \equiv b \pmod n\)이고 \(n \mid c\)이면 \(a + c \equiv b \pmod n\)이다.

증명의 뼈대.

  • ① 가정 선언: \(\underline{\quad(1)\quad}\)

  • ② 정의로 번역: \(\underline{\quad(2)\quad}\)

  • ③ 목표의 차를 아는 배수들로 조합하고 역번역: \(\underline{\quad(3)\quad}\)

(도착점은 \(n \mid \big((a+c) - b\big)\)이다. 그 차를 어떤 두 덩어리의 합으로 다시 쓸지가 관건이고, 이 명제는 (C4)에 \(c \equiv 0\)을 넣은 경우에 해당한다 — 해설의 주석과 대조해 볼 자리다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 합동 증명의 첫 줄은 언제나 정의 번역 “\(n \mid (\cdot)\)”이다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “\(17 \equiv 5 \pmod 6\)은 참(나머지가 같으니까)”은

0점이고, “\(17 - 5 = 12 = 6 \times 2\)이므로 \(6 \mid 12\), 정의에 의해 참”이

만점이다. 증명 문항에서는 여기에 두 가지가 더 걸린다 — 정의 번역이 첫 줄에

있는가, 인용한 정리((C4) 등)가 그 시점에 이미 증명된 것인가.

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

기본 ●○○#

1. 참\(\cdot\)거짓을 정의(\(n \mid (a-b)\) 확인)로 판정하시오. (a) \(17 \equiv 5 \pmod 6\) (b) \(8 \equiv -1 \pmod 3\) (c) \(21 \equiv 7 \pmod 8\) (d) \(-3 \equiv 7 \pmod 5\) (e) \(100 \equiv 2 \pmod 7\)

힌트

각 항목에서 할 일은 둘뿐이다 — 차 \(a - b\)를 구하고, 그 차가 법의 배수인지

곱 등식으로 확인한다. 음수 차가 나와도 그대로 진행한다: \(-10 = 5 \times (-2)\)처럼

곱하는 수가 정수이기만 하면 배수다.

2. “\(a \equiv b \pmod n\)”을 (a) \(\mid\) 기호로, (b) \(\exists\) 기호로 번역하시오. 그리고 (c) “두 정수 \(a, b\)는 10으로 나눈 나머지(일의 자리)가 같다”를 합동식으로 쓰시오.

힌트

(a)는 정의 20.1을 그대로 옮기면 되고, (b)는 거기에 2주차 정의 2.1을 한 겹 더

푼다. (c)는 §1.6에서 “일의 자리는 법 10”이라 한 것을 기호로 옮기는 자리다.

3. 다음 수는 mod 5에서 \(0, 1, 2, 3, 4\) 중 어느 것과 합동인가? \(17\), \(23\), \(-4\), \(40\)

힌트

각 수에서 5의 배수를 더하거나 빼서 \(0\) 이상 \(5\) 미만으로 옮긴다. 옮긴

뒤에는 차가 5의 배수인지 곱 등식으로 확인한다. 음수 \(-4\)는 5를 더해 본다.

4. (C1) 반사성: 모든 정수 \(a\)에 대해 \(a \equiv a \pmod n\)임을 증명하시오.

힌트

정의가 요구하는 것은 \(n \mid (a - a)\)이다. \(a - a\)는 무엇이고, 그 수가 \(n\)의

배수인지는 2주차 문제 2(a)에서 \(7 \mid 0\)으로 판정한 것과 같은 계산이다 —

일반의 \(n \mid 0\)은 여기서 \(0 = n \times 0\)으로 직접 확인한다.

5. (C2) 대칭성: \(a \equiv b \pmod n\)이면 \(b \equiv a \pmod n\)임을 증명하시오. (힌트: 2주차 문제 8)

힌트

가정이 주는 것은 \(n \mid (a-b)\)이고 목표가 요구하는 것은 \(n \mid (b-a)\)이다.

두 수는 부호만 다르다 — \(b - a = -(a-b)\)이고, 배수의 부호를 뒤집어도

배수라는 것이 2주차 문제 8이다.

6. “\(n\)이 홀수 \(\Longleftrightarrow\) \(n \equiv 1 \pmod 2\)”를 두 방향으로 설명하시오 (정의 대조).

힌트

양방향 모두 정의 번역이다. \(n \equiv 1 \pmod 2\)는 \(2 \mid (n-1)\)이고, 이를

한 겹 더 풀면 \(n - 1 = 2k\)인 정수 \(k\)가 존재한다 — 이 등식을 \(n\)에 대해

정리하면 홀수의 정의(정의 1.2)와 나란히 놓인다.

표준 ●●○#

7. (C3) 추이성을 백지에서 증명하시오 (빈칸 훈련의 완성본).

8. (C4) 합 보존을 백지에서 증명하시오 (예제 2.2 재현).

9. \(a \equiv b \pmod n\)이면 다음이 성립함을 각각 증명하시오. (a) \(a + c \equiv b + c \pmod n\) (임의의 정수 \(c\)) (b) \(ka \equiv kb \pmod n\) (임의의 정수 \(k\))

힌트

(a)는 두 가지 길이 있다 — 정의로 직접 계산하거나, (C4)에 \(c \equiv c\)(반사성)를

끼워 넣는다. 두 번째 길은 (C1)이 장식이 아니라 부품이라는 것을 보여 준다.

(b)는 \(ka - kb = k(a-b)\)로 묶고 2주차 훈련 1을 인용한다.

10. \(a \equiv b \pmod n\)이면 \(a^2 \equiv b^2 \pmod n\)임을 (C5)를 인용해 두 줄로 증명하시오.

11. \(7^{42}\)의 일의 자리를 구하시오 (예제 2.3의 방법; \(7^k\)의 mod 10 주기를 먼저 찾을 것).

힌트

§1.6의 \(3^{100}\)과 같은 절차다. \(7^1, 7^2, 7^3, 7^4\)를 법 10에서 줄여 1이

나오는 지수를 찾고, 42를 그 주기로 나눈 나머지로 위치를 정한다.

12. 오늘이 화요일이면 365일 후는 무슨 요일인가? (\(365\)를 7로 나눈 나머지부터)

13. 정수 \(x\)가 \(2 \mid x\)이고 \(3 \mid x\)이면 \(6 \mid x\)임을 증명하시오. (힌트: \(x = 3k\)로 쓴 뒤, \(3k\)가 짝수라는 사실에서 \(k\)가 짝수임을 끌어내라 — “홀수 \(\times\) 홀수 = 홀수”(1주차 문제 8)의 대우가 열쇠. 5주차 문제 9의 빚 청산)

이 문제가 빌려 쓰는 사실 — 대우를 부품으로 쓰기

문제의 힌트가 가리키는 사실은 “\(3k\)가 짝수이면 \(k\)는 짝수이다”이다. 이것은

1주차 문제 8(“홀수와 홀수의 곱은 홀수”)의 대우(“곱이 짝수이면 두 인수 중

적어도 하나가 짝수이다”)를 이 상황에 적용한 것이다 — 3은 홀수이므로 짝수인

쪽은 \(k\)일 수밖에 없다. 같은 말을 뒤집으면, \(k\)까지 홀수라면 곱 \(3k\)가 홀수가

되어 가정과 어긋난다. 19주차에서 대우가 원명제와 동치임을 확인했으므로,

이미 증명한 명제의 대우는 따로 증명하지 않고

근거 ④로 인용할 수 있다. 답안에서는 대우를 인용하거나, 힌트대로 “만약 \(k\)가

홀수라면 …이 되어 모순이므로 \(k\)는 짝수다”로 적어도 된다.

14. “\(n^2 + 1 \equiv 0 \pmod 4\)인 정수 \(n\)은 존재하지 않는다”를 증명하시오. (힌트: 17주차 문제 9 — \(n^2\)은 mod 4에서 0 또는 1)

힌트

존재하지 않음을 보이는 방법은 가능한 값을 전부 훑는 것이다. 17주차 문제 9가

\(n^2\)의 후보를 두 개로 줄여 주므로, 각 후보에 (C4)로 1을 더해 \(n^2+1\)의

후보를 만들고, 그 목록에 0이 없음을 확인한다.

도전 ●●●#

15. (9의 배수 판정법) 세 자리 자연수 \(N = 100a + 10b + c\)에 대해

\[ N \equiv a + b + c \pmod 9 \]

임을 증명하시오. (힌트: \(10 \equiv 1 \pmod 9\)에서 (C5)로 \(100 \equiv 1\), 그다음 (C4)\(\cdot\)문제 9(b)로 조립) 그리고 이것이 왜 “자릿수 합이 9의 배수 \(\Longleftrightarrow\) 원래 수가 9의 배수”라는 판정법이 되는지 한 문장으로 쓰시오.

힌트

출발점은 \(10 - 1 = 9\)라는 사실 하나다. 여기서 \(10 \equiv 1 \pmod 9\)이 나오고,

(C5)를 \(10 \equiv 1\)과 \(10 \equiv 1\)에 적용하면 \(100 \equiv 1\)이 나온다.

그다음 문제 9(b)로 계수 \(a, b\)를 곱해 붙이고, (C4)로 세 조각을 더한다.

마지막 문장은 \(9 \mid \big(N - (a+b+c)\big)\)로 되돌려 놓고, 2주차 예제 2.2(배수의

합)와 2주차 문제 7(배수의 차)로 양방향을 잇는 자리다.

16. 친구가 \(437 \times 254 = 110{,}898\)이라고 계산했다. 곱셈을 다시 하지 않고, mod 9 검산(문제 15의 원리)으로 이 계산이 틀렸음을 보이시오.

힌트

좌변의 두 세 자리 수를 각각 자릿수 합으로 법 9에서 줄이고(문제 15), (C5)로

두 값을 곱해 줄인다. 우변은 세 자리가 아니므로 문제 15가 그대로 닿지 않는다 —

9로 나누어떨어지는지 정의로 직접 확인한다. 두 값이 다르면 등식이 성립할 수

없다.

17. (C5) 곱 보존을 백지에서 증명하시오 — “빼고 더하기” 다리 놓기 포함.

힌트

예제 2.2의 확인 17에서 만든 항등식 \(ac - bd = c(a-b) + b(c-d)\)가 몸통이다.

그 앞뒤로 정의 번역과 역번역을 붙이고, 두 덩어리가 각각 배수임을 2주차

훈련 1로, 합이 배수임을 2주차 예제 2.2로 근거 붙인다.

18. 17주차 문제 15(“홀수의 제곱은 \(8m+1\) 꼴”)를 합동 언어로 재진술하고, 그것을 이용해 “\(a, b\)가 홀수이면 \(a^2 + b^2 \equiv 2 \pmod 8\)”을 증명하시오.

힌트

재진술은 정의 번역이다 — \(n^2 = 8m + 1\)은 \(n^2 - 1 = 8m\), 곧 \(8 \mid (n^2-1)\)이고

이는 \(n^2 \equiv 1 \pmod 8\)이다. 재진술을 끝내면 두 홀수에 각각 적용하고

(C4)로 더하기만 하면 된다.

19. (글쓰기 교정) 다음 답안을 규칙 6조에 비추어 교정하시오 (내용은 옳다고 치고, 서술만).

“\(n = 2k+1\). \(\Rightarrow n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1 = \) 홀수. \(\blacksquare\)”

힌트

여섯 조항을 차례로 대조하며 위반을 세어 본다. 첫 글자가 무엇인가(1조),

\(k\)는 소개되었는가(2조), 마지막 등호의 오른쪽은 수인가(3조), \(\Rightarrow\)가

접속사로 쓰였는가(4조), 시작 표시가 있는가(6조). 지적만으로 끝내지 말고

교정본까지 적는 것이 이 문제의 완결이다.

20. (서술) \(\equiv \pmod n\)이 등호(=)와 닮은 점 세 가지(C1~C3)와 다른 점 한 가지를 쓰시오. 그리고 “같음의 조건을 느슨하게 바꾼 세계마다 새로운 산술이 생긴다”는 관점에서, mod 12의 세계(시계)에서 \(8 + 7\)이 무엇이 되는지 계산해 보시오. (36~38주차 예고)

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

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 세 박자 틀(§2 관찰)과 근거 목록(§1.8)만 펴 놓고, 예제 2.2((C4) 합 보존)를 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다. 이어서 (C5)의 다리 놓기 항등식만 다시 유도해 본다.

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

  • 정의 20.1을 “\(n \mid (a-b)\)”까지 조각 그대로 정확히 썼다.

  • 법 \(\pmod n\) 표기를 빠뜨리면 무엇이 무너지는지 한 문장으로 설명했다(§1.3).

  • (C1)~(C5)를 진술하고, 각각이 2주차의 어느 정리로 증명되는지 짝지었다.

  • (C4)와 (C5)를 백지에 처음부터 끝까지 재현했다 — (C5)는 “빼고 더하기” 포함.

  • 재현한 증명에서 ① 가정 선언 ② 정의 번역 ③ 조합 ④ 역번역의 네 단계를 손가락으로 짚을 수 있다.

  • \(3^{100}\)의 일의 자리 계산(주기 찾기 \(\to\) 지수 축소)을 재현했다.

  • 글쓰기 규칙 6조를 백지에 썼다.

  • 합동식의 양변을 공통 인수로 나눌 수 없다는 것을 반례와 함께 말할 수 있다(§1.5).

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

막힌 지점

처방

증명의 첫 줄이 나오지 않는다

§2 관찰 — 첫 줄은 언제나 정의 번역 \(n \mid (\cdot)\)이다

목표의 차를 어떻게 쪼갤지 모르겠다

예제 2.2 확인 16 — 목표의 차를 괄호를 풀고 다시 묶어 본다

식에 \((a-b)\)가 보이지 않는다

예제 2.2 확인 17 — 같은 항을 빼고 더해 덩어리를 만들어 낸다

어느 정리를 인용할지 모르겠다

§1.8 근거 목록 — 2주차 부품 셋과 (C1)~(C5)뿐이다

나머지 계산이 자꾸 어긋난다

§1.4 — 나머지는 연습장용이고 답안은 차의 배수 판정으로 쓴다

큰 수의 거듭제곱에서 막힌다

§1.6 — 1이 나오는 지수를 먼저 찾는다

계산은 맞는데 답안이 감점된다

§1.7 규칙 6조 — 여섯 조항으로 한 줄씩 대조한다

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) \((a - b)\) (2) \(a - b\) (3) \(a - c \equiv b - c \pmod n\)

※ 핵심은 (2)다. \((a-c) - (b-c) = a - c - b + c = a - b\)로, 빼는 \(c\)가 서로 상쇄되어 가정이 붙잡고 있는 덩어리가 그대로 남는다. 문제 9(a)의 합 버전과 같은 구조이고, 거기서는 \((a+c) - (b+c) = a - b\)가 된다.

빈칸 사다리 — 훈련 2#

(1) 가정 (2) 정의 20.1 (3) \(b - c\) (4) 2주차 예제 2.2 (5) \(a - c\) (6) \(a \equiv c \pmod n\)

※ (5)에서 \((a-b) + (b-c) = a - c\)로 가운데 \(b\)가 상쇄된다 — 2주차 예제 2.1 (추이성)에서 다리 \(b\)를 대입으로 소거한 것과 같은 발상이고, 여기서는 덧셈으로 소거된다. 문제 7이 이 완성본을 백지에서 재현하는 자리다.

빈칸 사다리 — 훈련 3#

(1) \(a \equiv b \pmod n\)이고 \(n \mid c\)라 가정하자. (2) 정의 20.1에 의해 \(n \mid (a - b)\)이다. (둘째 가정 \(n \mid c\)는 이미 배수 꼴이므로 번역할 것이 없다.) (3) \((a + c) - b = (a - b) + c\)이고 \(n \mid (a-b)\), \(n \mid c\)이므로 2주차 예제 2.2에 의해 \(n \mid \big((a+c) - b\big)\)이다. 따라서 정의에 의해 \(a + c \equiv b \pmod n\)이다. \(\blacksquare\)

※ 가정 두 개 중 하나가 이미 “\(n \mid c\)” 꼴이라 번역 단계가 반만 필요했다. \(n \mid c\)는 \(c \equiv 0 \pmod n\)과 같은 뜻이므로, 이 명제는 (C4)에 \(c \equiv 0\)을 넣은 것과 같다 — 부품을 어느 쪽으로 읽어도 같은 결과가 나온다.

문제 1#

접근. 다섯 항목 전부에서 할 일은 같다 — 차 \(a - b\)를 구하고, 그 차를 \(n \times (\text{정수})\) 꼴로 적을 수 있는지 본다. 차가 음수로 나와도 절차는 바뀌지 않는다. 나눗셈으로 나머지를 비교하는 것은 연습장에서만 한다.

풀이. (a) 참. \(17 - 5 = 12\)이고 \(12 = 6 \times 2\)이며 2는 정수이므로 \(6 \mid 12\)이다. 따라서 \(17 \equiv 5 \pmod 6\)이다. (b) 참. \(8 - (-1) = 9\)이고 \(9 = 3 \times 3\)이므로 \(3 \mid 9\)이다. 따라서 \(8 \equiv -1 \pmod 3\)이다. 빼는 수가 음수일 때 부호에 주의한다 — \(8 - 1 = 7\)이 아니다. (c) 거짓. \(21 - 7 = 14\)인데 \(14 = 8c\)인 정수 \(c\)는 없다(\(8 \times 1 = 8\), \(8 \times 2 = 16\)). 따라서 \(8 \nmid 14\)이고 \(21 \not\equiv 7 \pmod 8\)이다. (d) 참. \(-3 - 7 = -10\)이고 \(-10 = 5 \times (-2)\)이며 \(-2\)는 정수이므로 \(5 \mid (-10)\)이다. 따라서 \(-3 \equiv 7 \pmod 5\)이다. (e) 참. \(100 - 2 = 98\)이고 \(98 = 7 \times 14\)이므로 \(7 \mid 98\)이다. 따라서 \(100 \equiv 2 \pmod 7\)이다.

복기. 판정의 두 얼굴 — 탐색은 나눗셈으로 해도 되지만, 답안의 근거는 곱 등식과 정수 확인(근거 ①)이다. (b)와 (d)에서 보듯 음수는 정의 앞에서 아무런 특별 취급도 받지 않는다. (e)의 결과는 예제 2.3의 요일 계산과 같은 사실이다.

문제 2#

접근. 정의를 겹겹이 푸는 문제다. \(\equiv\)는 정의 20.1로 \(\mid\)가 되고, \(\mid\)는 2주차 정의 2.1로 \(\exists\) 문장이 된다. (c)는 반대로, 말로 된 조건을 합동식으로 압축한다.

풀이. (a) \(n \mid (a - b)\). 정의 20.1을 그대로 옮긴 것이다. (b) \(\exists k \in \mathbb{Z},\ a - b = nk\). (a)에 2주차 정의 2.1을 한 겹 더 적용했다. 말로 적으면 “\(a - b = nk\)인 정수 \(k\)가 존재한다”이고, 이 문장이 증명에서 실제로 쓰는 꼴이다. (c) \(a \equiv b \pmod{10}\). 일의 자리는 10으로 나눈 나머지이므로 법이 10이고, “나머지가 같다”가 곧 합동이다(§1.4).

복기. 정의의 사슬 \(\equiv \to \mid \to \exists\) 가운데 어디까지 풀지는 목적이 정한다. 판정만 할 때는 \(\mid\)까지, 문자로 계산할 때는 \(\exists\)까지 푼다. (c)처럼 반대 방향으로 압축하는 것도 같은 사슬을 거꾸로 읽는 일이다.

문제 3#

접근. 각 수에서 5의 배수를 더하거나 빼서 \(0\) 이상 \(5\) 미만의 수로 옮긴다. 옮긴 결과가 답이고, 근거는 “차가 5의 배수”라는 확인이다. 음수는 5를 몇 번 더해야 범위 안에 들어오는지 본다.

풀이. \(17 \equiv 2 \pmod 5\) — \(17 - 2 = 15 = 5 \times 3\)이므로 \(5 \mid 15\)이다. \(23 \equiv 3 \pmod 5\) — \(23 - 3 = 20 = 5 \times 4\)이므로 \(5 \mid 20\)이다. \(-4 \equiv 1 \pmod 5\) — \(-4 - 1 = -5 = 5 \times (-1)\)이므로 \(5 \mid (-5)\)이다. \(40 \equiv 0 \pmod 5\) — \(40 - 0 = 40 = 5 \times 8\)이므로 \(5 \mid 40\)이다.

복기. \(-4\)에서 \(-4\)나 \(4\)라고 답하는 경우가 많다. 원인은 나눗셈의 몫을 0 쪽으로 반올림하는 계산기의 관습을 그대로 쓰기 때문이다. 요구되는 범위는 \(0 \le r < 5\)이므로 몫을 \(-1\)까지 내려야 하고, 정의로 확인하면 (\(-4 - 1 = -5\)가 5의 배수) 갈래 없이 결정된다. (검산: \(17, 23, -4, 40\)을 각각 5로 나눈 나머지가 \(2, 3, 1, 0\) ✓.)

문제 4#

접근. 정의가 요구하는 것은 \(n \mid (a - a)\)뿐이다. \(a - a = 0\)이므로 물음은 “\(n\)이 0을 나누는가”로 바뀌고, 이것은 2주차 문제 2(a)에서 이미 판정했다. 짧은 증명이지만 세 박자(번역-조합-역번역)는 그대로 들어간다.

풀이. \(a\)를 임의의 정수, \(n\)을 자연수라 하자. \(a - a = 0\)이고, \(0 = n \times 0\)이며 0은 정수이므로 정의 2.1에 의해 \(n \mid 0\)이다. 곧 \(n \mid (a - a)\)이다. 따라서 정의 20.1에 의해 \(a \equiv a \pmod n\)이다. \(a\)는 임의였으므로 모든 정수 \(a\)에 대해 성립한다. \(\blacksquare\)

복기. 결론이 뻔해 보여도 근거의 사슬은 똑같이 요구된다 — 여기서 실제로 쓰인 사실은 “\(n\)은 0을 나눈다”이고, 그 근거는 \(0 = n \times 0\)이라는 곱 등식이다. 이 한 줄이 빠지면 (C1)은 인용할 수 없는 명제로 남고, 문제 9(a)의 둘째 풀이가 무너진다.

문제 5#

접근. 가정이 주는 것은 \(n \mid (a - b)\), 목표가 요구하는 것은 \(n \mid (b-a)\)다. 두 수는 부호만 다르므로, 배수의 부호를 뒤집어도 배수라는 2주차 문제 8이 그대로 다리가 된다.

풀이. \(a \equiv b \pmod n\)이라 가정하자. 정의 20.1에 의해 \(n \mid (a - b)\)이다. 2주차 문제 8(\(a \mid b\)이면 \(a \mid (-b)\))에 의해 \(n \mid -(a-b)\)이고, \(-(a - b) = b - a\)이므로 \(n \mid (b - a)\)이다. 따라서 정의 20.1에 의해 \(b \equiv a \pmod n\)이다. \(\blacksquare\)

복기. 정의 20.1이 \(a - b\)라는 순서 있는 차로 적혀 있는데도 실제로는 순서가 무관하다는 것이, 바로 이 (C2)가 보장해 주는 내용이다. §1.3 해부 표의 셋째 조각에서 “대칭성이 증명되고 나서야 순서가 무관해진다”고 한 빚을 여기서 갚았다. 이후로는 \(n \mid (b-a)\)를 보아도 \(a \equiv b\)라 적을 수 있다.

문제 6#

접근. 양방향 모두 정의 번역만으로 끝난다. \(n \equiv 1 \pmod 2\)를 두 겹 풀면 \(n - 1 = 2k\)가 나오고, 이 등식을 \(n\)에 대해 정리하면 홀수의 정의 \(n = 2k+1\)과 같은 식이 된다. 곧 두 문장은 같은 등식의 다른 배열이다.

풀이. (\(\Rightarrow\)) \(n\)이 홀수라 가정하자. 정의 1.2에 의해 \(n = 2k + 1\)인 정수 \(k\)가 존재한다. 양변에서 1을 빼면 \(n - 1 = 2k\)이고 \(k\)는 정수이므로 \(2 \mid (n-1)\)이다. 따라서 정의 20.1에 의해 \(n \equiv 1 \pmod 2\)이다. (\(\Leftarrow\)) \(n \equiv 1 \pmod 2\)라 가정하자. 정의 20.1에 의해 \(2 \mid (n-1)\)이고, 정의 2.1에 의해 \(n - 1 = 2k\)인 정수 \(k\)가 존재한다. 양변에 1을 더하면 \(n = 2k + 1\)이므로, 정의 1.2에 의해 \(n\)은 홀수이다. 양방향이 모두 성립하므로 두 명제는 동치이다. \(\blacksquare\)

복기. 1주차의 짝\(\cdot\)홀 세계 전체가 법 2의 합동으로 흡수된다 — 짝수는 \(n \equiv 0 \pmod 2\), 홀수는 \(n \equiv 1 \pmod 2\)이다. 그래서 17주차의 짝\(\cdot\)홀 분할은 법 2의 나머지 분할과 같은 것이었고, 같은 방식으로 법 3, 법 4의 분할이 얻어진다.

문제 7#

접근. 훈련 2의 완성본이다. 세 박자 그대로 — 정의로 두 배수를 받고, 목표의 차 \(a - c\)를 그 두 배수의 합으로 다시 쓰고, 정의로 되돌린다. 가운데 \(b\)가 상쇄되는 것이 이 증명의 전부다.

풀이. \(a \equiv b \pmod n\)이고 \(b \equiv c \pmod n\)이라 가정하자. 정의 20.1에 의해 \(n \mid (a - b)\)이고 \(n \mid (b - c)\)이다. 2주차 예제 2.2(배수 두 개의 합은 배수)에 의해

\[ n \mid \big((a - b) + (b - c)\big) \]

이고, \((a-b) + (b-c) = a - c\)이므로 \(n \mid (a - c)\)이다. 따라서 정의 20.1에 의해 \(a \equiv c \pmod n\)이다. \(\blacksquare\)

복기. 2주차 예제 2.1(나누어떨어짐의 추이성)에서는 다리 \(b\)를 대입으로 소거했고, 여기서는 덧셈으로 소거했다. 두 경우 모두 “가운데 것을 없애는 변형”이 증명의 몸통이고, 이 발상은 36주차에서 추이성을 관계의 성질로 다룰 때 다시 나온다. (검산: \(n = 6\), \(a = 17\), \(b = 5\), \(c = 29\)이면 \(6 \mid 12\), \(6 \mid (-24)\)이고 \(6 \mid (-12)\) ✓.)

문제 8#

접근. 예제 2.2의 네 문장 재현이다. 목표의 차 \((a+c) - (b+d)\)를 괄호를 풀어 다시 묶으면 가정이 붙잡고 있는 \((a-b)\)와 \((c-d)\)가 드러난다. 그 재배열이 보이면 나머지는 인용이다.

풀이. \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이라 가정하자. 정의 20.1에 의해 \(n \mid (a - b)\)이고 \(n \mid (c - d)\)이다. 2주차 예제 2.2에 의해

\[ n \mid \big((a - b) + (c - d)\big) \]

이고, 덧셈의 교환\(\cdot\)결합법칙으로 \((a-b) + (c-d) = (a+c) - (b+d)\)이므로 \(n \mid \big((a+c) - (b+d)\big)\)이다. 따라서 정의 20.1에 의해 \(a + c \equiv b + d \pmod n\)이다. \(\blacksquare\)

복기. 이 증명이 끝나는 순간 (C4)가 근거 ④에 등록되고, 이후 문제 9(a), 14, 15, 18이 전부 이 한 정리를 인용한다. 증명의 순서가 곧 인용 가능 시점의 순서라는 것을 답안에서 지키는 것도 채점 대상이다. (검산: \(n = 6\)에서 \(17 \equiv 5\), \(8 \equiv 2\)이면 \(25 \equiv 7\) — \(6 \mid 18\) ✓.)

문제 9#

접근. (a)는 두 길이 있다. 정의로 직접 계산하면 \((a+c) - (b+c) = a - b\)로 \(c\)가 상쇄되고, 부품으로 가면 (C4)에 \(c \equiv c\)(반사성, 문제 4)를 끼워 넣는다. (b)는 \(ka - kb = k(a-b)\)로 묶은 뒤 2주차 훈련 1을 인용한다.

풀이. (a) 풀이 1 (정의로 직접). \(a \equiv b \pmod n\)이라 가정하고 \(c\)를 임의의 정수라 하자. 정의에 의해 \(n \mid (a-b)\)이다. 그런데 \((a + c) - (b + c) = a - b\)이므로 \(n \mid \big((a+c) - (b+c)\big)\)이고, 정의에 의해 \(a + c \equiv b + c \pmod n\)이다. \(\blacksquare\) 풀이 2 (부품 재사용). 문제 4(반사성)에 의해 \(c \equiv c \pmod n\)이다. (C4)를 \(a \equiv b\)와 \(c \equiv c\)에 적용하면 \(a + c \equiv b + c \pmod n\)이다. \(\blacksquare\) (b) \(a \equiv b \pmod n\)이라 가정하고 \(k\)를 임의의 정수라 하자. 정의에 의해 \(n \mid (a - b)\)이다. 2주차 훈련 1(\(a \mid b\)이면 임의의 정수 \(c\)에 대해 \(a \mid bc\))에 의해 \(n \mid k(a - b)\)이고, \(k(a-b) = ka - kb\)이므로 \(n \mid (ka - kb)\)이다. 따라서 정의에 의해 \(ka \equiv kb \pmod n\)이다. \(\blacksquare\)

복기. (a)의 풀이 2에서 반사성이 “당연한 성질”이 아니라 부품으로 쓰였다 — (C1)~(C5)를 한 세트로 증명해 두는 이유가 이것이다. 한편 (b)의 역은 성립하지 않는다: §1.5 확인 7에서 본 대로 \(2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}\)이지만 \(3 \not\equiv 8 \pmod{10}\)이다. 곱하는 것은 자유이고 나누는 것은 자유가 아니다.

문제 10#

접근. (C5)는 서로 다른 두 합동식을 요구하지만, 같은 합동식을 두 번 넣어도 된다. \(a \equiv b\)와 \(a \equiv b\)를 넣으면 결론이 \(a \cdot a \equiv b \cdot b\)가 된다. 정의까지 내려가지 않고 부품 하나로 끝나는 문제다.

풀이. \(a \equiv b \pmod n\)이라 가정하자. (C5)를 두 합동식 \(a \equiv b \pmod n\)과 \(a \equiv b \pmod n\)에 적용하면 \(a \cdot a \equiv b \cdot b \pmod n\), 곧 \(a^2 \equiv b^2 \pmod n\)이다. \(\blacksquare\)

여기서 인용한 (C5)의 답안 형태는 문제 17이지만, 그 증명은 §2 예제 2.2 말미에서 이미 조립되었으므로 근거 ④로 쓸 수 있다.

복기. 같은 정리에 같은 가정을 두 번 대입하는 것은 근거 ④의 정당한 사용이다. 이 조작을 반복하면 \(a^3 \equiv b^3\), \(a^4 \equiv b^4\)로 이어지고, 그 반복의 일반형이 §1.6에서 인정하고 쓴 거듭제곱 보존이다(엄밀한 증명은 31주차 문제 13). (검산: \(n = 6\)에서 \(17 \equiv 5\)이면 \(289 \equiv 25\) — \(289 - 25 = 264 = 6 \times 44\) ✓.)

문제 11#

접근. 일의 자리는 법 10이다. §1.6의 절차 그대로 \(7^k\)를 법 10에서 줄여 1이 나오는 지수를 찾고, 42를 그 주기로 나눈 나머지로 위치를 정한다. 큰 수를 직접 계산하지 않는 것이 이 방법의 요점이다.

풀이. 법 10에서 \(7\)의 거듭제곱을 차례로 줄인다.

\[ 7^1 \equiv 7, \quad 7^2 = 49 \equiv 9, \quad 7^3 \equiv 7 \cdot 9 = 63 \equiv 3, \quad 7^4 \equiv 7 \cdot 3 = 21 \equiv 1 \pmod{10} \]

(각 단계는 (C5)를 앞 결과와 \(7 \equiv 7\)에 적용한 것이다. 예를 들어 \(63 \equiv 3\)은 \(63 - 3 = 60\)이 10의 배수이므로 성립한다.) \(7^4 \equiv 1\)이 나왔으므로 주기는 4다. \(42 = 4 \times 10 + 2\)이므로

\[ 7^{42} = (7^4)^{10} \cdot 7^2 \equiv 1^{10} \cdot 9 = 9 \pmod{10} \]

이다. 거듭제곱 보존(§1.6에서 인정하고 쓰기로 한 사실, 엄밀한 증명은 31주차 문제 13)에 의해 \((7^4)^{10} \equiv 1^{10} \pmod{10}\)이고, 여기에 (C5)로 \(7^2 \equiv 9\)를 곱하면 위와 같다. 따라서 \(7^{42}\)의 일의 자리는 9이다.

복기. 절차를 세 단계로 고정해 두면 밑이 3, 7처럼 1로 되돌아오는 경우에는 그대로 쓸 수 있다 — ① 법을 정한다 ② 1이 나오는 지수(주기)를 찾는다 ③ 지수를 주기로 나눈 나머지만 남긴다. 1이 돌아오지 않는 밑도 있다 — 법 10에서 2의 거듭제곱은 2, 4, 8, 6이 반복될 뿐 1이 나오지 않고, 5의 거듭제곱은 언제나 5다. 그때는 1 대신 앞서 나온 값이 다시 나오는 지점을 주기로 잡는다. 38주차 문제 12에서 이 계산을 \(\mathbb{Z}_{10}\)의 언어로 다시 쓴다.

문제 12#

접근. 요일은 법 7이다(예제 2.3). 365를 7로 나눈 나머지를 구해 큰 수를 작은 수로 갈아 끼운 뒤, 화요일에서 그만큼 진행한다.

풀이. \(365 = 7 \times 52 + 1\)이고 \(365 - 1 = 364 = 7 \times 52\)이므로 \(7 \mid 364\), 곧 \(365 \equiv 1 \pmod 7\)이다. 따라서 365일 후의 요일은 1일 후의 요일과 같다. 화요일의 하루 뒤는 수요일이므로 답은 수요일이다.

복기. 이 계산이 “1년 뒤 같은 날짜의 요일이 하루 밀린다”는 현상의 근거다. 윤년이면 \(366 = 7 \times 52 + 2\)이므로 \(366 \equiv 2 \pmod 7\)이 되어 이틀 밀린다. 달력의 규칙성은 대부분 법 7의 합동으로 설명된다.

문제 13#

접근. 두 가정 중 더 강한 정보인 \(3 \mid x\)부터 쓴다 — \(x = 3k\)로 놓으면 목표 \(6 \mid x\)까지 남은 것은 \(k\)가 짝수라는 사실 하나다. 그 사실은 \(x\)가 짝수라는 다른 가정에서 나오고, 다리는 “홀수 \(\times\) 홀수 = 홀수”(1주차 문제 8)의 대우다.

풀이. \(2 \mid x\)이고 \(3 \mid x\)라 가정하자. 정의 2.1에 의해 \(x = 3k\)인 정수 \(k\)가 존재한다. 또 \(2 \mid x\)이므로 \(x\)는 짝수이고, 따라서 \(3k\)는 짝수이다. 여기서 \(k\)가 홀수라면, 3도 홀수이므로 1주차 문제 8(홀수와 홀수의 곱은 홀수)에 의해 \(3k\)가 홀수가 되어 \(3k\)가 짝수라는 것과 어긋난다. 그러므로 \(k\)는 짝수이고, 정의 1.1에 의해 \(k = 2m\)인 정수 \(m\)이 존재한다. 그러면

\[ x = 3k = 3(2m) = 6m \]

이고 \(m\)은 정수이므로, 정의 2.1에 의해 \(6 \mid x\)이다. \(\blacksquare\)

복기. 5주차 문제 9에서 나열 관찰로만 인정하고 쓰던 “2와 3의 공배수는 6의 배수”가 여기서 증명됐다. 7주차 문제 9, 25주차 문제 12, 30주차 문제 17이 이 결과를 그대로 인용한다. 8주차 문제 11(d)와 14주차 훈련 1이 쓰는 “공배수 = 최소공배수의 배수”의 일반형은 이번 주가 증명한 2와 3의 경우를 넘어서므로, 여전히 인정하고 쓰는 사실로 남는다. 몸통에 쓰인 “만약 ~라면 어긋나므로 ~이다”라는 서술은 다음 주 귀류법의 축소판이다. (검산: \(x = 24\)이면 \(2 \mid 24\), \(3 \mid 24\)이고 \(24 = 6 \times 4\) ✓.)

문제 14#

접근. 존재하지 않음을 보이는 방법은 가능한 값을 전부 훑는 것이다. 17주차 문제 9가 \(n^2\)의 법 4 값을 0과 1 두 개로 줄여 주므로, 각각에 (C4)로 1을 더해 \(n^2 + 1\)의 후보를 만들고 그 목록에 0이 없음을 확인한다.

풀이. \(n\)을 임의의 정수라 하자. 17주차 문제 9에 의해 \(n^2\)을 4로 나눈 나머지는 0 또는 1이므로, \(n^2 \equiv 0 \pmod 4\) 또는 \(n^2 \equiv 1 \pmod 4\)이다. 문제 4(반사성)에 의해 \(1 \equiv 1 \pmod 4\)이므로, (C4)를 적용하면

  • \(n^2 \equiv 0\)인 경우: \(n^2 + 1 \equiv 0 + 1 = 1 \pmod 4\)

  • \(n^2 \equiv 1\)인 경우: \(n^2 + 1 \equiv 1 + 1 = 2 \pmod 4\)

이다. 두 경우가 모든 정수 \(n\)을 빠짐없이 덮고, 어느 경우에도 \(n^2 + 1 \equiv 0 \pmod 4\)가 아니다. 따라서 \(n^2 + 1 \equiv 0 \pmod 4\)인 정수 \(n\)은 존재하지 않는다. \(\blacksquare\)

복기. “가능한 값의 목록을 만들고 목표가 그 목록에 없음을 보인다” — 존재하지 않음을 증명하는 표준 수법이고, 17주차 문제 17(\(n^2+2\)는 4의 배수가 아니다)을 합동 언어로 옮긴 것이다. 목록을 만드는 도구가 이번 주에는 (C4)와 (C5)다. (검산: \(n = 0, 1, 2, 3\)에서 \(n^2 + 1 = 1, 2, 5, 10\)이고 4로 나눈 나머지는 \(1, 2, 1, 2\) — 0이 없다 ✓.)

문제 15#

접근. 출발점은 \(10 - 1 = 9\)라는 사실 하나다. 여기서 \(10 \equiv 1 \pmod 9\)이 나오고, (C5)로 \(100 \equiv 1\)을 얻는다. 그다음 문제 9(b)로 계수 \(a, b\)를 붙이고 (C4)로 세 조각을 더하면 목표에 닿는다. 마지막 문장은 합동을 정의 20.1로 되돌린 뒤 2주차의 배수 정리 두 개로 잇는 자리다 — “나머지가 같다”는 §1.4에서 정한 대로 근거 목록에 없다.

풀이. \(10 - 1 = 9 = 9 \times 1\)이므로 \(9 \mid (10 - 1)\), 곧 \(10 \equiv 1 \pmod 9\)이다. (C5)를 \(10 \equiv 1\)과 \(10 \equiv 1\)에 적용하면 \(100 \equiv 1 \pmod 9\)이다. 문제 9(b)에 의해 양변에 정수를 곱해도 합동이 유지되므로

\[ 100a \equiv a \pmod 9, \qquad 10b \equiv b \pmod 9 \]

이고, 문제 4(반사성)에 의해 \(c \equiv c \pmod 9\)이다. (C4)를 앞의 두 식에 적용하면 \(100a + 10b \equiv a + b \pmod 9\)이고, 여기에 다시 (C4)로 \(c \equiv c\)를 더하면

\[ N = 100a + 10b + c \equiv a + b + c \pmod 9 \]

이다. \(\blacksquare\) (여기서 쓴 (C5)의 증명은 §2 예제 2.2 말미에서 조립되었고, 답안 형태로 적는 것이 문제 17이다.)

판정법이 되는 이유: \(N \equiv a+b+c \pmod 9\)이므로 정의 20.1에 의해 \(9 \mid \big(N - (a+b+c)\big)\)이다. 자릿수 합이 9의 배수이면 \(N = \big(N - (a+b+c)\big) + (a+b+c)\)가 두 배수의 합이므로 2주차 예제 2.2에 의해 \(9 \mid N\)이고, 거꾸로 \(9 \mid N\)이면 \(a+b+c = N - \big(N - (a+b+c)\big)\)가 두 배수의 차이므로 2주차 문제 7에 의해 \(9 \mid (a+b+c)\)이다. 곧 한쪽이 9의 배수인 것과 다른 쪽이 9의 배수인 것이 서로 같다.

복기. 이 증명이 쓴 것은 \(10 \equiv 1 \pmod 9\) 단 하나이고, 나머지는 (C4)와 (C5)로 그 사실을 자릿수만큼 퍼뜨린 것이다. 같은 논증이 임의 자릿수로 확장되며 (\(10^k \equiv 1^k = 1\)), 그 일반화의 엄밀한 처리가 31주차 문제 15다. 또 \(10 - 1 = 9\)는 3의 배수이기도 하므로 \(10 \equiv 1 \pmod 3\)이고, 똑같은 논증이 3의 배수 판정법을 준다. (검산: \(N = 342\)이면 \(3+4+2 = 9\)이고 \(342 = 9 \times 38\) ✓.)

문제 16#

접근. 등식이 참이라면 양변을 법 9로 줄인 값도 같아야 한다. 그러므로 좌변과 우변을 각각 법 9에서 줄여 비교하고, 값이 다르면 등식은 성립할 수 없다. 좌변을 줄이는 도구는 문제 15(자릿수 합)와 (C5)이고, 우변은 세 자리가 아니므로 정의로 직접 판정한다.

풀이. 좌변의 두 수는 세 자리이므로 문제 15가 그대로 적용된다 — 각 수는 자릿수 합과 법 9에서 합동이다. \(437 \equiv 4 + 3 + 7 = 14 \pmod 9\)이고, 다시 \(14 \equiv 1 + 4 = 5 \pmod 9\)이다 (\(14 - 5 = 9\)). 또 \(254 \equiv 2 + 5 + 4 = 11 \equiv 2 \pmod 9\)이다 (\(11 - 2 = 9\)). (C5)를 두 합동식에 적용하면

\[ 437 \times 254 \equiv 5 \times 2 = 10 \equiv 1 \pmod 9 \]

이다. 한편 주장된 값 \(110{,}898\)은 여섯 자리이므로 문제 15(세 자리 한정)가 닿지 않는다. 정의로 직접 판정한다 — \(110{,}898 - 0 = 110{,}898 = 9 \times 12322\)이므로 \(9 \mid 110{,}898\), 곧 \(110{,}898 \equiv 0 \pmod 9\)이다. (자릿수 합 \(1+1+0+8+9+8 = 27\)도 같은 값을 주지만, 임의 자릿수의 자릿수 합 규칙은 31주차 문제 15의 몫이므로 여기서는 검산으로만 쓴다.) 만약 \(437 \times 254 = 110{,}898\)이 참이라면 같은 수가 법 9에서 1과도 0과도 합동이어야 하는데, \(1 \not\equiv 0 \pmod 9\)이므로 그럴 수 없다. 따라서 이 계산은 틀렸다. \(\blacksquare\)

복기. 이 검산법은 “법 9의 나머지가 맞는가”만 확인하므로 틀림은 확정하고 맞음은 보장하지 않는다 — 필요조건 검사다. 실제 값은 \(110{,}998\)이고 \(110{,}998 - 1 = 110{,}997 = 9 \times 12333\)이므로 법 9에서 1 — 앞의 계산과 맞는다(자릿수 합 \(28\)로도 같은 값이 나온다). 옳은 답이 아닌데도 통과하는 값이 9의 배수만큼 떨어진 곳마다 있으므로, 통과했다고 옳다고 결론지을 수는 없다.

문제 17#

접근. 예제 2.2의 확인 17에서 만든 항등식 \(ac - bd = c(a-b) + b(c-d)\)가 몸통이다. 그 앞에 정의 번역, 뒤에 역번역을 붙이고, 두 덩어리가 각각 배수임을 2주차 훈련 1로, 합이 배수임을 2주차 예제 2.2로 근거 붙인다.

풀이. \(a \equiv b \pmod n\)이고 \(c \equiv d \pmod n\)이라 가정하자. 정의 20.1에 의해 \(n \mid (a - b)\)이고 \(n \mid (c - d)\)이다. 여기서 \(ac - bd\)에 \(-bc + bc\)를 더해 보면(값은 변하지 않는다)

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

이다. 2주차 훈련 1(배수에 임의의 정수를 곱해도 배수)에 의해 \(n \mid c(a - b)\)이고 \(n \mid b(c - d)\)이다. 2주차 예제 2.2(배수 두 개의 합은 배수)에 의해 \(n \mid \big(c(a-b) + b(c-d)\big)\), 곧 \(n \mid (ac - bd)\)이다. 따라서 정의 20.1에 의해 \(ac \equiv bd \pmod n\)이다. \(\blacksquare\)

복기. “빼고 더하기”는 목표에 필요한 덩어리가 식에 없을 때 그 덩어리가 나타나도록 항을 쪼개는 수법이다. 17주차 문제 16에서 \(x = (x-y)+y\)로 쓴 것과 같은 발상이고, 32주차의 귀납 단계에서 \(f(k+1)\)을 “\(f(k)\)의 배수 항 + 나머지”로 재배열할 때 다시 쓴다. 어느 항을 삽입할지는 도착점이 정한다 — 여기서는 \(bc\)를 넣었지만 \(ad\)를 넣어도 된다. \(ac - bd = ac - ad + ad - bd = a(c-d) + d(a-b)\)로 쪼개지며 결론은 같다. 삽입할 항은 두 덩어리가 인수로 남게 하는 것이면 되고, 그런 항이 유일할 필요는 없다. (검산: \(n = 6\)에서 \(17 \equiv 5\), \(8 \equiv 2\)이면 \(136 \equiv 10\) — \(136 - 10 = 126 = 6 \times 21\) ✓.)

문제 18#

접근. 재진술은 정의 번역이다 — \(n^2 = 8m + 1\)은 \(n^2 - 1 = 8m\), 곧 \(8 \mid (n^2 - 1)\)이고 이는 \(n^2 \equiv 1 \pmod 8\)이다. 재진술을 끝내면 두 홀수에 각각 적용하고 (C4)로 더하기만 하면 된다.

풀이. 재진술. 17주차 문제 15는 “\(n\)이 홀수이면 \(n^2 = 8m + 1\)인 정수 \(m\)이 존재한다”이다. 이 등식을 정리하면 \(n^2 - 1 = 8m\)이므로 정의 2.1에 의해 \(8 \mid (n^2 - 1)\)이고, 정의 20.1에 의해 이는 다음과 같다.

\[ n\text{이 홀수이면 } n^2 \equiv 1 \pmod 8 \]

증명. \(a\)와 \(b\)가 홀수라 가정하자. 위의 재진술을 \(a\)와 \(b\)에 각각 적용하면 \(a^2 \equiv 1 \pmod 8\)이고 \(b^2 \equiv 1 \pmod 8\)이다. (C4)를 이 두 합동식에 적용하면

\[ a^2 + b^2 \equiv 1 + 1 = 2 \pmod 8 \]

이다. \(\blacksquare\)

복기. 따름정리 하나가 바로 나온다 — 홀수 제곱 두 개의 합은 4의 배수가 될 수 없다. 법 8에서 나머지가 2이면 \(a^2 + b^2 = 8k + 2 = 4(2k) + 2\)로 법 4에서도 나머지가 2이기 때문이다. 이것이 19주차 문제 18에서 얻은 결과이고, 합동 언어로 쓰니 계산이 두 줄로 줄었다. 38주차에서는 같은 사실이 \(\mathbb{Z}_8\)의 홀수 대표원 제곱이 전부 \([1]\)이라는 형태로 다시 나온다. (검산: \(a = 3\), \(b = 5\)이면 \(9 + 25 = 34 = 8 \times 4 + 2\) ✓.)

문제 19#

접근. 여섯 조항을 차례로 대조하며 위반을 세고, 지적으로 끝내지 말고 교정본까지 적는다. 계산 자체는 옳으므로 고칠 것은 서술뿐이다 — 어떤 문장이 어떤 근거로 다음 문장을 낳는지가 드러나게 다시 쓴다.

풀이. 위반은 다섯 곳이다. ① 1조 위반. 첫 문장이 수식 “\(n = 2k+1\)”로 시작한다. 말로 시작해야 한다. ② 2조 위반. \(n\)과 \(k\)가 소개 없이 등장한다. \(n\)이 임의의 홀수인지 특정 수인지, \(k\)의 존재가 보장된 것인지 아무 선언이 없다. ③ 3조 위반. “\(2(2k^2+2k)+1 = \) 홀수”에서 수와 성질을 등호로 이었다. “홀수”는 수가 아니므로 등호의 오른쪽에 올 수 없다. ④ 4조 위반. \(\Rightarrow\)가 문장 사이의 접속사로 쓰였다. 산문에서는 “그러면”, “따라서”를 쓴다. ⑤ 6조 위반. “증명.”이라는 개시 표시가 없다. (\(\blacksquare\)는 있으므로 종료 표시만 갖춰져 있다.)

교정본. “증명. \(n\)을 홀수라 하자. 홀수의 정의에 의해 \(n = 2k+1\)인 정수 \(k\)가 존재한다. 그러면 \(n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\)이고, \(2k^2 + 2k\)는 정수이므로 \(n^2\)은 홀수이다. \(\blacksquare\)”

복기. 교정본과 원본의 계산은 한 글자도 다르지 않다 — 달라진 것은 각 줄이 어느 근거로 나왔는지를 읽는 사람이 복원할 수 있게 된 점뿐이다. 15주차 §1.8의 답안 A에서 시작한 글쓰기 훈련이 여기서 여섯 조항으로 완성되고, 24주차와 50주차의 시험에서 이 여섯 조항이 채점 대상이 된다.

문제 20#

접근. 닮은 점은 (C1)~(C3)을 등호의 세 성질과 짝지으면 되고, 다른 점은 “\(=\)가 묶는 것”과 “\(\equiv\)가 묶는 것”의 범위를 비교한다. 시계 계산은 법 12의 합동으로 번역한 뒤 (C4)로 정당화한다.

풀이. (예시 답안) 닮은 점 세 가지. 등호가 가진 반사성(\(a = a\)), 대칭성(\(a = b\)이면 \(b = a\)), 추이성(\(a = b\)이고 \(b = c\)이면 \(a = c\))을 \(\equiv \pmod n\)도 그대로 가진다 — 각각 (C1), (C2), (C3)이다. 그래서 합동식은 등식처럼 좌우를 바꾸거나 사슬로 이어 쓸 수 있고, (C4)(C5)에 의해 변끼리 더하고 곱할 수도 있다. 다른 점. \(=\)는 완전히 같은 대상만 묶지만, \(\equiv \pmod n\)은 17과 5처럼 서로 다른 수들을 “나머지가 같다”는 기준으로 같은 취급한다 — 같음의 기준이 느슨해진 것이다. (같음의 기준이 느슨해진 대가로 잃는 것도 있다: §1.5 확인 7에서 본 대로 양변을 공통 인수로 나누는 조작이 허용되지 않는다. 이 점을 다른 점으로 써도 된다.) 시계 계산. \(8 + 7 = 15\)이고 \(15 - 3 = 12 = 12 \times 1\)이므로 \(15 \equiv 3 \pmod{12}\)이다. 따라서 법 12의 세계에서 \(8 + 7\)은 3이 된다 — 8시에서 7시간 뒤가 3시인 것이 이 계산이다. “12를 넘으면 되감는” 산술이 (C4)로 정당화된다.

복기. 같음의 기준을 바꾸면 산술이 바뀐다는 관찰은 이 과정의 뒷부분 전체를 관통한다. 어떤 관계가 이런 “느슨한 같음”의 자격을 갖는지가 36~37주차 동치관계의 주제이고, 그렇게 묶어 만든 세계 \(\mathbb{Z}_n\)의 산술이 잘 정의되는지가 38주차의 주제다. 이번 주에 증명한 (C4)(C5)가 그때 연산의 자격 심사에 그대로 쓰인다.

다음 주 예고: 귀류법(proof by contradiction) — 결론을 부정한 채로 논리를 밀고 나가 어긋남에 도달하는 증명법을 다룬다. 이번 주 문제 13의 몸통에서 “만약 \(k\)가 홀수라면 어긋나므로”라고 쓴 대목이 그 축소판이다. 2500년 묵은 두 결과 “\(\sqrt{2}\)는 무리수”와 “소수는 무한히 많다”를 직접 증명하며, 11주차 문제 20에서 적어 둔 두 줄이 그때 완성된다.