C15주차 — 정수론: 최대공약수와 산술의 기본정리

내용

C15주차 — 정수론: 최대공약수와 산술의 기본정리#

이 주의 길잡이

핵심 문장: “서로소”는 말이지 등식이 아니다. 그 말을 등식 \(ax + by = 1\)로 바꿔 주는 정리가 베주 항등식이고, 그 등식이 유클리드 보조정리를 낳고, 그 보조정리가 산술의 기본정리의 유일성을 완성한다.

이 주의 위치: 2학기 20주 과정의 C15주차. 1권 33주차 문제 16이 “증명은 정수론 과목의 몫”이라 적어 두었고, 네 주차가 각각 다른 항목을 미뤄 두었다 — C7주차 §1.8은 유클리드 보조정리를 “S15주차 문제 10에서 증명”으로 등록했으나 그 증명이 기댄 베주 항등식이 미증명이었고, C11주차 §1.7은 같은 보조정리를 “인정하고 쓴 것”으로 올렸으며, C8주차 §1.7은 소인수분해의 유일성을, C13주차 §1.8은 기약분수 표현의 유일성을 뒤로 미뤘다. 그 넷이 여기서 세워진다. S15주차 문제 10이 기성품으로 인용한 베주 항등식이 이번 주의 첫 정리다. 다음 주 C16주차의 조합론은 이번 주의 나눗셈 계산을 세는 기술로 바꿔 쓴다.

원서 대응: Chartrand 12장 (Proofs in Number Theory). 1일차에 이 장을 통독한 상태로 이 교안에 온다.

이번 주 목표#

최대공약수를 정의하고, 정의의 조각마다 그것을 지우면 무엇이 무너지는지 설명한다.
유클리드 호제법의 네 걸음을 백지에 쓰고, 각 걸음의 근거를 나눗셈 정리와 C6주차 (D2)로 댄다.
베주 항등식을 최소원리로 증명하고, 호제법의 역대입으로 계수 \(x, y\)를 실제로 계산한다.
베주로 유클리드 보조정리를 증명하고, 그 보조정리로 산술의 기본정리의 유일성을 완성한다.

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

표기 — § 와 난이도 표시

§는 “절”이라고 읽는다. §1.5는 이 주차의 1.5 절을, §6은 6절 전체를 가리킨다.

다른 주차를 가리킬 때는 “C6주차 §1.2”처럼 주차를 앞에 적는다.

연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서

3으로 갈수록 지지대가 줄어든다.

준비 운동 (C14주차 복습)#

지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다.

C14주차의 기수 비교 \(|A| \le |B|\)의 정의와 CSB 활용 서식 세 걸음을 쓰시오.
C6주차의 나눗셈 기본 성질 (D1) 추이 \(\cdot\) (D2) 선형결합 \(\cdot\) (D3) 크기를 진술하고, (D2)를 증명한 C6주차 예제 2.1을 백지에 재현하시오. 이번 주의 §1.4와 §1.5는 (D2)와 (D3)만으로 굴러간다.
C7주차 §1.8이 유클리드 보조정리를 “S15주차 문제 10에서 증명”으로 등록한 자리, C11주차 §1.7이 같은 보조정리를 “1권 33주차 문제 16에서 인정하고 쓴 것”으로 올려 둔 자리, C8주차 §1.7이 소인수분해의 유일성을 미뤄 둔 자리, C13주차 §1.8이 기약분수 표현의 유일성을 미뤄 둔 자리를 각각 찾아 확인하시오. 네 자리의 취급이 서로 다르다는 것까지 적어 둔다 — S15주차 문제 10의 증명은 베주 항등식을 기성품으로 인용한 상태였다.

이어서 진단 문제 하나를 풀어 보자. 풀지 못해도 된다 — 이번 주가 무엇을 메우는지 가늠하기 위한 기록이다.

(진단) 소수 \(p\)와 정수 \(a, b\)에 대해 “\(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)이다”를

지금 가진 도구만으로 증명해 보시오.

답을 노트에 적어 둔다. §5의 백지 재현 뒤에 이 기록을 다시 본다.

자주 나오는 세 가지 답#

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 자연스러운 출발점이고, 셋 다 이번 주에 메울 정확한 간격이 있다.

유형 1 — 정의를 풀고 밀어붙이기. “\(p \mid ab\)이므로 \(ab = pk\)인 정수 \(k\)가

존재한다. \(p\)는 소수이므로 양의 약수가 1과 \(p\)뿐이다. 따라서 …”라고 적고 멈춘다. 정의를 등식으로 푼 것까지는 정확하다 — 이 과정의 표준 첫걸음이다. 간격은 얻은 등식이 곱 \(ab\) 전체에 대한 등식이라는 데 있다. 결론은 \(a\) 하나 또는 \(b\) 하나에 대한 주장이므로, \(ab = pk\)에서 \(a\)나 \(b\)를 따로 떼어내는 통로가 하나 더 필요하다. 그 통로를 만드는 것이 §1.5다.

유형 2 — 소인수분해로 답하기. “\(ab\)의 소인수분해에 \(p\)가 들어 있으므로

\(a\) 또는 \(b\)의 소인수분해 어딘가에 \(p\)가 있다.” 결론은 참이고 그림도 정확하다. 간격은 그 추론이 소인수분해가 유일함을 이미 쓰고 있다는 데 있다. 그런데 유일성의 증명이 바로 이 보조정리를 재료로 쓴다(§1.7) — 곧 이 답은 순환이다. 순환을 끊으려면 소인수분해를 거치지 않는 증명이 있어야 하고, 그것이 §1.6이다.

유형 3 — 소거법 서식까지. S15주차 정의 15.2의 소거법을 골라 걸음 ①

“\(p \nmid a\)라 하자”까지 적고 멈췄다. 도구 선택은 정확하다 — 결론이 \(\lor\)이므로 소거법이 정확한 서식이다(S15주차 §1.7의 판정표). 간격은 걸음 ②에 있다. \(p \nmid a\)에서 곧바로 나오는 것은 “\(p\)와 \(a\)의 공약수는 1뿐이다”라는 말인데, 말로는 계산이 시작되지 않는다. §1.1이 그 막힘을 그대로 재연한다.

개념 — 말을 등식으로 바꾸기#

1 소거법의 걸음 ②에서 어디가 막히는가#

새 정리를 꺼내기 전에, 지금 가진 도구 — 나눗셈의 정의와 (D1)~(D3), 소수의 정의, 소거법의 서식 — 만으로 준비 운동 4번을 끝까지 밀어붙여 본다.

시도 — 소거법으로 밀어붙이기

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

“\(p \mid ab\)라 하자. 소거법을 쓴다. \(p \nmid a\)라 하자 [걸음 ①].

\(p\)는 소수이므로 \(p\)의 양의 약수는 1과 \(p\)뿐이다. \(p\)와 \(a\)의 공약수는

\(p\)의 양의 약수이므로 1이거나 \(p\)인데, \(p\)이면 \(p \mid a\)가 되어 걸음 ①과

충돌한다. 따라서 \(p\)와 \(a\)의 공약수는 1뿐이다. 그러므로 \(b\)는 … “

여기서 멈춘다. 다음 줄이 나오지 않는다.

확인 1. 멈춘 자리에서 손에 쥔 것은 “\(p\)와 \(a\)의 공약수는 1뿐이다”이다. 다음 줄로 나아가려면 이 사실이 어떤 종류의 정보로 바뀌어야 하는가. 그리고 그 다음 줄에서 \(b\)를 등장시키려면 무엇을 해야 하는가.

답

등식으로 바뀌어야 한다. “공약수가 1뿐”은 어떤 수들의 목록에 대한 서술이지

\(p\)나 \(a\)의 생김새를 주는 등식이 아니므로, 대입할 것도 곱할 것도 없다.

\(b\)를 등장시키는 방법은 하나뿐이다 — \(p\)와 \(a\)만 들어 있는 등식을 하나

확보한 뒤 그 양변에 \(b\)를 곱하는 것이다. 곱할 등식이 없으니 \(b\)를 무대에

올릴 방법이 없고, 그래서 다음 줄이 나오지 않는다.

(준비 운동 유형 1이 멈춘 자리도 같은 자리다. 그쪽은 \(ab = pk\)라는 등식을

쥐었지만 그 등식이 \(a\)와 \(b\)를 붙여 놓은 채라 떼어낼 수 없었다.)

이 주 전체의 기준

“공약수”, “서로소”, “최대공약수”는 전부 말이다.

이 말들을 계산 가능한 등식으로 바꿔 주는 정리가 베주 항등식이고,

이번 주의 세 정리는 모두 그 한 번의 번역 위에 선다.

2 사례를 모아 보기 — 공약수의 목록#

말부터 정확히 한다. 두 정수를 동시에 나누는 정수를 공약수라 부른다. 몇 쌍에 대해 양의 공약수를 전부 적어 보자.

\(a\)	\(b\)	\(a, b\)의 양의 공약수 전체	그중 가장 큰 것
\(48\)	\(18\)	\(1, 2, 3, 6\)	\(6\)
\(35\)	\(15\)	\(1, 5\)	\(5\)
\(14\)	\(9\)	\(\underline{\quad(1)\quad}\)	\(\underline{\quad(2)\quad}\)
\(12\)	\(0\)	\(\underline{\quad(3)\quad}\)	\(\underline{\quad(4)\quad}\)
\(0\)	\(0\)	모든 양의 정수	\(\underline{\quad(5)\quad}\)

확인 2. 표의 (1)~(5)를 채워 보자. 넷째 행에서 \(0\)의 양의 약수가 무엇인지 먼저 정하고, 다섯째 행에서는 “가장 큰 것”이 실제로 뽑히는지 판정한다.

답

(1) \(1\) (2) \(1\) (3) \(1, 2, 3, 4, 6, 12\) (4) \(12\) (5) 없다.

넷째 행: 임의의 정수 \(c\)에 대해 \(0 = c \times 0\)이므로 \(c \mid 0\)이다(정의 6.1).

곧 \(0\)은 모든 정수로 나누어떨어지므로, \(12\)와 \(0\)의 공약수는 \(12\)의 양의 약수

전부이고 그중 최대는 \(12\)다.

다섯째 행: 모든 양의 정수가 공약수이므로 목록에 끝이 없고, 가장 큰 것을 뽑을

수 없다. 이 한 줄이 아래 정의에서 “둘 다 \(0\)은 아닌”이라는 조각이 필요한 이유다.

확인 3. 표의 어느 행에서도 공약수의 목록이 유한하게 끊겼다 — 다섯째 행만 빼고. 목록이 끊기는 이유를 (D3)으로 설명해 보자.

답

\(a\)와 \(b\) 중 \(0\)이 아닌 쪽을 하나 잡아 그것을 \(b_0\)이라 하자 (다섯째 행을 뺀

모든 행에서 그런 쪽이 있다). \(c\)가 \(a, b\)의 공약수이면 특히 \(c \mid b_0\)이고

\(b_0 \ne 0\)이므로 (D3)에 의해 \(|c| \le |b_0|\)이다. 곧 모든 공약수가 \(-|b_0|\)와

\(|b_0|\) 사이에 갇히므로 후보가 유한하고, 그중 최대가 반드시 뽑힌다.

넷째 행이 \(b = 0\)인 자리이므로 거기서는 \(b_0 = a = 12\)를 잡는다.

다섯째 행에서만 이 논증이 무너지는 이유는 \(a\)와 \(b\)가 둘 다 \(0\)이라

잡을 \(b_0\)이 없기 때문이다 — (D3)을 걸 상대가 없다.

이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 표의 넷째 열에 한 일을 문장으로 굳혔을 뿐이다.

정의 1.1 — 최대공약수 (greatest common divisor) [백지 암기 대상]#

둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해, \(a\)와 \(b\)를 모두 나누는 정수 중 가장 큰

것을 \(a\)와 \(b\)의 최대공약수라 하고 \(\gcd(a, b)\)로 쓴다.

표기 — \(\gcd(a, b)\)

“지시디 에이 비” 또는 “에이와 비의 최대공약수”로 읽는다. \(\gcd(a,b)\)는 문장이

아니라 수다 — \(a \mid b\)가 참\(\cdot\)거짓이 정해지는 문장인 것과 다르다(C6주차 §1.2).

그래서 \(\gcd(a,b)\)는 등식의 한쪽에 놓을 수 있고, 그것이 §1.5의 출발점이다.

정의 1.2 — 서로소 (relatively prime) [백지 암기 대상]#

정수 \(a, b\)가 서로소라는 것은 \(\gcd(a, b) = 1\)이라는 뜻이다.

3 정의 해부 — 조각마다 하는 일#

정의 1.1은 네 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다.

조각	하는 일	증명에서의 역할
“둘 다 \(0\)은 아닌 정수 \(a, b\)”	적용 전제	인용하기 전에 이 조건을 확인한다. 확인 2의 다섯째 행이 위반 사례다
“\(a\)와 \(b\)를 모두 나누는”	후보 자격	두 나눗셈 조건을 동시에 요구한다. 하나만 만족하면 그냥 약수이지 공약수가 아니다
“정수 중”	무대	후보를 정수로 묶어 두어야 (D3)이 걸리고 목록이 유한해진다
“가장 큰 것”	유일한 값의 지정	\(\gcd(a,b)\)를 수 하나로 확정한다. 이 조각이 있어야 \(\gcd(a,b) = ax+by\) 같은 등식이 뜻을 가진다

조각 삭제 실험 1 — “가장 큰”을 지우면. “공약수 중 하나”로 바꿔 보자. 그러면 \(\gcd(48, 18)\)이 \(1\)이어도 되고 \(2\)여도 되고 \(6\)이어도 된다.

확인 4. “가장 큰”을 지우는 순간 정확히 무엇이 무너지는가. §1.5에서 증명할 “\(\gcd(a,b) = ax + by\)”라는 문장이 어떻게 되는지로 답해 보자.

답

\(\gcd(a,b)\)가 수를 하나로 지정하지 못한다. 그러면 “\(\gcd(a,b) = ax + by\)”는

좌변이 무엇인지 정해지지 않은 등식이므로 참\(\cdot\)거짓을 판정할 수 없고, 검산할

수도 없다. 실제로 \(48\)과 \(18\)의 공약수 \(1\)에 대해서는 \(1 = 48x + 18y\)인 정수

\(x, y\)가 없다 — \(48x + 18y\)는 언제나 \(6\)의 배수이기 때문이다. 곧 “가장 큰”은

편의를 위한 수식어가 아니라 §1.5의 정리를 참으로 만드는 조각이다.

조각 삭제 실험 2 — “둘 다 0은 아닌”을 지우면. \(\gcd(0,0)\)을 허용하면 확인 2의 다섯째 행이 그대로 반례가 된다 — 공약수의 목록에 끝이 없어 최대가 존재하지 않는다. 존재하지 않는 것에 이름을 붙인 셈이므로, 이후의 모든 정리에서 \(\gcd(0,0)\)이 나오는 순간 문장이 무의미해진다.

대칭과 부호. 정의는 \(a\)와 \(b\)를 대등하게 다루므로 \(\gcd(a,b) = \gcd(b,a)\)이고, \(c \mid a\)와 \(c \mid (-a)\)가 같은 뜻이므로 \(\gcd(a,b) = \gcd(|a|, |b|)\)이다. 계산에서는 언제나 음이 아닌 쪽으로 바꿔 놓고 시작한다.

4 절차 해부 — 유클리드 호제법#

공약수의 목록을 매번 적는 방식은 수가 커지면 쓸 수 없다. \(\gcd(1147, 899)\)에서 \(1147\)의 약수를 전부 찾는 일부터 막힌다. 목록을 만들지 않고 \(\gcd\)를 얻는 절차가 유클리드 호제법이고, 그 근거는 다음 한 줄이다.

보조 명제 1.A — 나눗셈이 공약수를 보존한다

정수 \(a, b, q, r\)에 대해 \(a = bq + r\)이면, \(a\)와 \(b\)의 공약수 전체의 집합은

\(b\)와 \(r\)의 공약수 전체의 집합과 같다.

증명. \(d\)를 \(a\)와 \(b\)의 공약수라 하자. 곧 \(d \mid a\)이고 \(d \mid b\)이다. 그러면 (D2)에 의해 \(d \mid (a \cdot 1 + b \cdot (-q))\)이고, \(a - bq = r\)이므로 \(d \mid r\)이다. \(d \mid b\)는 이미 있으므로 \(d\)는 \(b\)와 \(r\)의 공약수다. 거꾸로 \(d\)를 \(b\)와 \(r\)의 공약수라 하자. (D2)에 의해 \(d \mid (b \cdot q + r \cdot 1)\)이고, \(bq + r = a\)이므로 \(d \mid a\)이다. 따라서 \(d\)는 \(a\)와 \(b\)의 공약수다. 두 집합이 서로를 포함하므로 같고, 같은 집합의 최대는 같으므로 \(\gcd(a, b) = \gcd(b, r)\)이다. \(\blacksquare\)

백지 암기 대상

유클리드 호제법 (Euclidean algorithm)

양의 정수 \(a, b\)의 \(\gcd\)를 구하려면 —

① 나눗셈 — 나눗셈 정리로 \(a = bq + r\), \(0 \le r < b\)인 \(q, r\)을 얻는다.

② 교체 — 보조 명제 1.A에 의해 \(\gcd(a,b) = \gcd(b,r)\)이므로 쌍 \((a,b)\)를 \((b,r)\)로 바꾼다.

③ 반복 — 나머지가 \(0\)이 될 때까지 ①②를 되풀이한다.

④ 회수 — 마지막으로 \(0\)이 아니었던 나머지가 \(\gcd(a,b)\)이다.

걸음마다 하는 일이 다르다. 하나를 빼면 무엇이 무너지는지가 그 걸음의 존재 이유다.

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 나눗셈	\(0 \le r < b\)인 나머지를 만든다	나머지가 작아진다는 보장이 사라져 ③이 끝나지 않는다 (아래 삭제 실험)
② 교체	같은 답을 갖는 더 작은 문제로 바꾼다	문제가 줄지 않는다. 교체를 정당화하는 것은 보조 명제 1.A 한 줄이다
③ 반복	나머지를 \(0\)까지 밀어 내린다	어디서 멈출지 정해지지 않는다
④ 회수	답을 읽어 낸다	계산은 끝났는데 답이 어느 수인지 지정되지 않는다

걸음 삭제 실험 — ①의 부등식을 지우면. “\(a = bq + r\)인 아무 \(q, r\)”만 요구해 보자. \(\gcd(48, 18)\)에서 \(q = 1\)을 골라 \(48 = 1 \cdot 18 + 30\)으로 적으면, ②에 따라 \(\gcd(18, 30)\)으로 옮겨 간다. 다시 \(18 = (-1) \cdot 30 + 48\)로 적으면 \(\gcd(30, 48)\)이 되고, \(30 = (-1) \cdot 48 + 78\)로 적으면 \(\gcd(48, 78)\)이 된다. 같은 방식으로 \(48 = (-1) \cdot 78 + 126\), … 이 끝없이 이어진다. 나머지가 작아지기는커녕 \(30 < 48 < 78 < 126 < \cdots\)으로 커지기만 하므로 \(r = 0\)에 닿는 걸음이 오지 않는다.

확인 5. 위 실험에서 보조 명제 1.A 자체는 여전히 참인가. 그렇다면 무엇이 잘못된 것인가.

답

보조 명제 1.A는 여전히 참이다 — 증명 어디에도 \(0 \le r < b\)를 쓰지 않았고,

(D2) 두 번이 전부다. 실제로

\(\gcd(48,18) = \gcd(18,30) = \gcd(30,48) = \gcd(48,78) = 6\)이 모두 맞다.

잘못된 것은 절차의 종료다. 부등식 \(0 \le r < b\)는 각 걸음에서 둘째 수가

반드시 작아지도록 강제하는 조각이고, 음이 아닌 정수는 무한히 내려갈 수 없으므로

유한 번에 \(r = 0\)에 닿는다. 부등식을 지우면 값이 커지는 쪽으로도 갈 수 있어

이 보장이 사라진다.

곧 ①의 부등식은 답의 정확성이 아니라 절차가 끝난다는 사실을 책임진다.

확인 6. 걸음 ④가 왜 답을 주는가. 마지막 줄이 \(12 = 2 \cdot 6 + 0\)이라면 그 다음 쌍은 \((6, 0)\)이다. \(\gcd(6, 0)\)을 정의 1.1로 직접 판정해 보자.

답

확인 2의 넷째 행과 같다. 모든 정수가 \(0\)을 나누므로 \(6\)과 \(0\)의 공약수는 \(6\)의

양의 약수 전부이고, 그중 최대는 \(6\)이다. 곧 \(\gcd(6,0) = 6\)이다.

일반적으로 \(d > 0\)이면 \(\gcd(d, 0) = d\)이므로, 마지막으로 \(0\)이 아니었던 나머지가

곧 답이다. 걸음 ④는 규칙이 아니라 정의 1.1의 직접 판정 한 번이다.

예. \(\gcd(1147, 899)\): \(1147 = 1 \cdot 899 + 248\), \(899 = 3 \cdot 248 + 155\), \(248 = 1 \cdot 155 + 93\), \(155 = 1 \cdot 93 + 62\), \(93 = 1 \cdot 62 + 31\), \(62 = 2 \cdot 31 + 0\). 따라서 \(\gcd(1147, 899) = 31\)이다. 약수 목록은 한 번도 만들지 않았다.

5 베주 항등식 — 말을 등식으로 바꾸는 정리#

§1.1이 멈춘 자리에서 필요한 것은 \(\gcd\)를 한쪽에 놓은 등식이었다. 그런 등식이 실제로 존재한다는 것이 이번 주의 중심 정리다.

\(x, y\)가 정수일 때 \(ax + by\) 꼴의 수를 \(a\)와 \(b\)의 정수 선형결합이라 부른다. (D2)가 다루는 그 꼴이고, 이번 절에서는 그것이 \(\gcd\)의 정체임이 밝혀진다.

정리 1.3 — 베주 항등식 (Bézout’s identity) [백지 암기 대상]#

둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해, \(\gcd(a, b) = ax + by\)인 정수 \(x, y\)가 존재한다.

더 정확히, \(\gcd(a,b)\)는 \(a\)와 \(b\)의 정수 선형결합 중 가장 작은 양수다.

증명의 도구는 1권 33주차의 최소원리다. 어느 집합에 적용할지부터 정한다.

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

확인 7. 최소원리를 인용하려면 먼저 \(S \ne \varnothing\)을 보여야 한다(1권 33주차의 조각 표 첫 줄). \(S\)의 원소를 하나 실제로 제시해 보자. 가정 “둘 다 \(0\)은 아닌”이 어디서 쓰이는지도 밝힌다.

답

\(x = a\), \(y = b\)를 넣으면 \(a \cdot a + b \cdot b = a^2 + b^2\)이다. \(a\)와 \(b\) 중

적어도 하나가 \(0\)이 아니므로 그 제곱이 양수이고, 나머지 하나의 제곱은 \(0\) 이상이라

\(a^2 + b^2 > 0\)이다. 따라서 \(a^2 + b^2 \in S\)이다.

가정 “둘 다 \(0\)은 아닌”이 정확히 이 부등식에서 소비된다. 둘 다 \(0\)이면

\(S\)가 공집합이 되어 최소원리를 인용할 자격이 없다.

증명. \(S\)는 공집합이 아닌 양의 정수의 부분집합이므로, 최소원리(1권 33주차)에 의해 최소원소를 가진다. 그것을 \(d\)라 하고, \(d \in S\)이므로 \(d = ax_0 + by_0\)인 정수 \(x_0, y_0\)을 잡아 둔다. 이 \(d\)가 \(\gcd(a,b)\)임을 두 단계로 보인다.

단계 1 — \(d\)는 \(a\)와 \(b\)의 공약수다. 나눗셈 정리(1권 33주차 예제 2.2)에 의해 \(a = dq + r\), \(0 \le r < d\)인 정수 \(q, r\)이 존재한다.

확인 8. \(r\)을 \(a\)와 \(b\)의 정수 선형결합으로 적어 보자. \(r = a - dq\)에 \(d = ax_0 + by_0\)을 대입하고 \(a\)와 \(b\)로 묶는다.

답

\(r = a - dq = a - (ax_0 + by_0)q = a - ax_0q - by_0q = a(1 - x_0 q) + b(-y_0 q)\).

\(1 - x_0q\)와 \(-y_0q\)는 정수이므로(근거 ②) \(r\)은 \(a\)와 \(b\)의 정수 선형결합이다.

확인 9. 만약 \(r > 0\)이라면 무엇과 모순인가. 그 모순에서 \(r\)의 값이 무엇으로 확정되는지까지 적어 보자.

답

\(r > 0\)이고 \(r\)이 선형결합이므로 \(r \in S\)이다. 그런데 나눗셈 정리가 준

부등식은 \(r < d\)이므로, \(d\)보다 작은 \(S\)의 원소가 있다는 뜻이 되어 \(d\)가 \(S\)의

최소원소라는 사실과 모순이다. 따라서 \(r > 0\)은 불가능하고, \(0 \le r\)이므로

\(r = 0\)으로 확정된다.

\(r = 0\)이므로 \(a = dq\), 곧 \(d \mid a\)이다. \(b\)에 대해서도 나눗셈 정리를 적용하고 같은 계산을 하면 — \(b = dq' + r'\)에서 \(r' = a(-x_0q') + b(1 - y_0q')\) — 마찬가지로 \(r' = 0\)이고 \(d \mid b\)이다. 따라서 \(d\)는 \(a\)와 \(b\)의 공약수다.

단계 2 — \(d\)는 공약수 중 가장 크다. \(c\)를 \(a\)와 \(b\)의 임의의 공약수라 하자.

확인 10. \(c \le d\)를 보이려 한다. \(c \mid a\)와 \(c \mid b\)에서 출발해 어떤 성질을 어떤 순서로 쓰는가.

답

먼저 (D2)를 쓴다: \(c \mid a\)이고 \(c \mid b\)이므로 임의의 정수 \(x_0, y_0\)에 대해

\(c \mid (ax_0 + by_0)\), 곧 \(c \mid d\)이다.

다음에 (D3)을 쓴다: \(d \in S\)이므로 \(d > 0\), 특히 \(d \ne 0\)이라 \(|c| \le |d| = d\)이다.

\(c \le |c|\)이므로 \(c \le d\)이다.

따라서 \(d\)는 \(a\)와 \(b\)의 공약수이면서 모든 공약수보다 크거나 같으므로, 정의 1.1에 의해 \(d = \gcd(a,b)\)이다. 그리고 \(d = ax_0 + by_0\)이었다. \(\blacksquare\)

백지 암기 대상

따름정리 1.3.1 — 서로소 판정

둘 다 \(0\)은 아닌 정수 \(a, b\)에 대해, \(\gcd(a,b) = 1\)인 것과 \(ax + by = 1\)인

정수 \(x, y\)가 존재하는 것은 서로 같다.

(\(\Rightarrow\))는 정리 1.3에 \(\gcd(a,b) = 1\)을 넣은 것이다. (\(\Leftarrow\))는 문제 6에서 증명한다 — 공약수 \(d\)가 \(1\)을 나누므로 \(d = 1\)이라는 두 줄이다.

1권에서 손으로 하던 일이 여기서 이름을 얻는 자리. 1권 2주차 이래로 두 수의 공약수를 다룰 때 한 일은 약수를 나열해 겹치는 것을 눈으로 고르는 작업이었고, 그 작업은 답을 주지만 다음 줄의 재료를 주지는 않았다. 정리 1.3은 그 나열 전체를 등식 하나로 대신한다. 이번 주에 새로 생기는 것은 \(\gcd\)라는 개념이 아니라 \(\gcd\)를 등식의 한쪽에 놓을 수 있다는 사실이며, 그것이 §1.6과 §1.7의 모든 줄을 가능하게 한다.

구성적으로 얻는 법. 정리 1.3의 증명은 최소원리를 썼으므로 \(x, y\)가 존재한다는 것만 말하고 값을 주지 않는다. 값이 필요할 때는 호제법의 나눗셈 줄들을 거꾸로 대입한다 — 그 절차가 확장 유클리드 호제법이고, 예제 2.1에서 함께 만든다.

6 유클리드 보조정리 — 미뤄 둔 증명의 청산#

정리 1.3이 확보한 등식을 §1.1이 멈춘 자리에 꽂으면 준비 운동 4번이 끝난다.

정리 1.4 — 유클리드 보조정리 (Euclid’s lemma) [백지 암기 대상]#

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

증명은 예제 2.2에서 한 줄씩 만든다. 여기서는 정리가 요구하는 가정과 그 가정이 소비되는 자리만 확인한다.

확인 11. 정리 1.4에서 “\(p\)가 소수”라는 가정을 “\(p\)가 \(1\)보다 큰 정수”로 약화하면 명제가 거짓이 된다. 반례를 하나 만들어 보자.

답

\(p = 6\), \(a = 2\), \(b = 3\). \(ab = 6\)이고 \(6 \mid 6\)이지만 \(6 \nmid 2\)이고 \(6 \nmid 3\)이다.

\(p = 4\), \(a = b = 2\)도 반례다 — \(4 \mid 4\)이지만 \(4 \nmid 2\)이다.

1권 2주차 문제 15와 C7주차 예제 2.1의 명제 \(C\)가 같은 반례를 다뤘다. 이 문제는

문제 10에서 제시된 증명의 평가 형태로 다시 나온다.

소수 가정이 소비되는 자리는 정확히 한 줄이다. \(p \nmid a\)일 때 \(\gcd(p, a) = 1\)을 얻는 줄이며, 그 줄이 성립하는 이유는 \(\gcd(p,a)\)가 \(p\)의 양의 약수인데 소수의 양의 약수가 \(1\)과 \(p\)뿐이기 때문이다. 합성수에서는 이 줄이 무너진다 — \(\gcd(6, 2) = 2\)다.

정리 1.4의 일반형

\(p\)가 소수이고 \(p \mid a_1 a_2 \cdots a_n\)이면, 어떤 \(i\)에 대해 \(p \mid a_i\)이다.

\(n\)에 대한 귀납으로 얻는다(문제 13). §1.7의 유일성 증명이 쓰는 것은 이 일반형이다.

확인 12. 정리 1.4가 세워지자 곧바로 정당해지는 인용이 여러 곳에 있다. C7주차 예제 2.2(\(\sqrt p\)가 무리수)의 어느 줄이 그 인용이었는지 적어 보자.

답

“\(p \mid a^2\)이므로 \(p \mid a\)이다”라는 줄과, 뒤에서 같은 논법을 \(b\)에 반복하는

줄 두 개다. \(a^2 = a \cdot a\)로 보면 정리 1.4의 \(ab\) 꼴이고, 결론 “\(p \mid a\) 또는

\(p \mid a\)”가 곧 \(p \mid a\)이다. C7주차 §1.8은 이 인용의 출처를 “S15주차 문제 10에서

증명”으로 적어 두었는데, 그 증명이 베주 항등식을 기성품으로 인용한 상태였다 —

이번 주에 정리 1.3이 서면서 그 미증명 자리가 메워진다. C8주차 문제 14

(\(3 \mid x^2\)에서 \(3 \mid x\))와, C11주차가 \(\mathbb{Z}_p\)의 영인자 부재를 보이며 쓴

일반 꼴 인용(\(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\))도 함께 정당해진다.

7 산술의 기본정리 — 존재와 유일#

정리 1.5 — 산술의 기본정리 (fundamental theorem of arithmetic) [백지 암기 대상]#

\(1\)보다 큰 모든 정수는 소수들의 곱으로 나타낼 수 있고, 그 표현은 소수들의 순서를

무시하면 유일하다.

이 정리는 의무가 둘인 명제다 — 존재와 유일은 별개의 책임이고(C7주차 §1.7), 증명하는 도구도 서로 다르다.

부분	진술	증명	도구
존재	\(n \ge 2\)는 소수이거나 소수들의 곱이다	C8주차 예제 2.2 (1권 33주차 예제 2.1)	강한 귀납
유일	두 소인수분해는 순서를 빼면 같다	이번 주 예제 2.3	정리 1.4의 일반형 + 최소 반례

확인 13. 존재를 증명한 강한 귀납의 논법을 유일성에 그대로 쓰려고 하면 어디서 막히는가. \(n = p_1 \cdots p_k = q_1 \cdots q_m\)이라는 두 분해를 손에 쥐었다고 하고, 다음 줄을 적어 보자.

답

다음 줄이 나오지 않는다. 강한 귀납이 주는 것은 “\(n\)보다 작은 수들에서 유일하다”는

정보이고, 그것을 쓰려면 두 분해에서 같은 소수 하나를 짝지어 지우고 더 작은

수로 내려가야 한다. 그런데 \(p_1\)이 오른쪽 목록의 어느 \(q_j\)와 같은지는

\(n = q_1 \cdots q_m\)이라는 등식만으로 지정되지 않는다.

지정해 주는 것이 정리 1.4의 일반형이다 — \(p_1 \mid q_1 \cdots q_m\)이므로 어떤 \(q_j\)에

대해 \(p_1 \mid q_j\)이고, \(q_j\)가 소수라 \(p_1 = q_j\)가 된다. 곧 유일성이 유클리드

보조정리를 필요로 하는 이유는 “지울 짝을 찾는 일”에 있다.

유일성이 자명하지 않다는 증거. 곱셈이 정의된 다른 수 체계에서는 이 정리가 실제로 거짓이 된다. 힐베르트 수 \(H = \{1, 5, 9, 13, 17, 21, \ldots\}\) — \(4k+1\) 꼴의 양의 정수 전체 — 는 곱셈에 닫혀 있지만 \(441 = 21 \times 21 = 9 \times 49\)이고, \(9\), \(21\), \(49\)는 \(H\) 안에서 더 쪼갤 수 없다. 문제 15가 이 사례를 다룬다.

8 이번 주에 쓸 수 있는 근거 — 목록 갱신#

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식\(\cdot\)부등식의 성질 ④ 이미 증명한 명제. 이번 주가 채우는 것은 ①과 ④다.

근거	이번 주에 추가\(\cdot\)갱신되는 것	이번 주에는 이렇게 쓴다
① 정의	정의 1.1(최대공약수) \(\cdot\) 정의 1.2(서로소) \(\cdot\) 최소공배수(문제 18 앞의 도입 상자)	“서로소” \(\leftrightarrow\) “\(\gcd = 1\)” \(\leftrightarrow\) “\(ax+by=1\)이 존재” 사이를 번역한다
② 닫힘성	변화 없음	선형결합의 계수가 정수임을 별도 설명 없이 쓴다
③ 등식\(\cdot\)부등식의 성질	변화 없음	등식 양변에 \(b\)를 곱하는 조작이 §1.6의 핵심 걸음이다
④ 이미 증명한 명제	보조 명제 1.A(공약수 보존) \(\cdot\) 정리 1.3(베주) \(\cdot\) 따름정리 1.3.1(서로소 판정) \(\cdot\) 정리 1.4(유클리드 보조정리와 그 일반형) \(\cdot\) 정리 1.5(산술의 기본정리) \(\cdot\) 나눗셈의 (D1)(D2)(D3)(C6주차 예제 2.1, 문제 6, 문제 11) \(\cdot\) 최소원리와 나눗셈 정리의 존재\(\cdot\)유일(1권 33주차) \(\cdot\) 소인수분해의 존재(C8주차 예제 2.2)	“정리 1.3에 의해 \(ax + by = \gcd(a,b)\)인 정수 \(x, y\)가 있다”가 이번 주 답안의 표준 문구다

지워지는 표시. 네 주차가 미뤄 둔 항목이 서로 다르므로 갈라 적는다.

미뤄 둔 자리	미뤄 둔 항목과 그때의 취급	이번 주가 청산하는 것
C7주차 §1.8	유클리드 보조정리 — “S15주차 문제 10에서 증명”으로 등록	그 증명이 기성품으로 인용한 베주 항등식이 정리 1.3으로 증명된다
C8주차 §1.7	소인수분해의 유일성 — 목록에서 빼고 C15주차로 미룸	예제 2.3이 유일성을 증명해 목록에 올린다
C11주차 §1.7	유클리드 보조정리 — “1권 33주차 문제 16에서 인정하고 쓴 것”	정리 1.4가 증명되어 그 표시가 지워진다
C13주차 §1.8	기약분수 표현의 유일성 — “인정하고 쓴다”	훈련 2의 명제를 두 번 쓰면 따라 나온다 (아래)

이 넷은 이번 주부터 표시 없이 인용한다. 기약분수 표현의 유일성(C13주차 문제 11)은 훈련 2의 명제(”\(\gcd(a,b) = 1\)이고 \(a \mid bc\)이면 \(a \mid c\)”)를 두 번 쓰면 나온다 — \(\frac ab = \frac cd\)이고 둘 다 기약, \(b, d > 0\)이면 \(ad = bc\)이고, \(b \mid ad\)와 \(\gcd(a,b) = 1\)에서 \(b \mid d\), 대칭으로 \(d \mid b\)이므로 \(b = d\)이며 그러면 \(a = c\)다.

확인 14. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) “\(\gcd(a,b) = 1\)이므로 \(ax + by = 1\)인 정수 \(x, y\)가 존재한다.”

(나) “\(6 \mid ab\)이고 \(6 \nmid a\)이므로 유클리드 보조정리에 의해 \(6 \mid b\)이다.”

(다) “\(d \mid a\)이고 \(d \mid b\)이므로 \(d \mid (a - bq)\)이다.”

답

(가) 허용 — 근거 ④, 정리 1.3(또는 따름정리 1.3.1)이다. 인용할 때

\(a, b\)가 둘 다 \(0\)은 아님을 확인해야 하지만, \(\gcd\)가 이미 쓰였으므로 그 조건은

앞줄에서 충족되어 있다.

(나) 불허 — 정리 1.4의 가정 “\(p\)가 소수”가 충족되지 않았다. \(6\)은 합성수이고,

확인 11의 반례가 그대로 이 문장의 반례다. 문제 10이 이 오류를 정면으로 다룬다.

(다) 허용 — 근거 ④, (D2)를 \(x = 1\), \(y = -q\)로 쓴 것이다. 보조 명제 1.A의

첫 줄이 정확히 이 문장이다.