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

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

예제 — 계산과 증명을 함께 만들기#

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

예제 2.1 — 호제법과 베주 계수#

과제. \(\gcd(42, 30)\)을 유클리드 호제법으로 구하고, \(\gcd(42,30) = 42x + 30y\)인 정수 \(x, y\)를 하나 찾아라.

설계 — 쓰기 전에 정하는 두 가지. 계산 문제에서도 출발점과 도착점을 먼저 정한다. 가정이 주는 것과 만들어야 할 것을 각각 수식으로 옮긴다.

말

수식 번역

가정 (주어진 것)

두 양의 정수 \(42\), \(30\)

나눗셈 정리를 걸 수 있는 쌍 \((42, 30)\)

목표 1 (구할 것)

\(\gcd(42,30)\)의 값

호제법의 마지막 \(0\) 아닌 나머지

목표 2 (만들 것)

베주 계수

\(\underline{\quad(?)\quad}\) 꼴의 등식 하나

확인 15. 목표 2 칸의 빈칸을 채워 보자. 정리 1.3이 존재를 보장하는 것은 정확히 어떤 꼴의 등식인가.

답

\(\gcd(42, 30) = 42 \times (\text{정수}) + 30 \times (\text{정수})\) 꼴의 등식.

정리 1.3은 이런 등식이 존재한다는 것만 말하므로, 값을 요구하는 이 과제에서는

존재 증명을 그대로 쓸 수 없다. 값을 만드는 절차가 호제법의 역대입이다.

1단계 — 호제법을 앞으로 밀어 답을 얻는다. 걸음 ①②③을 나머지가 \(0\)이 될 때까지 되풀이한다.

확인 16. 첫 줄을 적어 보자: \(42 = \underline{\quad} \times 30 + \underline{\quad}\). 몫과 나머지는 나눗셈 정리의 조건 \(0 \le r < 30\)을 만족해야 한다.

답

\(42 = 1 \times 30 + 12\). 몫 \(1\), 나머지 \(12\)이고 \(0 \le 12 < 30\)이다 ✓.

보조 명제 1.A에 의해 \(\gcd(42, 30) = \gcd(30, 12)\)이다.

확인 17. 남은 줄을 끝까지 적고 \(\gcd\)를 읽어 보자: \(30 = \underline{\quad} \times 12 + \underline{\quad}\), \(12 = \underline{\quad} \times 6 + \underline{\quad}\).

답

\(30 = 2 \times 12 + 6\), \(12 = 2 \times 6 + 0\).

나머지가 \(0\)이 되었으므로 걸음 ④에 따라 마지막으로 \(0\)이 아니었던 나머지가

답이다: \(\gcd(42, 30) = 6\).

2단계 — 답을 등식으로 고립시킨다. 역대입은 “\(6 = \cdots\)” 꼴의 줄에서 시작한다. 그 줄은 이미 호제법 안에 있다.

확인 18. 호제법의 어느 줄에서 \(6\)을 좌변으로 옮길 수 있는가. 그 줄을 \(6 = \cdots\) 꼴로 다시 적어 보자.

답

\(30 = 2 \times 12 + 6\)이라는 줄이다. \(2 \times 12\)를 이항하면

\(6 = 30 - 2 \times 12\)이다. 이 등식의 우변에는 \(42\)가 아직 없고 \(30\)과 \(12\)가 있다.

남은 일은 \(12\)를 \(42\)와 \(30\)으로 바꿔 넣는 것이다.

3단계 — 위 줄을 대입해 \(42\)와 \(30\)만 남긴다.

확인 19. \(12\)를 무엇으로 바꿔 넣는가. 바꿔 넣은 뒤 \(42\)끼리, \(30\)끼리 묶어 보자.

답

첫 줄 \(42 = 1 \times 30 + 12\)에서 \(12 = 42 - 30\)이다. 대입하면

\(6 = 30 - 2(42 - 30) = 30 - 2 \times 42 + 2 \times 30 = 3 \times 30 - 2 \times 42\)이다.

\(42\)의 계수는 \(-2\), \(30\)의 계수는 \(3\)이다. 대입할 때 괄호 앞의 \(-2\)를 두 항에

모두 분배해야 한다 — 이 자리에서 부호를 놓치는 경우가 많다.

확인 20. 결과를 정리 1.3의 꼴 \(\gcd = 42x + 30y\)로 적고, 검산 한 줄을 붙여 보자.

답

\(6 = 42 \times (-2) + 30 \times 3\)이므로 \(x = -2\), \(y = 3\)이다.

검산: \(42 \times (-2) + 30 \times 3 = -84 + 90 = 6\) ✓.

계수는 유일하지 않다 — \(x = 3\), \(y = -4\)도 \(126 - 120 = 6\)이므로 답이다.

정리 1.3은 존재만 주장하므로 어느 쌍을 제시해도 되고, 대조할 정답표가 없으므로

검산이 유일한 채점 수단이다.

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

증명의 한 줄

왜 이 줄을 쓰는가?

\(42 = 1 \cdot 30 + 12\)

걸음 ①. 나눗셈 정리로 \(0 \le 12 < 30\)인 나머지를 만든다. 보조 명제 1.A에 의해 \(\gcd(42,30) = \gcd(30,12)\)이다.

\(30 = 2 \cdot 12 + 6\)

걸음 ①②의 반복. \(\gcd(30,12) = \gcd(12,6)\)이고 나머지가 \(12\)에서 \(6\)으로 줄었다.

\(12 = 2 \cdot 6 + 0\)

나머지가 \(0\)이므로 걸음 ③이 끝난다.

따라서 \(\gcd(42, 30) = 6\)이다.

걸음 ④. \(\gcd(6,0) = 6\)이라는 정의 1.1의 직접 판정(확인 6)이 근거다.

\(6 = 30 - 2 \cdot 12\)

역대입의 시작. 답 \(6\)이 좌변에 오는 줄을 호제법에서 골라 이항한다.

\(12 = 42 - 1 \cdot 30\)

대입할 재료. 우변에 남은 \(12\)를 없애기 위해 그 위 줄을 \(12 = \cdots\) 꼴로 돌린다.

\(6 = 30 - 2(42 - 30) = 3 \cdot 30 - 2 \cdot 42\)

대입하고 \(42\)끼리, \(30\)끼리 묶는다(근거 ③). 괄호 앞의 부호를 두 항에 모두 분배한다.

곧 \(6 = 42 \cdot (-2) + 30 \cdot 3\)이다.

정리 1.3의 꼴 \(\gcd = ax + by\)에 맞춰 적는다. 계수의 순서를 \(a, b\)에 맞추는 것도 답안의 일부다.

검산: \(-84 + 90 = 6\) ✓

계수가 유일하지 않으므로 대조할 정답표가 없다. 검산이 유일한 확인 수단이다.

[주의] 자주 하는 실수: 나머지를 도로 계산하기. 역대입 중에 \(42 - 30\)을 \(12\)로 되돌려 계산하면 원래 자리로 돌아간다. 역대입에서 지켜야 할 것은 \(42\)와 \(30\)을 문자처럼 그대로 두고 계수만 모으는 것이다. 수를 끝까지 미루는 이 습관이 문제 7(b)의 긴 계산에서 결정적이다.

예제 2.2 — 유클리드 보조정리 (정리 1.4)#

명제. \(p\)가 소수이고 \(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)이다.

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

확인 21. 번역표를 채워 보자. 결론의 꼴 “\(p \mid a\) 또는 \(p \mid b\)”에 붙는 서식은 \(\underline{\quad}\)(S15주차 정의 15.2)이고, 부정할 쪽은 \(\underline{\quad}\)이며, 그 부정에서 얻는 말은 \(\underline{\quad}\), 그 말을 바꿀 등식은 \(\underline{\quad}\)이다.

답

서식은 소거법이다 — 결론이 \(\lor\)이고 어느 쪽이 참인지 가정만으로는 지목되지

않는다(S15주차 §1.7의 판정표).

부정할 쪽은 \(p \mid a\)이고, 곧 “\(p \nmid a\)라 하자”로 시작한다. \(p \mid b\) 쪽을

부정해도 대칭이라 사정이 같다.

그 부정에서 얻는 말은 “\(\gcd(p, a) = 1\)”이다.

그 말을 바꿀 등식은 따름정리 1.3.1이 주는 \(px + ay = 1\)이다.

확인 22. 등식 \(px + ay = 1\)을 손에 쥔 뒤 \(b\)를 어떻게 등장시키는가. 등장시킨 뒤 결론까지 가는 데 필요한 근거는 무엇인가.

답

양변에 \(b\)를 곱한다(근거 ③): \(pbx + aby = b\).

좌변의 두 항이 모두 \(p\)의 배수임을 밝히면 (D2)에 의해 그 합인 \(b\)도 \(p\)의

배수다. 첫 항은 \(pbx = p(bx)\)이므로 자명하고, 둘째 항은 가정 \(p \mid ab\)에서

\(ab = pm\)인 정수 \(m\)이 있으므로 \(aby = pmy = p(my)\)이다.

§1.1이 멈춘 자리에서 필요했던 “\(b\)를 무대에 올리는 방법”이 정확히 이 곱셈이다.

증명의 한 줄

왜 이 줄을 쓰는가?

\(p\)를 소수, \(a, b\)를 정수라 하고 \(p \mid ab\)라 하자.

대상을 문자로 잡고 가정을 선언한다.

소거법을 쓴다. \(p \nmid a\)라 하자.

소거법의 걸음 ①. 이 줄이 없으면 아래 유도가 무조건 참인 것으로 읽혀 거짓 명제를 주장하게 된다(S15주차 §1.4의 삭제 실험).

\(\gcd(p, a)\)는 \(p\)의 양의 약수이고, \(p\)가 소수이므로 그것은 \(1\) 또는 \(p\)이다.

소수의 정의(1권 15주차 정의 15.2)를 여기서 푼다. 소수 가정이 소비되는 유일한 자리다.

\(\gcd(p,a) = p\)이면 \(p \mid a\)가 되어 앞 줄의 가정과 충돌하므로 \(\gcd(p, a) = 1\)이다.

걸음 ①이 실제로 소비되는 자리(S15주차의 기준 ㄴ). \(\gcd\)가 공약수라는 정의 1.1의 조각을 쓴다.

따름정리 1.3.1에 의해 \(px + ay = 1\)인 정수 \(x, y\)가 존재한다.

말이 등식으로 바뀌는 줄. 이 한 줄이 §1.1의 막힘을 푼다.

양변에 \(b\)를 곱하면 \(pbx + aby = b\)이다.

근거 ③. 결론에 있어야 할 \(b\)를 무대에 올리는 조작이며, 곱할 등식이 있어야만 가능하다.

\(p \mid pbx\)이고, \(p \mid ab\)이므로 \(ab = pm\)인 정수 \(m\)이 있어 \(aby = p(my)\), 곧 \(p \mid aby\)이다.

두 항 각각이 \(p\)의 배수임을 밝힌다. 가정 \(p \mid ab\)가 소비되는 유일한 자리다.

(D2)에 의해 \(p \mid (pbx + aby)\)이고, 그 값이 \(b\)이므로 \(p \mid b\)이다.

선형결합 성질로 두 항의 합을 넘긴다. 좌변이 \(b\)와 같다는 것은 앞 줄의 등식이다.

따라서 \(p \mid a\) 또는 \(p \mid b\)이다. \(\blacksquare\)

소거법의 걸음 ③. 조건문 분해로 원래의 \(\lor\) 결론을 회수한다. 이 줄이 없으면 증명된 것은 조건문뿐이다.

복기. S15주차 문제 10이 이 증명을 소거법의 표준 형태로 세우면서 베주 항등식만 기성품으로 인용해 두었다. 정리 1.3이 증명된 지금 그 인용이 정당해졌고, 증명 전체가 빈 자리 없이 선다. 이식 가능한 조합은 “서로소라는 말을 등식으로 바꾼 뒤 양변에 곱한다”는 두 줄이며, 문제 11\(\cdot\)12\(\cdot\)18과 훈련 2가 이 조합을 그대로 쓴다.

예제 2.3 — 산술의 기본정리의 유일성#

명제. \(1\)보다 큰 정수의 소인수분해는 소수들의 순서를 무시하면 유일하다.

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

확인 23. 설계 네 칸을 채워 보자. 서식은 \(\underline{\quad}\)(C8주차 §1.4)이고, 무대는 \(\underline{\quad}\)이며, 반례에서 꺼낼 등식은 \(\underline{\quad}\), 그 등식에 걸 정리는 \(\underline{\quad}\)이다.

답

서식은 최소 반례법이다. 유일성은 “모든 \(n \ge 2\)에 대해 …”의 꼴이고,

확인 13이 밝혔듯 \(n\)보다 작은 곳의 정보가 필요하므로 최소 반례가 맞는 서식이다.

무대는 \(2\) 이상의 정수 전체.

반례에서 꺼낼 등식은 \(n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m\) (서로 다른 두 소인수분해).

걸 정리는 정리 1.4의 일반형이다 — \(p_1\)이 오른쪽 곱을 나누므로 어떤 \(q_j\)를 나눈다.

증명. 모순을 위해, 소인수분해가 유일하지 않은 \(2\) 이상의 정수가 존재한다고 가정하자. 그런 정수들의 집합은 공집합이 아닌 자연수의 부분집합이므로 최소원리에 의해 최소원소를 가진다. 그것을 \(n\)이라 하고, \(n\)의 서로 다른 두 소인수분해를

\[ n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m \]

이라 하자 (모든 \(p_i\)와 \(q_j\)는 소수). \(p_1\)이 좌변을 나누므로 \(p_1 \mid n\)이고, 따라서 \(p_1 \mid q_1 q_2 \cdots q_m\)이다. 정리 1.4의 일반형에 의해 어떤 \(j\)에 대해 \(p_1 \mid q_j\)이다. \(q_j\)는 소수이므로 그 양의 약수는 \(1\)과 \(q_j\)뿐이고 \(p_1 > 1\)이므로 \(p_1 = q_j\)이다. 오른쪽 목록의 순서를 바꿔 \(j = 1\)이라 해도 무방하다 — 유일성의 진술이 순서를 무시하기 때문이다. 양변을 \(p_1 = q_1\)로 나누면

\[ \frac{n}{p_1} = p_2 \cdots p_k = q_2 \cdots q_m \]

이다. \(p_1 \ge 2\)이므로 \(\frac{n}{p_1} < n\)이고, \(n\)이 최소 반례였으므로 \(\frac{n}{p_1}\)의 소인수분해는 유일하다. 따라서 \(p_2, \ldots, p_k\)와 \(q_2, \ldots, q_m\)은 순서를 무시하면 같은 목록이고 \(k - 1 = m - 1\)이다. 여기에 \(p_1 = q_1\)을 되돌려 붙이면 \(n\)의 두 분해도 순서를 무시하면 같고 \(k = m\)이다. 이는 두 분해가 서로 다르다고 한 가정과 모순이다.

따라서 유일하지 않은 정수는 존재하지 않고, \(1\)보다 큰 모든 정수의 소인수분해는 순서를 무시하면 유일하다. \(\blacksquare\)

이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 원서의 증명과 실전의 답안은 처음부터 끝까지 이런 산문이다. 이번 주의 목표는 이 산문을 백지에서 재현하는 것이다.

(\(\frac{n}{p_1} = 1\)이 되는 경우도 규칙 안에 있다 — 그때는 \(k = m = 1\)이고 \(n = p_1 = q_1\)이라 두 분해가 처음부터 같다. 소수 하나도 없는 곱을 \(1\)로 읽으면 위 논증이 그대로 통한다.)

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

예제 2.1은 계산이고 2.2와 2.3은 증명이므로 겉모습이 다르다. 그럼에도 밟은 순서는 같다. 대응표의 빈칸을 채워 보자.

걸음

예제 2.1

예제 2.2

예제 2.3

손에 쥔 말

“\(42\)와 \(30\)의 최대공약수”

“\(p\)와 \(a\)는 서로소”

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

말을 등식으로 바꾸는 도구

나눗셈 정리(호제법)

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

정리 1.4의 일반형

얻은 등식

\(42 = 1 \cdot 30 + 12\) 등

\(px + ay = 1\)

\(p_1 = q_j\)

등식을 소비하는 조작

역대입

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

양변을 \(p_1\)로 나눠 소거

마무리

검산

(D2)로 \(p \mid b\)

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

확인 24. 표의 (1)~(4)를 채워 보자.

답

(1) “\(n\)의 두 소인수분해가 서로 다르다”.

(2) 따름정리 1.3.1(베주 항등식).

(3) 양변에 \(b\)를 곱한다.

(4) \(\frac{n}{p_1}\)의 유일성과 대조해 모순을 얻고 가정을 철회한다.

확인 25. 세 예제가 공통으로 한 일을 한 문장으로 적어 보자. 그리고 §1.1의 막힘이 어느 걸음에서 풀리는지 지목해 보자.

답

공통으로 한 일: **말로 주어진 조건을 등식으로 바꾼 뒤, 그 등식에 한 번의 대수

조작을 가해 결론의 재료를 만들었다.**

§1.1의 막힘이 풀리는 곳은 둘째 걸음이다. 말을 쥐고 있는 한 대입할 것도 곱할

것도 없었고, 등식이 하나 생기는 순간 셋째 걸음의 조작이 가능해진다. 이번 주의

세 정리는 각각 “어떤 말을 어떤 등식으로 바꿔 주는가”로 요약된다.

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

백지 암기 대상

정수론 답안의 서식

① 말 확인 — 가정과 결론에서 등식이 아닌 낱말(공약수\(\cdot\)서로소\(\cdot\)소수\(\cdot\)분해)을 표시한다.

② 등식으로 번역 — 그 낱말을 등식으로 바꿔 주는 정리를 고른다: 나머지가 필요하면 나눗셈 정리, 서로소가 필요하면 베주, 소수가 곱을 나누면 유클리드 보조정리.

③ 조작 — 얻은 등식에 대입\(\cdot\)곱셈\(\cdot\)소거 중 하나를 가해 결론의 재료를 만든다.

④ 근거 명시 — 각 줄이 (D1)~(D3), 근거 ①~④ 중 무엇인지 밝힌다.

⑤ 마무리 — 계산은 검산으로, 증명은 인용한 정의\(\cdot\)정리의 번호를 대며 닫는다.

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

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

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

과제. \(\gcd(35, 15)\)를 호제법으로 구하고 베주 계수를 찾아라.

호제법. \(35 = 2 \cdot 15 + \underline{\quad(1)\quad}\)이고, \(15 = 3 \cdot 5 + 0\)이다. 나머지가 \(0\)이 되었으므로 걸음 ④에 의해 \(\gcd(35, 15) = \underline{\quad(2)\quad}\)이다.

역대입. 첫 줄을 \(5 = \cdots\) 꼴로 돌리면 \(5 = 35 - 2 \cdot 15\)이다. 정리 1.3의 꼴에 맞춰 적으면

\[ 5 = 35 \cdot \underline{\quad(3)\quad} + 15 \cdot \underline{\quad(4)\quad} \]

이다.

검산. \(35 \cdot 1 + 15 \cdot (-2) = 35 - 30 = 5\) ✓.

뜻. 이 등식이 있으면 “\(5\)는 \(35\)와 \(15\)의 양의 정수 \(\underline{\quad(5)\quad}\) 중 가장 작은 것”임이 정리 1.3으로 보증된다.

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

이번에는 구조 낱말과 근거 문장도 빈칸이다. 예제 2.2의 두 줄 조합을 소수 대신 서로소 조건에서 쓰는 훈련이다.

명제. 정수 \(a, b, c\)에 대해, \(\gcd(a, b) = 1\)이고 \(a \mid bc\)이면 \(a \mid c\)이다.

증명. \(\gcd(a,b) = 1\)이고 \(a \mid bc\)라 하자. \(\gcd(a,b) = 1\)이므로 \(\underline{\quad(1)\quad}\)에 의해

\[ ax + by = \underline{\quad(2)\quad} \]

인 정수 \(x, y\)가 존재한다. 결론에 \(c\)가 있어야 하므로 양변에 \(\underline{\quad(3)\quad}\)를 곱하면

\[ acx + bcy = c \]

이다. 첫 항은 \(acx = a(cx)\)이므로 \(a \mid acx\)이고, 둘째 항은 가정 \(\underline{\quad(4)\quad}\)에서 \(bc = ak\)인 정수 \(k\)가 있으므로 \(bcy = a(ky)\), 곧 \(a \mid bcy\)이다. 따라서 \(\underline{\quad(5)\quad}\)에 의해 \(a \mid (acx + bcy)\)이고, 그 값이 \(c\)이므로 \(a \mid c\)이다. \(\blacksquare\)

관찰. 이 명제에서 \(a\)를 소수 \(p\)로 두고 경우를 한 번 나누면 정리 1.4가 따라 나온다 — \(p \mid b\)이면 결론이 곧바로 성립하고, \(p \nmid b\)이면 \(\gcd(p, b) = 1\)이라 이 명제를 걸 수 있기 때문이다. 곧 유클리드 보조정리는 이 명제의 \(\underline{\quad(6)\quad}\)이다.

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

이번에는 §2 관찰의 서식 다섯 칸을 통째로 채운다.

명제. 둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해 \(d = \gcd(a, b)\)라 하자. 그러면 \(\dfrac ad\)와 \(\dfrac bd\)는 서로소이다.

답안의 뼈대.

  • ① 말 확인: \(\underline{\quad(1)\quad}\)

  • ② 등식으로 번역: \(\underline{\quad(2)\quad}\)

  • ③ 조작: \(\underline{\quad(3)\quad}\)

  • ④ 근거 명시: \(\underline{\quad(4)\quad}\)

  • ⑤ 마무리: \(\underline{\quad(5)\quad}\)

(안내: \(\frac ad\)와 \(\frac bd\)가 정수라는 것부터 밝혀야 한다 — \(d\)가 \(a\)와 \(b\)의 공약수라는 정의 1.1의 조각이 그 근거다. 그리고 결론이 “서로소”이므로 목표 쪽에서는 따름정리 1.3.1의 어느 방향을 쓰는지 고르는 일이 걸음 ②에 포함된다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.

호제법과 베주 계산은 나눗셈 줄을 하나도 빼지 않고 적고, 정리 증명은 베주 \(\to\) 유클리드 보조정리 \(\to\) 유일성의 사슬 중 어느 고리를 쓰는지 밝힌다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 이번 주 답안의 채점 항목은 넷이다.

① 계산 문제에서 나눗셈 줄이 전부 적혀 있는가. “\(\gcd = 6\)”만 적은 답안은 절차를 보이지 않은 것이다.

② 정리를 인용할 때 가정이 충족됨을 밝혔는가. 특히 정리 1.4는 “\(p\)가 소수”를 확인하지 않으면 인용 자격이 없다.

③ “서로소이므로”에서 곧바로 다음 줄로 넘어가지 않고 등식으로 바꾸는 줄을 적었는가. 그 줄이 §1.1의 막힘을 푸는 유일한 줄이다.

④ 베주 계수를 구한 답안에 검산이 붙어 있는가. 계수는 유일하지 않으므로 검산이 유일한 확인 수단이다.

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

기본 ●○○#

1. [백지] GCD\(\cdot\)유클리드 호제법\(\cdot\)베주 항등식\(\cdot\)유클리드 보조정리\(\cdot\)FTA(존재+유일)를 쓰시오.

힌트

정의는 §1.3의 조각 표와 함께, 절차는 §1.4의 걸음 표와 함께 외운다. 조각과 걸음마다

“빼면 무엇이 무너지는가”를 붙여 두면 잊은 조각을 남은 조각에서 재구성할 수 있다.

2. 유클리드 호제법으로 GCD를 구하시오. (a) \(\gcd(24, 36)\) (b) \(\gcd(17, 5)\) (c) \(\gcd(100, 64)\)

힌트

(a)는 작은 수가 앞에 있다. 정의 1.1이 대칭이므로 \(\gcd(24,36) = \gcd(36,24)\)로

바꿔 놓고 시작하면 걸음 ①의 조건 \(0 \le r < b\)가 곧바로 만족된다.

3. 예제 2.1(\(\gcd(42,30)\) 베주)을 백지 재현하시오.

힌트

호제법 세 줄을 먼저 적고, 그다음에 역대입을 시작한다. 역대입의 첫 줄은 답 \(6\)이

좌변에 오도록 이항한 줄이며, 그 줄은 호제법 안에 이미 있다.

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

힌트

훈련 1은 수만 바꾼 예제 2.1이고, 훈련 2는 예제 2.2에서 “소수”를 “서로소”로 바꾼

것이다. 훈련 3은 §2 관찰의 다섯 칸을 순서대로 채운다.

5. 예제 2.2(유클리드 보조정리 증명)를 백지 재현하시오.

힌트

아홉 줄의 순서를 먼저 여백에 적는다: 가정 \(\to\) 소거법 걸음 ① \(\to\) 소수의 약수 \(\to\)

\(\gcd = 1\) \(\to\) 베주 \(\to\) 양변에 \(b\) \(\to\) 두 항이 배수 \(\to\) (D2) \(\to\) 걸음 ③.

6. \(\gcd(a, b) = 1 \iff ax + by = 1\) (서로소 판정)의 한 방향(\(\Leftarrow\))을 증명하시오.

힌트

\(d = \gcd(a,b)\)라 두고 \(d \mid a\), \(d \mid b\)에서 출발한다. (D2)를 걸면 \(d\)가 어떤

수를 나누는가. 그 수의 양의 약수는 무엇뿐인가.

표준 ●●○#

7. \(\gcd(a, b) = ax + by\)의 베주 계수를 구하시오: (a) \(\gcd(14, 9)\) (b) \(\gcd(55, 34)\) (연속 피보나치 — 호제법이 가장 느린 경우).

힌트

(b)는 나눗셈 줄이 여덟 개이고 몫이 거의 전부 \(1\)이다. 역대입에서 수를 도로

계산하지 말고 두 원본 \(55\)와 \(34\)의 계수만 모은다 — 예제 2.1의 실수 상자가

경고한 그 습관이다. 한 줄 올라갈 때마다 검산하면 부호 오류를 초기에 잡는다.

8. 유클리드 보조정리로 \(\sqrt3\)이 무리수임을 완전 증명하시오 (1권 21주차 문제 7과 C8주차 문제 14가 부품으로 빌려 쓴 “\(3 \mid a^2 \Rightarrow 3 \mid a\)”를 이제 보조정리 증명 완료 상태로).

힌트

C7주차 예제 2.2의 4단 서식을 그대로 쓰되, “\(3 \mid a^2\)이므로 \(3 \mid a\)”라는 줄에

붙일 근거가 이제 정리 1.4임을 명시한다. \(a^2 = a \cdot a\)로 보면 정리 1.4의 \(ab\) 꼴이다.

문제 9\(\cdot\)18이 처음 쓰는 도구 — 소인수의 지수

정리 1.5의 유일성이 서면 \(n \ge 2\)를 \(n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\)

(서로 다른 소수 \(p_i\), 양의 정수 \(e_i\))로 적는 표준형이 확정된다. 각 소수 \(p\)에

대해 “\(n\)의 소인수분해에서 \(p\)의 지수”라는 수가 하나로 정해지고, 그것을

비교하는 논증이 가능해진다. 곱셈에 대해서는 지수가 더해지므로 \(n^2\)에서 각

지수는 두 배, 곧 짝수다. 유일성이 없으면 “그 지수”라는 말 자체가 성립하지

않는다 — 문제 9와 18은 이 도구 위에서만 굴러간다.

9. FTA 유일성으로 “\(\sqrt{12}\)는 무리수”를 증명하시오 (\(12 = 2^2 \cdot 3\), 완전제곱 아님 — 소인수 3의 지수가 홀수).

힌트

\(\sqrt{12} = \frac ab\)라 두고 분모를 없애면 \(12b^2 = a^2\)이다. 양변에서 소수 \(3\)의

지수만 세어 비교한다. 좌변의 \(12\)가 \(3\)을 하나 갖고 \(b^2\)이 짝수 개를 보태므로

좌변은 홀수, 우변은 짝수다.

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

Result. \(6 \mid ab\)이면 \(6 \mid a\) 또는 \(6 \mid b\).

증명. 유클리드 보조정리에 의해 성립.

힌트

평가는 두 물음으로 나눈다. ① 명제 자체가 참인가 — 작은 수로 반례를 찾아본다.

② 인용한 정리의 가정이 충족되는가 — 정리 1.4의 첫 낱말을 다시 읽는다.

11. 베주로 일차부정방정식: \(14x + 9y = 1\)의 정수 해를 하나 구하시오 (문제 7(a)의 베주 계수 활용).

새 낱말 — 일차부정방정식 (linear Diophantine equation)

미지수가 여럿이고 정수 해만 인정하는 방정식 \(ax + by = c\)를 일차부정방정식이라

한다. 정리 1.3은 \(c = \gcd(a,b)\)일 때 해가 존재함을 말하고, 호제법의 역대입이 그

해를 하나 준다. 해가 하나 있으면 무한히 많다 — \((x_0, y_0)\)이 해일 때

\(x = x_0 + \frac{b}{d}t\), \(y = y_0 - \frac{a}{d}t\) (\(d = \gcd(a,b)\), \(t \in \mathbb{Z}\))도

해임을 대입으로 확인할 수 있다. 이 일반해가 모든 해라는 사실은 지금은 인정하고

쓴다(증명은 훈련 3의 결과를 쓰면 두 줄이다).

힌트

새로 계산할 것이 없다. 문제 7(a)에서 이미 \(1 = 14 \cdot 2 + 9 \cdot (-3)\)을 얻었으므로

그 계수를 그대로 옮겨 적고 검산만 붙인다.

12. “연속한 두 정수는 서로소”(\(\gcd(n, n+1) = 1\))를 베주로 증명하시오.

힌트

따름정리 1.3.1의 (\(\Leftarrow\)) 방향, 곧 문제 6이 증명한 쪽을 쓴다. 계수를 찾는

것이 전부이고, \(n+1\)과 \(n\)의 차가 \(1\)이라는 사실이 그 계수를 곧바로 준다.

13. 유클리드 보조정리 일반화: “\(p\) 소수, \(p \mid a_1 a_2 \cdots a_n\)이면 어떤 \(a_i\)에 대해 \(p \mid a_i\)”를 귀납으로 증명하시오 (예제 2.2를 부품으로).

힌트

귀납 단계에서 \(a_1 \cdots a_{n+1}\)을 두 덩어리 \((a_1 \cdots a_n)\)과 \(a_{n+1}\)의 곱으로

묶는다. 그러면 곱이 두 개짜리가 되어 예제 2.2를 그대로 걸 수 있고, 두 갈래 중

앞쪽에 귀납 가정을 쓴다.

14. FTA 응용: 임의의 정수 \(n \ge 2\)의 약수 개수를 소인수분해로 구하는 공식을 설명하시오 (\(n = p_1^{e_1} \cdots p_k^{e_k}\)이면 약수 개수 \((e_1+1)\cdots(e_k+1)\) — 예 \(12 = 2^2 \cdot 3\)의 약수 \((2+1)(1+1) = 6\)개: \(1,2,3,4,6,12\)).

힌트

두 가지를 각각 밝혀야 한다. ① \(n\)의 양의 약수는 반드시 \(p_1^{f_1} \cdots p_k^{f_k}\)

(\(0 \le f_i \le e_i\)) 꼴이다. ② 서로 다른 지수 조합은 서로 다른 수를 준다. 두

주장 모두 정리 1.5의 유일성이 근거다.

도전 ●●●#

15. (FTA 유일성 완전 증명) 예제 2.3을 백지에서 완전 재현하고, “유클리드 보조정리 없이는 유일성이 무너진다”를 힐베르트 수 \(H = \{1, 5, 9, 13, \ldots\}\) (\(4k+1\) 꼴)에서 예로 보이시오 (\(441 = 21 \cdot 21 = 9 \cdot 49\), \(9, 21, 49\)가 \(H\)에서 더 못 쪼개짐 \(\to\) 유일성 실패).

힌트

뒷부분은 세 가지를 각각 확인해야 한다. ① \(H\)가 곱셈에 닫혀 있다 —

\((4a+1)(4b+1)\)을 전개한다. ② \(9, 21, 49\)가 \(H\) 안에서 더 쪼개지지 않는다 —

정수 범위의 인수를 나열하고 그중 \(H\)에 드는 것이 있는지 본다. ③ 정리 1.4가

\(H\)에서 거짓이다 — \(21\)과 \(441 = 9 \cdot 49\)로 확인한다.

16. (베주 완전 증명) 베주 항등식을 최소원리로 완전 증명하시오 (개념 절의 증명을 백지 재현 — \(S = \{ax+by > 0\}\)의 최소원 \(d\)가 \(a, b\)를 나눔).

힌트

1권 33주차의 최소원리 4단 서식대로 순서를 먼저 적는다: 집합 지정 \(\to\) 비공집합

확인 \(\to\) 최소원소 잡기 \(\to\) 모순. 비공집합 확인에서 \(a^2 + b^2\)을 제시하는 줄과,

나머지 \(r\)을 선형결합으로 다시 쓰는 줄을 빠뜨리기 쉽다.

17. (무한 소수) 소수가 무한히 많음을 FTA를 이용해 재증명하시오 (S11주차 문제 15와 다른 각도 — 유한 가정 시 \(N = p_1 \cdots p_k + 1\)이 어떤 소수로도 안 나뉨, FTA 존재와 모순).

힌트

\(N\)이 소수인지 아닌지 따지지 않는다. 필요한 것은 “\(N \ge 2\)이므로 소인수를 적어도

하나 가진다”는 정리 1.5의 존재 부분뿐이고, 그 소인수가 목록 안에 있어야 한다는

가정에서 모순이 나온다. 모순을 만드는 줄은 (D2)다.

이 문제가 처음 쓰는 낱말 — 최소공배수 (least common multiple)

두 양의 정수 \(a, b\)를 모두 배수로 갖는 양의 정수를 \(a\)와 \(b\)의 양의 공배수라

하고, 그중 가장 작은 것을 최소공배수라 하며 \(\operatorname{lcm}(a,b)\)로 쓴다.

존재는 최소원리가 준다 — \(ab\)가 양의 공배수이므로 양의 공배수의 집합은 공집합이

아니고, 공집합이 아닌 양의 정수 집합에는 최소원소가 있다(1권 33주차). 정의 1.1과

짝을 이루는 낱말이며, 이 상자가 §1.8의 근거 ①에 올리는 항목이다. C2주차 문제 16이

“\(A_m \cap A_n = A_{\operatorname{lcm}(m,n)}\)의 일반형에 필요한 도구는 C15주차의

최대공약수와 최소공배수”라고 적으며 이 자리를 지목해 두었다.

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

Result. \(\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab\) (양의 정수).

증명. \(a = 4, b = 6\)이면 \(\gcd = 2\), \(\operatorname{lcm} = 12\), \(2 \cdot 12 = 24 = 4 \cdot 6\) ✓. 따라서 성립.

힌트

평가에서 지적할 것과 대안으로 제시할 것이 따로 있다. 지적은 1권 1주차 이래의

기준이면 충분하다. 대안은 문제 9 앞의 도입 상자가 준 도구로 만든다 — 각 소수의

지수를 \(\gcd\)와 \(\operatorname{lcm}\)에서 각각 어떻게 읽는지 정한 뒤,

\(\min(s,t) + \max(s,t)\)를 계산한다.

19. (설계) 중국인 나머지 정리 맛보기: 연립합동 “\(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\)”의 해를 구하고, 그 해가 법 \(15\)에서 유일함을 밝히시오.

이 문제가 쓰는 사실 — 서로소인 두 법의 결합

\(m \mid k\)이고 \(n \mid k\)일 때 \(mn \mid k\)는 일반적으로 거짓이다(\(m = n = 2\),

\(k = 2\)가 반례다). 참이 되려면 \(\gcd(m,n) = 1\)이 필요하고, 그 조건 아래의 증명은

베주 두 줄이다. C6주차 문제 15가 \(m = 2\), \(n = 3\)의 사례를 다루면서 일반형을

이번 주로 미뤄 두었다 — 유일성 부분이 그 일반형을 쓴다. 증명은 §6의 문제 19에 있다.

힌트

존재는 두 길이 있다. 하나는 \(x \equiv 2 \pmod 3\)인 수를 작은 것부터 나열해

둘째 조건에 걸리는 것을 고르는 길이고, 다른 하나는 \(3u + 5v = 1\)을 먼저 구한 뒤

\(x = 2 \cdot 5v + 3 \cdot 3u\)로 조립하는 길이다. 뒤쪽이 일반 법에서도 통하는 설계다.

20. (서술) (a) “베주 \(\to\) 유클리드 보조정리 \(\to\) FTA 유일성”의 사슬을 예제 2.2\(\cdot\)2.3으로 정리하고, 왜 유일성이 유클리드 보조정리를 필요로 하는지(힐베르트 수의 반례) 세 문장 이내로 쓰시오. (b) 이번 주가 청산한 “외상”(C7주차 §1.8\(\cdot\)C8주차 §1.7\(\cdot\)C11주차 §1.7\(\cdot\)C13주차 §1.8의 네 자리)을 두 문장 이내로 정리하시오.

힌트

(a)의 축은 확인 13이다 — 유일성 증명이 보조정리를 부르는 자리는 “지울 짝을

찾는 일” 한 곳이며, 그 자리가 비면 무엇이 일어나는지가 힐베르트 수의 사례다.

(b)는 §1.8의 “지워지는 표시” 표에 적힌 네 곳을 자기 말로 옮긴다.

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

이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다.

요일

할 일

1일차

원서 Chartrand 12장 통독 — 모르는 문장은 표시만 하고 통과한다

2일차

교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다

3일차

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

4일차

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

5일차

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

1차 시도 — 틀 카드 허용. 유클리드 호제법의 네 걸음(§1.4), 정수론 답안의 서식(§2 관찰), 근거 목록(§1.8)만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

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

  • 정의 1.1과 1.2를 조각 그대로 썼다 (“둘 다 \(0\)은 아닌”, “가장 큰 것”까지).

  • 유클리드 호제법의 네 걸음을 쓰고, 걸음마다 그것을 빼면 무엇이 무너지는지 한 줄씩 적었다.

  • 보조 명제 1.A를 진술하고 (D2) 두 번으로 증명했다.

  • 예제 2.1을 재현했고, 역대입에서 \(42\)와 \(30\)을 도로 계산하지 않았다.

  • 정리 1.3을 최소원리로 증명했고, \(S \ne \varnothing\) 확인 줄과 나머지 \(r\)을 선형결합으로 다시 쓰는 줄을 모두 적었다.

  • 예제 2.2를 재현했고, 소수 가정이 소비되는 줄과 가정 \(p \mid ab\)가 소비되는 줄을 손가락으로 짚었다.

  • 예제 2.3을 재현했고, 정리 1.4의 일반형을 인용한 자리를 짚었다.

  • 정리 1.4가 합성수에서 거짓임을 반례로 보였다.

  • 원서 12장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다.

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

막힌 지점

처방

호제법의 첫 줄에서 몫을 어떻게 잡을지 모르겠다

§1.4의 걸음 ① — 몫은 취향이 아니라 나눗셈 정리가 \(0 \le r < b\)로 지정한다

역대입에서 원래 수로 돌아가 버린다

예제 2.1의 실수 상자 — 두 원본을 문자처럼 두고 계수만 모은다

베주 증명에서 최소원리 인용이 어색하다

§1.5 확인 7과 1권 33주차의 4단 서식 — 비공집합 확인이 인용의 자격이다

“서로소이므로”에서 다음 줄이 나오지 않는다

§1.1의 시도와 확인 1 — 말은 등식이 아니다. 따름정리 1.3.1을 부르는 줄이 빠졌다

유클리드 보조정리를 합성수에 걸었다

§1.6 확인 11 — 소수 가정이 소비되는 줄이 한 곳뿐이고 그 줄이 무너진다

유일성 증명에서 두 목록을 어떻게 맞추는지 흐려진다

§1.7 확인 13 — 짝을 지정하는 것은 정리 1.4의 일반형 한 줄이다

지수를 세는 논증이 정당한지 의심스럽다

문제 9 앞의 도입 상자 — “그 지수”라는 말은 정리 1.5의 유일성이 있어야 성립한다

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) \(5\) (2) \(5\) (3) \(1\) (4) \(-2\) (5) 선형결합

※ 이 훈련의 관절은 (3)(4)다. \(5 = 35 - 2 \cdot 15\)를 정리 1.3의 꼴로 옮길 때 \(-2 \cdot 15\)의 부호를 계수 쪽으로 넘겨 \(15 \cdot (-2)\)로 적어야 한다. 뺄셈을 그대로 두면 “\(ax + by\) 꼴”이라는 형식 요구를 만족하지 못하고, 검산할 때 부호를 두 번 읽게 된다. 그리고 (5)는 정리 1.3의 둘째 문장 — \(\gcd\)는 선형결합 중 가장 작은 양수라는 것 — 을 그대로 인용한 자리다.

빈칸 사다리 — 훈련 2#

(1) 따름정리 1.3.1 (또는 정리 1.3) (2) \(1\) (3) \(c\) (4) \(a \mid bc\) (5) (D2), 곧 나눗셈의 선형결합 성질 (6) 특수한 경우

※ 이 훈련이 보여 주는 것은 예제 2.2에서 실제로 일하는 것이 “소수”가 아니라 “서로소”라는 사실이다. 예제 2.2의 증명에서 소수 가정은 \(\gcd(p,a) = 1\)을 얻는 데만 쓰였고, 그 뒤의 네 줄은 서로소라는 조건만 있으면 그대로 굴러간다. 그래서 이 명제가 정리 1.4보다 넓다. 다만 단순 대입은 아니다 — 이 훈련의 명제에 \(a = p\), \(b = a\)를 넣으면 얻는 것은 “\(\gcd(p,a) = 1\)이고 \(p \mid ab\)이면 \(p \mid b\)”이고, 정리 1.4는 가정에 서로소가 없고 결론이 \(\lor\)인 문장이라 아직 같은 문장이 아니다. 사이를 잇는 것은 경우 나눔 한 줄이다: \(p \mid a\)이면 결론이 곧바로 성립하고, \(p \nmid a\)이면 \(\gcd(p, a) = 1\)이므로 이 훈련의 명제를 걸 수 있다. 이 한 줄을 거쳐 정리 1.4가 따라 나오므로 정리 1.4는 이 명제의 따름정리이지 대입 사례가 아니며, 그 한 줄이 곧 이번 주가 강조한 소거법의 걸음 ①이다. (6)을 “일반화”라고 적었다면 방향이 반대다 — 넓은 쪽이 이 훈련의 명제다.

빈칸 사다리 — 훈련 3#

(1) 결론의 “서로소”가 말이다. 가정의 “\(d = \gcd(a,b)\)”도 말이므로, 둘 다 등식으로 바꿔야 한다. 먼저 \(\frac ad\)와 \(\frac bd\)가 정수임을 확보한다 — \(d\)가 \(a\)와 \(b\)의 공약수이므로(정의 1.1) \(a = d a'\), \(b = d b'\)인 정수 \(a', b'\)이 존재하고, \(a' = \frac ad\), \(b' = \frac bd\)이다. (2) 가정 쪽은 정리 1.3으로 번역한다: \(d = ax + by\)인 정수 \(x, y\)가 존재한다. 결론 쪽은 따름정리 1.3.1의 (\(\Leftarrow\)) 방향을 쓰기로 정한다 — 곧 \(a'X + b'Y = 1\)인 정수 \(X, Y\)를 하나 제시하면 된다. (3) \(d = ax + by\)에 \(a = da'\), \(b = db'\)을 대입하면 \(d = d a' x + d b' y = d(a'x + b'y)\)이다. \(d > 0\)이므로 양변을 \(d\)로 나누면 \(1 = a'x + b'y\)이다. (4) 대입은 근거 ③, \(a', b'\)이 정수라는 것은 정의 1.1의 공약수 조각과 근거 ②, 마지막 결론은 따름정리 1.3.1이다. (5) \(a'x + b'y = 1\)인 정수 \(x, y\)가 존재하므로 따름정리 1.3.1에 의해 \(\gcd(a', b') = 1\), 곧 \(\frac ad\)와 \(\frac bd\)는 서로소이다. \(\blacksquare\)

※ 검산으로 확인해 보자. \(a = 42\), \(b = 30\), \(d = 6\)이면 \(a' = 7\), \(b' = 5\)이고 예제 2.1이 준 \(6 = 42(-2) + 30(3)\)을 \(6\)으로 나누면 \(1 = 7(-2) + 5(3) = -14 + 15\) ✓. 곧 이 훈련의 증명은 예제 2.1의 등식을 \(d\)로 나누는 조작 하나다. 문제 11의 도입 상자가 인정하고 쓴 “일반해가 모든 해다”라는 사실도 이 결과에서 두 줄로 나온다.

문제 1#

접근. 암기 항목을 문장으로만 외우면 일부를 잊었을 때 복구할 길이 없다. 정의는 §1.3의 조각 표와 함께, 절차는 §1.4의 걸음 표와 함께 외운다. 조각과 걸음마다 붙은 “빼면 무엇이 무너지는가”가 재구성의 실마리다.

풀이. 다음 다섯 항목을 적으면 된다. ① 최대공약수: 둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해 \(a\)와 \(b\)를 모두 나누는 정수 중 가장 큰 것을 \(\gcd(a,b)\)로 쓴다. 서로소는 \(\gcd(a,b) = 1\)이다. ② 유클리드 호제법: ① 나눗셈 정리로 \(a = bq + r\), \(0 \le r < b\) ② 보조 명제 1.A에 의해 \(\gcd(a,b) = \gcd(b,r)\)이므로 쌍을 \((b,r)\)로 교체 ③ 나머지가 \(0\)이 될 때까지 반복 ④ 마지막으로 \(0\)이 아니었던 나머지가 답. ③ 베주 항등식: 둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해 \(\gcd(a,b) = ax + by\)인 정수 \(x, y\)가 존재한다. 곧 \(\gcd(a,b)\)는 \(a, b\)의 정수 선형결합 중 가장 작은 양수다. ④ 유클리드 보조정리: \(p\)가 소수이고 \(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)이다. ⑤ 산술의 기본정리: \(1\)보다 큰 모든 정수는 소수들의 곱으로 나타낼 수 있고(존재 — 강한 귀납), 그 표현은 순서를 무시하면 유일하다(유일 — 유클리드 보조정리 + 최소 반례).

복기. 다섯 항목이 사슬로 묶여 있다는 것까지 함께 적어야 재현이 완결된다 — ①이 ③의 대상이고, ③이 ④의 유일한 재료이며, ④가 ⑤의 유일성 부분을 지탱한다.

문제 2#

접근. 걸음 ①의 조건 \(0 \le r < b\)가 만족되도록 큰 수를 앞에 놓고 시작한다. (a)는 작은 수가 앞에 있으므로 정의 1.1의 대칭성으로 순서를 바꾼다. 나눗셈 줄을 하나도 빠뜨리지 않고 적는 것이 채점 항목 ①이다.

풀이. (a) \(\gcd(24, 36) = \gcd(36, 24)\)이다. \(36 = 1 \cdot 24 + 12\), \(24 = 2 \cdot 12 + 0\). 마지막으로 \(0\)이 아니었던 나머지는 \(12\)이므로 \(\gcd(24, 36) = 12\)이다. (b) \(17 = 3 \cdot 5 + 2\), \(5 = 2 \cdot 2 + 1\), \(2 = 2 \cdot 1 + 0\). 마지막으로 \(0\)이 아니었던 나머지는 \(1\)이므로 \(\gcd(17, 5) = 1\)이고, 정의 1.2에 의해 \(17\)과 \(5\)는 서로소다. (c) \(100 = 1 \cdot 64 + 36\), \(64 = 1 \cdot 36 + 28\), \(36 = 1 \cdot 28 + 8\), \(28 = 3 \cdot 8 + 4\), \(8 = 2 \cdot 4 + 0\). 따라서 \(\gcd(100, 64) = 4\)이다.

검산. (c)에서 \(100 = 4 \cdot 25\), \(64 = 4 \cdot 16\)이고 \(\gcd(25, 16) = 1\)이므로 \(4\)보다 큰 공약수는 없다 ✓. 나머지가 매 줄 줄어드는지도 함께 확인한다 — \(36 > 28 > 8 > 4 > 0\) ✓.

문제 3#

접근. 앞으로 가는 계산과 거꾸로 가는 계산을 분리해 적는다. 호제법 세 줄을 먼저 전부 적고, 그 세 줄만 재료로 삼아 역대입한다. 역대입에서 새 나눗셈을 하지 않는 것이 핵심이다.

풀이. 호제법: \(42 = 1 \cdot 30 + 12\), \(30 = 2 \cdot 12 + 6\), \(12 = 2 \cdot 6 + 0\). 따라서 \(\gcd(42, 30) = 6\)이다. 역대입: 둘째 줄에서 \(6 = 30 - 2 \cdot 12\)이고, 첫째 줄에서 \(12 = 42 - 1 \cdot 30\)이다. 대입하면

\[ 6 = 30 - 2(42 - 30) = 30 - 2 \cdot 42 + 2 \cdot 30 = 42 \cdot (-2) + 30 \cdot 3 \]

이다. 따라서 \(x = -2\), \(y = 3\)이다.

검산. \(42 \cdot (-2) + 30 \cdot 3 = -84 + 90 = 6\) ✓.

복기. 재현이 무너지는 자리는 대개 역대입의 첫 줄을 고르는 데 있다. 규칙은 간단하다 — 답이 나머지로 처음 등장한 줄을 골라 그 나머지를 좌변으로 옮긴다. 여기서는 \(6\)이 둘째 줄의 나머지이므로 둘째 줄이다.

문제 4#

접근. 세 훈련이 요구하는 것이 각각 다르다. 훈련 1은 계산 절차, 훈련 2는 근거 문장, 훈련 3은 답안 전체의 설계다. 백지에서는 훈련 3부터 어려우므로 §2 관찰의 다섯 걸음을 먼저 여백에 적어 두고 채운다.

풀이. 위의 “빈칸 사다리 — 훈련 1\(\cdot\)2\(\cdot\)3” 항목과 대조한다. 훈련 1은 (1) \(5\) (2) \(5\) (3) \(1\) (4) \(-2\) (5) 선형결합, 훈련 2는 (1) 따름정리 1.3.1 (2) \(1\) (3) \(c\) (4) \(a \mid bc\) (5) (D2) (6) 특수한 경우이며, 훈련 3은 다섯 걸음의 답안 전체다.

복기. 훈련 2의 (6)을 맞혔는지가 이번 주의 이해도를 가른다. 정리 1.4의 힘이 “소수”에서 오는 것이 아니라 “서로소”에서 온다는 것을 잡았다면, 문제 12와 18의 설계가 저절로 보인다.

문제 5#

접근. 아홉 줄의 순서를 먼저 여백에 적고 그 사이를 채운다. 채점에서 가장 자주 빠지는 줄은 소거법의 걸음 ③(“따라서 \(p \mid a\) 또는 \(p \mid b\)이다”)이다. 그 줄이 없으면 증명된 것은 조건문 \(p \nmid a \Rightarrow p \mid b\)뿐이다.

풀이. \(p\)를 소수, \(a, b\)를 정수라 하고 \(p \mid ab\)라 하자. 소거법을 쓴다. \(p \nmid a\)라 하자. \(\gcd(p, a)\)는 \(p\)의 양의 약수이고 \(p\)가 소수이므로 그것은 \(1\) 또는 \(p\)이다. \(\gcd(p, a) = p\)이면 \(\gcd\)가 공약수이므로 \(p \mid a\)가 되어 앞의 가정과 충돌한다. 따라서 \(\gcd(p, a) = 1\)이다. 따름정리 1.3.1에 의해 \(px + ay = 1\)인 정수 \(x, y\)가 존재한다. 양변에 \(b\)를 곱하면 \(pbx + aby = b\)이다. 첫 항은 \(pbx = p(bx)\)이므로 \(p \mid pbx\)이고, 가정 \(p \mid ab\)에서 \(ab = pm\)인 정수 \(m\)이 있으므로 \(aby = pmy = p(my)\), 곧 \(p \mid aby\)이다. (D2)에 의해 \(p \mid (pbx + aby) = b\)이다. 따라서 \(p \mid a\) 또는 \(p \mid b\)이다. \(\blacksquare\)

검산. \(p = 5\), \(a = 4\), \(b = 10\)으로 줄을 따라가 보자. \(ab = 40\)이고 \(5 \mid 40\) ✓. \(5 \nmid 4\)이므로 걸음 ①이 발동하고 \(\gcd(5,4) = 1\) ✓. \(5 \cdot 1 + 4 \cdot (-1) = 1\)이므로 \(x = 1\), \(y = -1\)이고, 양변에 \(10\)을 곱하면 \(50 - 40 = 10\) — 두 항 모두 \(5\)의 배수이므로 \(5 \mid 10\) ✓.

문제 6#

접근. 결론이 “\(\gcd(a,b) = 1\)”이므로 목표는 어떤 수가 \(1\)임을 보이는 것이다. 양의 정수가 \(1\)임을 보이는 표준 통로는 “그것이 \(1\)을 나눈다”이고, \(1\)의 양의 약수는 \(1\)뿐이다. 그러면 남은 일은 \(d = \gcd(a,b)\)가 \(1\)을 나눔을 보이는 것이고, 그 도구가 (D2)다.

풀이. \(ax + by = 1\)인 정수 \(x, y\)가 존재한다고 하자. \(d = \gcd(a, b)\)라 두면 정의 1.1에 의해 \(d \mid a\)이고 \(d \mid b\)이다. (D2)에 의해 \(d \mid (ax + by)\)이고, \(ax + by = 1\)이므로 \(d \mid 1\)이다. \(1 \ne 0\)이므로 (D3)에 의해 \(|d| \le 1\)이고, \(d\)는 \(a\)와 \(b\)의 공약수 중 최대인데 \(1\)이 언제나 공약수이므로 \(d \ge 1\)이다. 따라서 \(d = 1\), 곧 \(a\)와 \(b\)는 서로소이다. \(\blacksquare\)

복기. “\(d \mid 1\)이므로 \(d = 1\)”을 한 줄로 넘기지 않고 (D3)과 \(d \ge 1\)을 각각 대는 것이 이번 주의 채점 기준 ②다. \(d \mid 1\)만으로는 \(d = -1\)도 배제되지 않으며, \(d \ge 1\)을 주는 것은 \(\gcd\)가 최대라는 정의 1.1의 조각이다.

문제 7#

접근. (a)는 예제 2.1과 같은 크기이므로 절차 확인용이다. (b)는 몫이 거의 전부 \(1\)이라 나눗셈 줄이 여덟 개로 늘어난다. 역대입에서 수를 도로 계산하면 길을 잃으므로, 매 단계에서 “지금 남아 있는 두 수”의 계수만 적고 넘어간다. 한 줄 올라갈 때마다 값을 검산하면 부호 오류를 초기에 잡는다.

풀이 (a). 호제법: \(14 = 1 \cdot 9 + 5\), \(9 = 1 \cdot 5 + 4\), \(5 = 1 \cdot 4 + 1\), \(4 = 4 \cdot 1 + 0\). 따라서 \(\gcd(14, 9) = 1\)이다. 역대입: \(1 = 5 - 1 \cdot 4\). 여기에 \(4 = 9 - 1 \cdot 5\)를 넣으면 \(1 = 5 - (9 - 5) = 2 \cdot 5 - 9\). 여기에 \(5 = 14 - 9\)를 넣으면 \(1 = 2(14 - 9) - 9 = 2 \cdot 14 - 3 \cdot 9\)이다. 곧 \(1 = 14 \cdot 2 + 9 \cdot (-3)\)이고 \(x = 2\), \(y = -3\)이다. 검산: \(28 - 27 = 1\) ✓.

풀이 (b). 호제법: \(55 = 1 \cdot 34 + 21\), \(34 = 1 \cdot 21 + 13\), \(21 = 1 \cdot 13 + 8\), \(13 = 1 \cdot 8 + 5\), \(8 = 1 \cdot 5 + 3\), \(5 = 1 \cdot 3 + 2\), \(3 = 1 \cdot 2 + 1\), \(2 = 2 \cdot 1 + 0\). 따라서 \(\gcd(55, 34) = 1\)이다. 역대입을 아래에서 위로 한 줄씩 올린다.

\[ 1 = 3 - 1 \cdot 2 = 3 - (5 - 3) = 2 \cdot 3 - 5 \]
\[ = 2(8 - 5) - 5 = 2 \cdot 8 - 3 \cdot 5 = 2 \cdot 8 - 3(13 - 8) = 5 \cdot 8 - 3 \cdot 13 \]
\[ = 5(21 - 13) - 3 \cdot 13 = 5 \cdot 21 - 8 \cdot 13 = 5 \cdot 21 - 8(34 - 21) = 13 \cdot 21 - 8 \cdot 34 \]
\[ = 13(55 - 34) - 8 \cdot 34 = 13 \cdot 55 - 21 \cdot 34 \]

곧 \(1 = 55 \cdot 13 + 34 \cdot (-21)\)이고 \(x = 13\), \(y = -21\)이다. 검산: \(715 - 714 = 1\) ✓.

복기. (b)의 계수 \(13\)과 \(21\)이 다시 피보나치 수라는 것이 우연이 아니다. 몫이 전부 \(1\)인 경우가 호제법이 가장 오래 걸리는 최악의 입력이고, 그때 역대입의 계수는 피보나치 수열을 거꾸로 밟는다. 계산이 길어질수록 매 줄 검산하는 습관이 값을 한다.

문제 8#

접근. C7주차 예제 2.2(\(\sqrt p\)가 무리수)의 4단 서식을 그대로 쓴다. 달라지는 것은 근거 하나뿐이다 — “\(3 \mid a^2\)이므로 \(3 \mid a\)”라는 줄이 그때는 베주 항등식이 아직 기성품이던 상태의 인용이었고, 지금은 이번 주가 증명을 끝낸 정리 1.4의 인용이다. 같은 부품을 1권 21주차 문제 7은 1권 19주차 예제 2.2에서, C8주차 문제 14는 유클리드 보조정리(\(p = 3\))에서 각각 빌려 왔다. 인용할 때 \(3\)이 소수임을 밝히는 것이 채점 항목 ②다.

풀이. 모순을 위해 \(\sqrt3\)이 유리수라고 가정하자. 그러면 \(\sqrt3 = \dfrac ab\)인 양의 정수 \(a, b\)가 존재하고, 기약분수로 잡을 수 있으므로 \(\gcd(a,b) = 1\)이라 하자. 양변을 제곱하고 분모를 없애면

\[ 3b^2 = a^2 \]

이다. 따라서 \(3 \mid a^2\), 곧 \(3 \mid a \cdot a\)이다. \(3\)은 소수이므로 정리 1.4에 의해 \(3 \mid a\) 또는 \(3 \mid a\), 곧 \(3 \mid a\)이다. 그러면 \(a = 3c\)인 정수 \(c\)가 존재하고, 대입하면 \(3b^2 = 9c^2\)이므로 양변을 \(3\)으로 나누어 \(b^2 = 3c^2\)이다. 따라서 \(3 \mid b^2\)이고, 같은 이유로 정리 1.4에 의해 \(3 \mid b\)이다. 곧 \(3\)은 \(a\)와 \(b\)의 공약수이므로 \(\gcd(a,b) \ge 3\)인데, 이는 \(\gcd(a,b) = 1\)과 모순이다. 따라서 \(\sqrt3\)은 무리수이다. \(\blacksquare\)

복기. 이 증명에서 소수 \(3\)이 쓰이는 곳은 정리 1.4를 인용하는 두 줄뿐이다. 그래서 \(3\)을 임의의 소수 \(p\)로 바꿔도 증명이 그대로 통하고, \(4\)로 바꾸면 곧바로 무너진다 — \(4 \mid 2^2\)이지만 \(4 \nmid 2\)이기 때문이며, 실제로 \(\sqrt4 = 2\)는 유리수다. 가정이 어디서 소비되는지 아는 것이 명제의 경계를 아는 것이다.

문제 9#

접근. 문제 8의 방식(\(3 \mid a\)를 꺼내 대입)도 통하지만, \(12\)가 합성수라 정리 1.4를 곧바로 걸 수 없다. 대신 문제 9 앞의 도입 상자가 준 도구를 쓴다 — 등식의 양변에서 소수 \(3\)의 지수만 세어 비교한다. 유일성이 있어야 “그 지수”라는 말이 성립한다는 점을 답안에 밝힌다.

풀이. 모순을 위해 \(\sqrt{12}\)가 유리수라고 가정하자. 그러면 \(\sqrt{12} = \dfrac ab\)인 양의 정수 \(a, b\)가 존재하고, 양변을 제곱해 분모를 없애면

\[ 12 b^2 = a^2 \]

이다. 정리 1.5에 의해 \(a\)와 \(b\)는 소인수분해가 유일하게 정해지므로, 각각에서 소수 \(3\)의 지수를 \(\alpha\), \(\beta\)라 하자 (지수가 \(0\)인 경우도 허용한다). 곱셈에서 지수는 더해지므로 우변 \(a^2\)에서 \(3\)의 지수는 \(2\alpha\)로 짝수다. 좌변은 \(12 = 2^2 \cdot 3\)이므로 \(12b^2\)에서 \(3\)의 지수는 \(1 + 2\beta\)로 홀수다. 같은 수의 소인수분해가 유일하므로(정리 1.5) 두 지수는 같아야 하는데, \(2\alpha = 1 + 2\beta\)는 짝수와 홀수가 같다는 뜻이라 불가능하다. 따라서 \(\sqrt{12}\)는 무리수이다. \(\blacksquare\)

검산. 논증이 무엇을 걸러 내는지 확인해 보자. \(\sqrt{36}\)에 같은 논법을 걸면 \(36 = 2^2 \cdot 3^2\)이라 좌변의 \(3\)의 지수가 \(2 + 2\beta\)로 짝수가 되어 모순이 나오지 않는다 — 실제로 \(\sqrt{36} = 6\)은 유리수다 ✓. 곧 이 논법은 “완전제곱이 아닌 정수”를 정확히 걸러 낸다.

문제 10#

접근. 제시된 증명의 평가는 두 물음으로 나눈다. ① 명제 자체가 참인가. ② 인용한 정리의 가정이 충족되는가. 여기서는 둘 다 실패하므로 두 가지를 모두 지적해야 한다. 명제가 거짓이면 반례를 제시하는 것이 평가의 완결이다.

풀이. 이 증명은 틀렸고, 명제 자체도 거짓이다. ① 명제의 반례: \(a = 2\), \(b = 3\)이라 하면 \(ab = 6\)이고 \(6 \mid 6\)이다. 그러나 \(6 \nmid 2\)이고 \(6 \nmid 3\)이므로 결론이 성립하지 않는다. 따라서 명제는 거짓이다. ② 인용의 오류: 정리 1.4는 나누는 수가 소수일 때의 정리다. \(6 = 2 \cdot 3\)은 합성수이므로 인용 자격이 없다. 정리 1.4의 증명에서 소수 가정이 소비되는 줄은 “\(p \nmid a\)이면 \(\gcd(p, a) = 1\)”인데, \(6\)에서는 이 줄이 무너진다 — \(6 \nmid 2\)이지만 \(\gcd(6, 2) = 2 \ne 1\)이다.

복기. “정리의 이름을 대면 증명이 끝난다”는 답안은 그 정리의 가정이 충족되는지를 검사하지 않았을 때 무너진다. 정리를 인용하는 줄은 언제나 두 부분이다 — 가정 충족의 확인과 결론의 회수. 1권 2주차 문제 15와 C7주차 예제 2.1의 명제 \(C\)가 같은 경계를 다뤘고, 확인 14의 (나)가 같은 오류의 짧은 판이다.

문제 11#

접근. 새로 계산할 것이 없다. 문제 7(a)가 이미 \(\gcd(14,9) = 1\)과 그 베주 계수를 주었고, 구하려는 방정식의 우변이 정확히 그 \(\gcd\)이므로 계수를 그대로 옮겨 적으면 된다. 답안에는 검산과 일반해를 함께 붙인다.

풀이. 문제 7(a)에서 \(1 = 14 \cdot 2 + 9 \cdot (-3)\)을 얻었다. 따라서 \((x, y) = (2, -3)\)이 \(14x + 9y = 1\)의 정수 해다. 검산: \(14 \cdot 2 + 9 \cdot (-3) = 28 - 27 = 1\) ✓. 일반해는 문제 11의 도입 상자가 준 꼴에 \(d = \gcd(14,9) = 1\)을 넣어

\[ x = 2 + 9t, \qquad y = -3 - 14t \qquad (t \in \mathbb{Z}) \]

이다. 실제로 대입하면 \(14(2 + 9t) + 9(-3 - 14t) = 28 + 126t - 27 - 126t = 1\) ✓.

복기. 계수 \(9\)와 \(-14\)의 자리가 바뀌어 있는 것이 이 일반해의 요점이다. \(x\)에는 \(b\)가, \(y\)에는 \(-a\)가 붙어야 두 항의 변화분 \(14 \cdot 9t\)와 \(-9 \cdot 14t\)가 상쇄된다. 부호나 자리를 잘못 적으면 대입 검산에서 곧바로 드러난다.

문제 12#

접근. 결론이 “서로소”이므로 따름정리 1.3.1의 (\(\Leftarrow\)) 방향을 쓴다 — 곧 \(1\)을 만드는 계수 한 쌍을 제시하면 끝난다. 두 수의 차가 \(1\)이라는 사실이 그 계수를 곧바로 준다.

풀이. \(n\)을 정수라 하자. 그러면

\[ (n+1) \cdot 1 + n \cdot (-1) = n + 1 - n = 1 \]

이다. 곧 \(1\)은 \(n+1\)과 \(n\)의 정수 선형결합이므로, 따름정리 1.3.1(문제 6에서 증명한 방향)에 의해 \(\gcd(n, n+1) = 1\)이다. 따라서 연속한 두 정수는 서로소이다. \(\blacksquare\)

검산. \(n = 8\)이면 \(9 \cdot 1 + 8 \cdot (-1) = 1\)이고 \(\gcd(8, 9) = 1\) ✓. \(n = -1\)처럼 음수나 \(n = 0\)(\(\gcd(0,1) = 1\))에서도 성립한다 — 증명의 어느 줄도 \(n\)이 양수임을 쓰지 않았다.

복기. 호제법으로 풀어도 한 줄이다: \((n+1) = 1 \cdot n + 1\), \(n = n \cdot 1 + 0\)이므로 \(\gcd = 1\). 두 풀이가 같은 계산을 다른 방향에서 적은 것이며, 이번 주의 계산과 증명이 같은 등식 위에 서 있음을 보여 준다.

문제 13#

접근. 곱의 인수 개수 \(n\)에 대한 귀납이다. 귀납 단계의 요령은 곱을 두 덩어리로 묶는 것 — \(a_1 \cdots a_{n+1} = (a_1 \cdots a_n) \cdot a_{n+1}\)로 보면 인수가 둘뿐인 곱이 되어 예제 2.2(정리 1.4)를 그대로 걸 수 있다. 그러면 두 갈래가 나오고, 앞 갈래에 귀납 가정을 쓴다.

풀이. \(p\)를 소수라 하고, \(n\)에 대한 귀납으로 증명한다. 기저 (\(n = 1\)). \(p \mid a_1\)이면 \(i = 1\)에 대해 \(p \mid a_i\)이므로 성립한다. 귀납 단계. \(n \ge 1\)에 대해 명제가 성립한다고 가정하고, \(p \mid a_1 a_2 \cdots a_{n+1}\) 이라 하자. 곱을 \((a_1 a_2 \cdots a_n) \cdot a_{n+1}\)로 묶으면 인수가 두 개인 곱이고, \(p\)가 소수이므로 정리 1.4에 의해

\[ p \mid (a_1 a_2 \cdots a_n) \quad \text{또는} \quad p \mid a_{n+1} \]

이다. 앞쪽이면 귀납 가정에 의해 어떤 \(i \le n\)에 대해 \(p \mid a_i\)이고, 뒤쪽이면 \(i = n+1\)이 그런 첨자다. 어느 경우든 어떤 \(i\)에 대해 \(p \mid a_i\)이다. 따라서 모든 \(n \ge 1\)에 대해 명제가 성립한다. \(\blacksquare\)

복기. \(n = 2\)의 경우가 곧 정리 1.4이므로, 이 문제는 “부품 하나를 반복 적용해 일반형을 만드는” 전형이다. 예제 2.3이 인용하는 것이 바로 이 일반형이며, 인수의 개수 \(m\)이 얼마든 정해져 있지 않으므로 일반형 없이는 예제 2.3의 그 줄을 쓸 수 없다.

문제 14#

접근. 공식을 유도하려면 두 가지를 각각 밝혀야 한다. ① \(n\)의 양의 약수가 반드시 \(p_1^{f_1} \cdots p_k^{f_k}\) (\(0 \le f_i \le e_i\)) 꼴이다. ② 서로 다른 지수 조합은 서로 다른 수를 준다. 둘 다 근거는 정리 1.5의 유일성이고, 그다음은 곱의 법칙으로 세는 일이다.

풀이. \(n \ge 2\)의 소인수분해를 \(n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\) (서로 다른 소수 \(p_i\), 양의 정수 \(e_i\))라 하자. ① 약수의 꼴. \(d\)를 \(n\)의 양의 약수라 하면 \(n = d \cdot d'\)인 양의 정수 \(d'\)이 존재한다. \(d\)와 \(d'\)의 소인수분해를 곱하면 \(n\)의 한 소인수분해가 되고, 정리 1.5에 의해 \(n\)의 소인수분해는 유일하므로 \(d\)에 등장하는 소수는 \(p_1, \ldots, p_k\) 중 하나뿐이며 각 \(p_i\)의 지수 \(f_i\)는 \(e_i\)를 넘을 수 없다. 곧 \(d = p_1^{f_1} \cdots p_k^{f_k}\) (\(0 \le f_i \le e_i\))이다. ② 거꾸로도 성립하고 중복이 없다. 그런 꼴의 수는 모두 \(n\)을 나눈다 — 남은 인수가 \(p_1^{e_1 - f_1} \cdots p_k^{e_k - f_k}\)이기 때문이다. 그리고 지수 조합이 다르면 두 수의 소인수분해가 다르므로 정리 1.5에 의해 두 수도 다르다. ③ 세기. 각 \(f_i\)가 \(0, 1, \ldots, e_i\)의 \(e_i + 1\)가지이고 선택이 서로 독립이므로, 약수의 개수는 \((e_1 + 1)(e_2 + 1) \cdots (e_k + 1)\)이다. \(\blacksquare\)

검산. \(12 = 2^2 \cdot 3^1\)이므로 공식은 \((2+1)(1+1) = 6\)을 준다. 실제 약수는 \(f_1 \in \{0,1,2\}\)와 \(f_2 \in \{0,1\}\)의 조합으로 \(1, 2, 4, 3, 6, 12\)의 여섯 개다 ✓.

복기. ②의 “중복이 없다”가 빠진 답안이 흔하다. 그 줄이 없으면 개수를 셀 때 같은 수를 두 번 세지 않았다는 보장이 없고, 개수를 세는 논증은 언제나 이 보장을 요구한다. 정리 1.5의 유일성이 여기서 두 번 일한다 — 목록을 만드는 데 한 번, 중복을 막는 데 한 번이다.

문제 15#

접근. 앞부분은 예제 2.3의 재현이므로 최소 반례법의 네 걸음을 여백에 적고 채운다. 뒷부분은 “보조정리가 없으면 유일성이 무너진다”를 보이는 일이므로, 정리 1.4가 거짓인 수 체계를 하나 제시하고 그 안에서 두 분해를 실제로 만들어 보인다.

풀이 (앞부분). 모순을 위해, 소인수분해가 유일하지 않은 \(2\) 이상의 정수가 존재한다고 가정하자. 그런 정수들의 집합은 공집합이 아닌 양의 정수의 부분집합이므로 최소원리(1권 33주차)에 의해 최소원소를 가진다. 그것을 \(n\)이라 하고, \(n\)의 서로 다른 두 소인수분해를

\[ n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m \]

이라 하자 (모든 \(p_i\)와 \(q_j\)는 소수). \(p_1\)이 좌변을 나누므로 \(p_1 \mid n\)이고, 따라서 \(p_1 \mid q_1 q_2 \cdots q_m\)이다. 정리 1.4의 일반형(문제 13)에 의해 어떤 \(j\)에 대해 \(p_1 \mid q_j\)이다. \(q_j\)는 소수이므로 그 양의 약수는 \(1\)과 \(q_j\)뿐이고 \(p_1 > 1\)이므로 \(p_1 = q_j\)이다. 유일성의 진술이 순서를 무시하므로 오른쪽 목록의 순서를 바꿔 \(j = 1\)이라 해도 무방하다. 양변을 \(p_1 = q_1\)로 나누면

\[ \frac{n}{p_1} = p_2 \cdots p_k = q_2 \cdots q_m \]

이다. \(p_1 \ge 2\)이므로 \(\frac{n}{p_1} < n\)이고, \(n\)이 최소 반례였으므로 \(\frac{n}{p_1}\)의 소인수분해는 유일하다. 따라서 \(p_2, \ldots, p_k\)와 \(q_2, \ldots, q_m\)은 순서를 무시하면 같은 목록이고 \(k - 1 = m - 1\)이다. 여기에 \(p_1 = q_1\)을 되돌려 붙이면 \(n\)의 두 분해도 순서를 무시하면 같고 \(k = m\)인데, 이는 두 분해가 서로 다르다고 한 가정과 모순이다. (\(\frac{n}{p_1} = 1\)인 경우도 규칙 안에 있다 — 그때는 \(k = m = 1\)이고 \(n = p_1 = q_1\)이라 두 분해가 처음부터 같다. 소수 하나도 없는 곱을 \(1\)로 읽으면 위 논증이 그대로 통한다.) 따라서 유일하지 않은 정수는 존재하지 않고, \(1\)보다 큰 모든 정수의 소인수분해는 순서를 무시하면 유일하다. \(\blacksquare\)

풀이 (뒷부분). \(H = \{4k + 1 : k \ge 0\} = \{1, 5, 9, 13, 17, 21, 25, \ldots\}\)라 하자. ① \(H\)는 곱셈에 닫혀 있다. \((4a+1)(4b+1) = 16ab + 4a + 4b + 1 = 4(4ab + a + b) + 1\)이고 \(4ab + a + b\)는 정수이므로 곱도 \(4k+1\) 꼴이다. 따라서 \(H\) 안에서 “쪼갠다”는 말이 뜻을 가진다 — \(H\)의 원소를 \(1\)보다 큰 \(H\)의 원소 두 개의 곱으로 적는 것이다. ② \(9, 21, 49\)는 \(H\) 안에서 더 쪼개지지 않는다. \(9\)를 \(1\)보다 큰 두 정수의 곱으로 적는 방법은 \(3 \times 3\)뿐인데 \(3 = 4 \cdot 0 + 3\)이라 \(H\)에 들지 않는다. \(21\)은 \(3 \times 7\)뿐이고 \(3, 7\) 모두 \(H\)에 들지 않는다. \(49\)는 \(7 \times 7\)뿐이고 마찬가지다. 곧 셋 다 \(H\)의 “소수”다. ③ 유일성이 무너진다. \(441 = 21 \times 21 = 9 \times 49\)이고 (검산: \(21^2 = 441\), \(9 \times 49 = 441\) ✓), \(441 = 4 \cdot 110 + 1\)이므로 \(441 \in H\)이다. 두 분해는 \(H\)의 소수들로 이루어져 있고 서로 다르므로, \(H\)에서는 소인수분해가 유일하지 않다. ④ 원인은 정리 1.4의 실패다. \(H\) 안에서 \(21 \mid 441 = 9 \times 49\)이지만 \(21 \nmid 9\)이고 \(21 \nmid 49\)이다. 예제 2.3에서 “\(p_1\)이 어떤 \(q_j\)를 나눈다”고 적은 줄이 \(H\)에서는 나오지 않으므로, 지울 짝을 찾을 수 없고 논증이 멈춘다. \(\blacksquare\)

복기. 유일성은 곱셈이 있는 모든 체계가 갖는 성질이 아니라 정수의 성질이며, 그것을 떠받치는 것이 정리 1.4이고 정리 1.4를 떠받치는 것이 베주 항등식이다. \(H\)에는 나눗셈 정리가 없어 호제법이 굴러가지 않고, 따라서 베주도 없다 — 사슬의 맨 앞이 없으면 맨 뒤도 없다.

문제 16#

접근. 1권 33주차의 최소원리 4단 서식대로 순서를 먼저 적는다: ① 최소원리를 걸 집합을 지정 ② 그 집합이 공집합이 아님을 확인 ③ 최소원소를 잡음 ④ 모순 또는 목표 확인. 이 문제에서 ④는 모순이 아니라 “그 최소원소가 실제로 \(\gcd\)다”의 확인 두 단계다. 빠뜨리기 쉬운 줄은 ②와, 나머지 \(r\)을 선형결합으로 다시 쓰는 줄이다.

풀이. 둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해

\[ S = \{ax + by : x, y \in \mathbb{Z},\ ax + by > 0\} \]

이라 하자. \(x = a\), \(y = b\)를 넣으면 \(a^2 + b^2\)이고, \(a\)와 \(b\) 중 적어도 하나가 \(0\)이 아니므로 \(a^2 + b^2 > 0\)이다. 따라서 \(a^2 + b^2 \in S\)이고 \(S \ne \varnothing\)이다. \(S\)는 공집합이 아닌 양의 정수의 부분집합이므로 최소원리(1권 33주차)에 의해 최소원소 \(d\)를 가지며, \(d \in S\)이므로 \(d = ax_0 + by_0\)인 정수 \(x_0, y_0\)을 잡는다. \(d \mid a\). 나눗셈 정리(1권 33주차 예제 2.2)에 의해 \(a = dq + r\), \(0 \le r < d\)인 정수 \(q, r\)이 존재한다. 그러면

\[ r = a - dq = a - (ax_0 + by_0)q = a(1 - x_0 q) + b(-y_0 q) \]

이므로 \(r\)은 \(a\)와 \(b\)의 정수 선형결합이다. 만약 \(r > 0\)이면 \(r \in S\)인데 \(r < d\)라 \(d\)의 최소성과 모순이므로 \(r = 0\)이고, 곧 \(a = dq\), 즉 \(d \mid a\)이다. \(b\)에 대해 같은 계산을 하면 \(d \mid b\)이다. \(d\)가 최대. \(c\)를 \(a, b\)의 임의의 공약수라 하자. (D2)에 의해 \(c \mid (ax_0 + by_0) = d\)이고, \(d > 0\)이므로 (D3)에 의해 \(|c| \le d\), 따라서 \(c \le d\)이다. 그러므로 \(d\)는 \(a\)와 \(b\)의 공약수 중 가장 큰 것이고, 정의 1.1에 의해 \(d = \gcd(a,b) = ax_0 + by_0\)이다. \(\blacksquare\)

복기. 이 증명은 계수 \(x_0, y_0\)의 값을 하나도 주지 않는다 — 최소원소가 존재한다는 사실만 쓰기 때문이다. 값이 필요하면 예제 2.1의 역대입을 쓴다. 존재 증명과 구성 절차가 따로 있는 전형이며, 존재는 이 증명이, 구성은 호제법이 맡는다.

문제 17#

접근. \(N = p_1 \cdots p_k + 1\)이 소수인지 아닌지는 따지지 않는다. 필요한 것은 “\(N \ge 2\)이므로 소인수를 적어도 하나 가진다”는 정리 1.5의 존재 부분뿐이고, 그 소인수가 유한 목록 안에 있어야 한다는 가정에서 모순이 나온다. 모순을 만드는 도구는 (D2)다.

풀이. 모순을 위해 소수가 유한하다고 가정하고, 소수 전체를 \(p_1, p_2, \ldots, p_k\)라 하자. \(N = p_1 p_2 \cdots p_k + 1\)이라 두면 각 \(p_i \ge 2\)이므로 \(N \ge 3 > 1\)이다. 정리 1.5의 존재 부분에 의해 \(N\)은 소수이거나 소수들의 곱이므로, 어느 경우든 \(N\)을 나누는 소수 \(p\)가 존재한다. 가정에 의해 소수는 목록에 있는 것뿐이므로 \(p = p_i\)인 \(i\)가 있다. 그러면 \(p_i \mid N\)이고, \(p_i\)는 곱 \(p_1 \cdots p_k\)의 인수이므로 \(p_i \mid p_1 \cdots p_k\)이다. (D2)에 의해 \(p_i \mid (N \cdot 1 + p_1 \cdots p_k \cdot (-1))\)이고, 그 값은 \(N - p_1 \cdots p_k = 1\)이므로 \(p_i \mid 1\)이다. 그런데 \(p_i \ge 2\)이므로 (D3)에 의해 \(p_i \le 1\)이어야 해서 모순이다. 따라서 소수는 무한히 많다. \(\blacksquare\)

복기. S11주차 문제 15의 증명과 뼈대는 같지만 인용하는 근거가 다르다. 그쪽은 “\(1\)보다 큰 정수는 소수 약수를 가진다”를 따로 세워 썼고, 여기서는 그것이 정리 1.5의 존재 부분이라는 이름을 얻는다. \(N\)이 소수라고 주장하지 않는 것이 이 증명의 요점이다 — 실제로 \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509\)로 합성수다.

문제 18#

접근. 지적할 것과 대안으로 제시할 것이 따로 있다. 지적은 1권 1주차 이래의 기준 하나면 충분하다 — 특정 값 하나의 확인은 \(\forall\) 명제의 증명이 아니다. 대안은 문제 9 앞의 도입 상자가 준 도구로 만든다. 각 소수의 지수를 \(\gcd\)와 \(\operatorname{lcm}\)에서 각각 어떻게 읽는지 정한 뒤 \(\min + \max = \) 두 지수의 합을 쓴다. \(\operatorname{lcm}\)의 정의와 존재는 이 문제 앞의 도입 상자에 있다 — 인용하기 전에 그 낱말이 어디서 정의되었는지 밝히는 것이 채점 항목 ②다.

풀이 (평가). 제시된 증명은 불완전하다. 명제는 모든 양의 정수 \(a, b\)에 대한 주장인데 답안이 확인한 것은 \(a = 4\), \(b = 6\) 한 쌍뿐이다. 확인한 쌍에 대해서는 계산이 옳지만, 확인하지 않은 무한히 많은 쌍은 이 계산이 보장하지 않는다. (명제 자체는 참이므로 반례는 없다 — 무너진 것은 결론이 아니라 근거다.)

풀이 (올바른 증명). \(a, b\)를 양의 정수라 하자. \(a\)와 \(b\)에 등장하는 소수를 모두 모아 \(p_1, \ldots, p_k\)라 하고, 지수 \(0\)을 허용해

\[ a = p_1^{s_1} \cdots p_k^{s_k}, \qquad b = p_1^{t_1} \cdots p_k^{t_k} \]

로 적는다 (정리 1.5의 유일성으로 각 지수가 하나로 정해진다). 문제 14의 ①에 의해 \(a\)의 약수는 지수가 \(s_i\) 이하인 것들이고 \(b\)의 약수는 지수가 \(t_i\) 이하인 것들이므로, 공약수는 각 지수가 \(\min(s_i, t_i)\) 이하인 것들이고 그중 최대는

\[ \gcd(a,b) = p_1^{\min(s_1,t_1)} \cdots p_k^{\min(s_k,t_k)} \]

이다. 공배수 쪽도 같은 방식이되 한 걸음이 더 붙는다. \(c\)가 \(a\)와 \(b\)의 양의 공배수이면 \(a \mid c\)와 \(b \mid c\)에 문제 14의 ①을 각각 걸어, \(c\)에서 각 \(p_i\)의 지수는 \(s_i\) 이상이면서 \(t_i\) 이상, 곧 \(\max(s_i, t_i)\) 이상이어야 한다. \(c\)는 \(p_1, \ldots, p_k\) 밖의 소수를 더 가질 수도 있지만 그런 인수는 값을 키우기만 하므로 최소인 후보에는 들어가지 않는다. 곧 후보 가운데 가장 작은 것은 지수를 정확히 \(\max(s_i, t_i)\)로 맞추고 다른 소수를 붙이지 않은 수이고, 그 수는 실제로 \(a\)와 \(b\)의 공배수이므로

\[ \operatorname{lcm}(a,b) = p_1^{\max(s_1,t_1)} \cdots p_k^{\max(s_k,t_k)} \]

이다. 두 수를 곱하면 각 \(p_i\)의 지수는 \(\min(s_i,t_i) + \max(s_i,t_i)\)인데, 두 수 중 작은 것과 큰 것을 더하면 두 수의 합이므로 이 값은 \(s_i + t_i\)이다. 따라서

\[ \gcd(a,b) \cdot \operatorname{lcm}(a,b) = p_1^{s_1 + t_1} \cdots p_k^{s_k + t_k} = ab \]

이다. \(\blacksquare\)

검산. \(a = 4 = 2^2\), \(b = 6 = 2 \cdot 3\)이면 지수는 \(2\)의 자리에서 \((2, 1)\), \(3\)의 자리에서 \((0, 1)\)이다. \(\gcd = 2^1 3^0 = 2\), \(\operatorname{lcm} = 2^2 3^1 = 12\), 곱은 \(24 = 4 \cdot 6\) ✓. 원 답안이 확인한 그 한 쌍이 여기서는 검산으로 제자리를 찾는다.

복기. \(\min(s,t) + \max(s,t) = s + t\)라는 한 줄이 이 정리의 전부다. 특정 값 확인이 증명이 되지 못하는 이유는 이 한 줄을 드러내지 못하기 때문이며, 드러난 순간 모든 \(a, b\)가 한 번에 처리된다.

문제 19#

접근. 존재와 유일은 별개의 의무다(C7주차 §1.7). 존재는 해를 하나 제시하면 되고, 유일은 두 해의 차가 \(15\)의 배수임을 보이면 된다. 존재를 조립식으로 만드는 설계가 일반 법에서도 통하므로 그쪽을 적는다 — \(3u + 5v = 1\)을 먼저 구해 두고, 각 조건을 하나씩만 건드리는 부품을 만든다.

풀이 (존재). \(\gcd(3, 5) = 1\)이므로 따름정리 1.3.1에 의해 \(3u + 5v = 1\)인 정수 \(u, v\)가 존재하고, \(u = 2\), \(v = -1\)이 그 하나다 (\(6 - 5 = 1\) ✓). \(5v = -5\)는 \(3\)으로 나눈 나머지가 \(1\)이고 \(5\)의 배수이며, \(3u = 6\)은 \(5\)로 나눈 나머지가 \(1\)이고 \(3\)의 배수다. 그러므로

\[ x = 2 \cdot (5v) + 3 \cdot (3u) = 2 \cdot (-5) + 3 \cdot 6 = -10 + 18 = 8 \]

로 두면, 법 \(3\)에서는 둘째 항이 사라지고 \(x \equiv 2 \cdot 1 = 2 \pmod 3\)이며, 법 \(5\)에서는 첫째 항이 사라지고 \(x \equiv 3 \cdot 1 = 3 \pmod 5\)이다. 검산: \(8 = 2 \cdot 3 + 2\)이므로 \(8 \equiv 2 \pmod 3\) ✓, \(8 = 1 \cdot 5 + 3\)이므로 \(8 \equiv 3 \pmod 5\) ✓.

풀이 (유일). 먼저 문제 19의 도입 상자가 미뤄 둔 사실을 증명한다. \(\gcd(m, n) = 1\)이고 \(m \mid k\)이며 \(n \mid k\)라 하자. 따름정리 1.3.1에 의해 \(mu + nv = 1\)인 정수 \(u, v\)가 있고, \(k = m s\), \(k = n t\)인 정수 \(s, t\)가 있다. 양변에 \(k\)를 곱하면

\[ k = kmu + knv = (nt)mu + (ms)nv = mn(tu + sv) \]

이고 \(tu + sv\)는 정수이므로 \(mn \mid k\)이다. 이제 \(x\)와 \(x'\)이 모두 두 합동식을 만족한다고 하자. 그러면 \(3 \mid (x - x')\)이고 \(5 \mid (x - x')\)이며 \(\gcd(3,5) = 1\)이므로, 위 사실에 의해 \(15 \mid (x - x')\), 곧 \(x \equiv x' \pmod{15}\)이다. 따라서 해는 법 \(15\)에서 유일하고, 해 전체는 \(x = 8 + 15t\) (\(t \in \mathbb{Z}\))이다. \(\blacksquare\)

복기. C6주차 문제 15가 \(m = 2\), \(n = 3\)의 사례로 다루고 일반형을 미뤄 둔 것이 위의 세 줄짜리 증명이다. 서로소 조건이 없으면 거짓이라는 것도 함께 기억해 둔다 — \(m = n = 2\), \(k = 2\)에서 \(2 \mid 2\)이지만 \(4 \nmid 2\)이다. 조립식 설계는 법이 셋 이상이어도 그대로 확장되며, 그것이 중국인 나머지 정리의 일반형이다.

문제 20#

접근. (a)의 축은 확인 13이다 — 유일성 증명이 보조정리를 부르는 자리는 “지울 짝을 찾는 일” 한 곳이고, 그 자리가 비면 무엇이 일어나는지가 문제 15의 힐베르트 수다. (b)는 §1.8의 “지워지는 표시” 표에 적힌 네 곳을 자기 말로 옮긴다.

풀이 (a). (예시 답안) 베주 항등식은 최소원리로 \(\gcd(a,b) = ax + by\)인 정수 \(x, y\)의 존재를 세우고, 그 등식이 예제 2.2에서 “\(p \nmid a\)이면 \(px + ay = 1\)”로 쓰여 양변에 \(b\)를 곱하는 조작을 가능하게 함으로써 유클리드 보조정리를 낳는다. 유클리드 보조정리의 일반형은 예제 2.3에서 두 소인수분해 \(p_1 \cdots p_k = q_1 \cdots q_m\) 가운데 \(p_1\)과 같은 \(q_j\)를 지목해 주어, 짝을 지우고 더 작은 수로 내려가는 최소 반례 논증을 굴러가게 한다. 유일성이 이 보조정리를 필요로 하는 이유는 등식만으로는 지울 짝이 지정되지 않기 때문이며, 보조정리가 성립하지 않는 힐베르트 수 \(H = \{4k+1\}\)에서는 실제로 \(441 = 21 \cdot 21 = 9 \cdot 49\)처럼 두 분해가 공존한다.

풀이 (b). (예시 답안) 네 자리가 서로 다른 것을 미뤄 두었다. C7주차 §1.8은 유클리드 보조정리를 “S15주차 문제 10에서 증명”으로 등록했지만 그 증명이 베주 항등식을 기성품으로 인용한 상태였고(예제 2.2의 “\(p \mid a^2\)이면 \(p \mid a\)” 두 줄이 그 인용을 실제로 썼다), C11주차 §1.7은 같은 보조정리를 “인정하고 쓴 것”으로 올려 \(\mathbb{Z}_p\)에 영인자가 없음을 보이며 “\(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)”를 썼으며, C8주차 §1.7은 소인수분해의 유일성을 목록에서 빼 두었고, C13주차 §1.8은 기약분수 표현의 유일성(문제 11)을 인정하고 썼다. 이번 주에 정리 1.3에서 정리 1.4를 거쳐 정리 1.5의 유일성까지가 증명되었으므로 네 자리가 모두 표시 없는 정식 인용이 되었고, 기약분수 표현의 유일성도 훈련 2의 명제를 두 번 쓰면 따라 나온다.

덧붙임 — C14주차는 외상이 아니다. C14주차 예제 2.2는 \(g(m,n) = 2^m 3^n\)의 단사성을 소인수분해의 유일성에 기대지 않고 홀짝 논증(1권 1주차 문제 8)만으로 자립적으로 처리했다. 이번 주가 갚는 것은 그 자리의 빚이 아니라, 유일성을 쓰면 한 줄로 끝날 자리를 우회했던 것을 이제 한 줄로 적어도 된다는 허가다. 청산 목록에 C14주차를 넣은 답안은 §1.8의 표와 대조해 바로잡는다.

복기. 이런 서술 문항의 채점 기준은 낱말의 나열이 아니라 의존의 방향이다. “베주가 있어야 보조정리가 서고, 보조정리가 있어야 유일성이 선다”는 순서가 답안에서 한 방향으로 흐르는지 확인한다. 방향이 흐려지면 준비 운동 유형 2의 순환으로 되돌아간다.

다음 주 예고 (C16): Chartrand 13장 — 조합론. 이번 주가 나눗셈의 등식을 다뤘다면 다음 주는 세는 일을 증명으로 만든다. 1권 12~14주차의 순열\(\cdot\)조합과 비둘기집 원리가 Chartrand의 언어로 다시 조직되고, 반복 조합과 이항정리가 더해진다. 특히 같은 수를 두 가지 방법으로 세어 항등식을 얻는 이중 세기가 새 도구로 들어오는데, 문제 14에서 약수의 개수를 지수 조합으로 센 논증이 그 예행연습이었다. 원서 13장을 통독하고 온다.