[이산구조 개념-22] 소수와 GCD/LCM — 정수의 DNA를 분해하다

1. 소수와 합성수의 정의 ⭐

정의

개념영문정의

소수	Prime	1보다 큰 정수 중 1과 자기 자신만을 양의 약수로 가지는 수
합성수	Composite	1보다 큰 정수 중 소수가 아닌 수 (1보다 큰 두 정수의 곱으로 구성)

원자와 분자 비유

소수는 숫자의 원자(Atom) — 더 이상 쪼갤 수 없는 가장 기본 단위. 합성수는 숫자의 분자(Molecule) — 소수 원자들이 결합한 것.

주요 소수 목록

범위소수

1~10	2, 3, 5, 7
11~20	11, 13, 17, 19
21~50	23, 29, 31, 37, 41, 43, 47

합성수 예시

합성수분해

4	2 × 2
6	2 × 3
8	2 × 2 × 2
9	3 × 3
10	2 × 5

⚠️ 중요한 함정 — 1은?

1은 소수도 합성수도 아니다.

수분류

0	정수론 분류 외 (음수도 아니고 양수도 아님)
1	단위(Unit) — 소수도 합성수도 아님
2	유일한 짝수 소수 ⭐
3, 5, 7, ...	소수
4, 6, 8, 9, ...	합성수

💡 시험 함정: "1은 소수다"라고 하면 틀린다. 소수와 합성수는 모두 1보다 큰 정수에서만 정의된다. 1은 어떤 분류에도 속하지 않는 특수한 수.

2의 특별함

2는 유일한 짝수 소수다. 이후의 모든 짝수는 2를 약수로 가지므로 합성수.

---

2. 소수의 무한성 — 유클리드의 증명

정리

소수는 무한히 많다. (Euclid, 기원전 300년경)

증명 (모순 증명) ⭐

9강에서 배운 모순 증명의 가장 유명한 응용.

1단계: 가정

"소수가 유한하다"고 가정. 모든 소수를 p₁, p₂, ..., pₙ이라 하자.

2단계: 모순적 수 만들기

N = p₁ × p₂ × ... × pₙ + 1 을 정의.

3단계: 모순 도출

케이스분석

N이 소수인 경우	우리가 나열한 소수에 없음 → 가정 위반
N이 합성수인 경우	N은 어떤 소수로 나뉠 수 있어야 함. 그러나 p₁~pₙ 어느 것으로 나눠도 나머지가 1. → 새 소수 존재 → 가정 위반

4단계: 결론

어느 쪽이든 모순 → 가정이 틀림 → 소수는 무한히 많음 ✅

💡 수학사적 의의: 이 증명은 2300년이 지났지만 여전히 가장 우아한 증명 중 하나로 평가된다. 단 4단계로 무한 개념을 다루는 마법 같은 논리.

---

3. 산술의 기본 정리 (Fundamental Theorem of Arithmetic) ⭐⭐⭐

정의

모든 양의 정수는 (오름차순으로 정렬된) 소수들의 곱으로 유일하게 표현된다.

두 가지 핵심

핵심설명

존재성	모든 정수는 소수의 곱으로 표현 가능
유일성	그 표현 방법은 (순서 무시 시) 단 하나

정수의 DNA 비유

모든 사람이 고유한 DNA를 가지듯, 모든 정수는 고유한 소수 DNA를 가진다.

소인수분해 예시

정수소인수분해

4	2 × 2 = 2²
12	2 × 2 × 3 = 2² × 3
60	2 × 2 × 3 × 5 = 2² × 3 × 5
100	2 × 2 × 5 × 5 = 2² × 5²
2000	2 × 2 × 2 × 2 × 5 × 5 × 5 = 2⁴ × 5³
2001	3 × 23 × 29

1의 처리

1은 빈 곱(Empty Product) 으로 정의됨. 어떤 소수도 곱하지 않은 상태.

산술의 기본 정리의 의의

의의설명

GCD/LCM 계산	소인수분해로 직접 구할 수 있음
암호학 기반	RSA의 핵심 토대
수론적 증명	수많은 정리의 출발점

💡 암호학 직결: RSA 암호는 "두 큰 소수를 곱하기는 쉬워도, 그 곱을 다시 두 소수로 분해하기는 매우 어렵다" 는 사실에 기반한다. 산술의 기본 정리가 존재를 보장하지만, 빠른 계산은 보장하지 않는다. 이 비대칭성이 인터넷 보안의 핵심.

---

4. 소수 판별 — 어떻게 빠르게 확인할까

단순 판별법

n이 소수인지 확인하려면 2부터 n−1까지 모두 나눠보면 된다 → O(n)

효율적 판별법 ⭐

2부터 √n까지만 확인하면 충분 → O(√n)

왜 √n까지만?

만약 n = a × b이고 a ≤ b라면, a ≤ √n이다. 즉, n의 약수가 있다면 √n 이하에 반드시 존재한다.

소수 판별 예제

97이 소수인가?

단계작업

1	√97 ≈ 9.85 → 2부터 9까지 확인
2	2, 3, 5, 7로 나눠보기
3	모두 나누어 떨어지지 않음
4	→ 97은 소수 ✅

에라토스테네스의 체 (역사적 알고리즘)

고대 그리스 수학자 에라토스테네스(기원전 200년경) 가 만든 알고리즘.

2부터 N까지의 수를 나열 → 소수의 배수를 차례로 지움 → 남는 수가 소수.

💡 현대 응용: 100자리 이상의 큰 수가 소수인지 판별하는 것은 여전히 어려운 문제. 밀러-라빈 소수 판정법 같은 확률적 알고리즘이 사용된다 (RSA 키 생성에 필수).

---

5. 최대공약수 (Greatest Common Divisor, GCD) ⭐⭐⭐

정의

두 정수 a, b(둘 다 0은 아님)의 공통 약수 중 가장 큰 양의 정수.

표기

gcd(a, b) = d

공식 정의

d = max{d : d | a ∧ d | b}

공통 블록 비유

두 건물 사이에서 가장 큰 공통 블록을 찾는 게임. 이 블록이 클수록 두 건물을 효율적으로 나눌 수 있다.

GCD 계산 — 약수 나열법

gcd(24, 36)을 구하라.

단계별 풀이

단계작업

1	24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
2	36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
3	공통 약수: 1, 2, 3, 4, 6, 12
4	가장 큰 공통 약수: 12 ✅

→ gcd(24, 36) = 12

---

6. 소인수분해를 이용한 GCD ⭐⭐⭐ 시험 빈출

핵심 원리

각 공통 소수의 지수 중 작은 것(min)을 선택

슬로건

"공통 분모는 보수적으로! min을 골라라!"

GCD 계산 알고리즘

단계작업

1	두 수를 소인수분해
2	공통 소수의 지수 중 min 선택
3	모두 곱함

GCD 계산 예제

gcd(84, 96)을 구하라.

1단계: 소인수분해

수소인수분해

84	2² × 3¹ × 7¹
96	2⁵ × 3¹ × 7⁰

2단계: 각 소수별 min 선택

소수84의 지수96의 지수min사용

2	2	5	2	2²
3	1	1	1	3¹
7	1	0	0	7⁰ = 1

3단계: 곱셈

gcd(84, 96) = 2² × 3¹ × 7⁰ = 4 × 3 × 1 = 12 ✅

검증

84 = 12 × 7, 96 = 12 × 8 → 12가 공통 약수 ✅

💡 시험 핵심: GCD를 빠르게 계산하려면 소인수분해 후 min 선택이 가장 안전한 방법이다. 약수 나열은 큰 수에서 시간이 너무 오래 걸린다.

---

7. 서로 소 (Relatively Prime / Coprime) ⭐

정의

gcd(a, b) = 1일 때 두 수를 서로 소라고 한다.

직관적 의미

두 수가 공통된 소인수가 전혀 없는 단절된 상태.

유전자 비유

두 사람이 전혀 다른 유전자를 가지고 있는 것과 비슷. 서로에게 영향을 주지 않는 독립 관계.

서로 소 판별 예시

두 수GCD서로 소?

21, 10	1	⭕ (21 = 3·7, 10 = 2·5)
8, 9	1	⭕ (8 = 2³, 9 = 3²)
14, 21	7	❌ (공통 소수 7)
15, 25	5	❌ (공통 소수 5)

⚠️ 시험 함정

서로 소라고 해서 두 수가 모두 소수일 필요는 없다.

두 수소수?서로 소?

9, 10	둘 다 합성수	⭕ 서로 소
4, 9	둘 다 합성수	⭕ 서로 소

→ 합성수끼리도 서로 소가 가능.

쌍으로 서로 소 (Pairwise Relatively Prime)

집합 안의 모든 쌍이 서로 소인 상태.

예시

집합 {10, 17, 21}이 쌍으로 서로 소인지 확인.

쌍GCD서로 소?

(10, 17)	1	⭕
(10, 21)	1	⭕
(17, 21)	1	⭕

→ 모든 쌍이 서로 소 → 쌍으로 서로 소 ✅

응용 분야

분야활용

RSA 암호	공개키와 비밀키가 서로 소 조건
분수 기약	분자와 분모가 서로 소일 때 기약분수
중국인의 나머지 정리	모듈로들이 쌍으로 서로 소 필요

💡 암호학 토대: RSA 공개키 e와 (p−1)(q−1)이 서로 소여야 RSA 알고리즘이 작동한다. "서로 소"는 단순한 수학 개념이 아니라 인터넷 보안의 필수 조건.

---

8. 최소공배수 (Least Common Multiple, LCM) ⭐⭐⭐

정의

두 정수 a, b의 공통 배수 중 가장 작은 양의 정수.

표기

lcm(a, b) = m

공식 정의

m = min{m > 0 : a | m ∧ b | m}

두 개구리 비유

서로 다른 보폭을 가진 두 개구리가 동시에 점프하다가 처음으로 같은 지점에 도달하는 운명적 만남.

LCM 계산 — 배수 나열법

lcm(6, 10)을 구하라.

단계작업

1	6의 배수: 6, 12, 18, 24, 30, 36, ...
2	10의 배수: 10, 20, 30, 40, ...
3	가장 작은 공통 배수: 30 ✅

→ lcm(6, 10) = 30

---

9. 소인수분해를 이용한 LCM ⭐⭐⭐

핵심 원리

각 소수의 지수 중 큰 것(max)을 선택

슬로건

"두 수의 배수가 되려면 양쪽 모든 요소를 충분히 포함! max를 골라라!"

LCM 계산 알고리즘

단계작업

1	두 수를 소인수분해
2	등장한 모든 소수의 지수 중 max 선택
3	모두 곱함

LCM 계산 예제

lcm(84, 96)을 구하라.

1단계: 소인수분해

수소인수분해

84	2² × 3¹ × 7¹
96	2⁵ × 3¹ × 7⁰

2단계: 각 소수별 max 선택

소수84의 지수96의 지수max사용

2	2	5	5	2⁵
3	1	1	1	3¹
7	1	0	1	7¹

3단계: 곱셈

lcm(84, 96) = 2⁵ × 3¹ × 7¹ = 32 × 3 × 7 = 672 ✅

검증

672 / 84 = 8 (정수) ✅ 672 / 96 = 7 (정수) ✅

---

10. GCD vs LCM 종합 비교 ⭐

항목GCDLCM

정의	가장 큰 공통 약수	가장 작은 공통 배수
약수/배수 방향	a, b의 약수	a, b의 배수
계산 시 지수 선택	min (작은 것)	max (큰 것)
비유	공통 블록 (나누는 관점)	만남의 지점 (배수 관점)
크기	gcd ≤ a, b ≤ lcm	a, b ≤ lcm

직관적 정리

상황GCDLCM

a = b	a (자기 자신)	a
a, b 서로 소	1	a × b
a | b	a	b

---

11. gcd × lcm = a × b의 아름다운 관계 ⭐⭐⭐

핵심 정리

두 양의 정수 a, b에 대해:

gcd(a, b) × lcm(a, b) = a × b

왜 성립하는가? — 수학적 증명

핵심 보조정리

임의의 두 수 x, y에 대해: min(x, y) + max(x, y) = x + y

증명

a와 b의 소인수분해:

• a = p₁^a₁ × p₂^a₂ × ... × pₙ^aₙ
• b = p₁^b₁ × p₂^b₂ × ... × pₙ^bₙ

GCD와 LCM 계산:

• gcd(a, b) = p₁^min(a₁,b₁) × ... × pₙ^min(aₙ,bₙ)
• lcm(a, b) = p₁^max(a₁,b₁) × ... × pₙ^max(aₙ,bₙ)

곱셈:

gcd(a, b) × lcm(a, b) = p₁^[min(a₁,b₁) + max(a₁,b₁)] × ... × pₙ^[min(aₙ,bₙ) + max(aₙ,bₙ)]

보조정리 적용:

= p₁^(a₁+b₁) × ... × pₙ^(aₙ+bₙ) = (p₁^a₁ × ... × pₙ^aₙ) × (p₁^b₁ × ... × pₙ^bₙ) = a × b ✅

검증 예제

a = 12, b = 18

항목계산

12	2² × 3¹
18	2¹ × 3²
gcd(12, 18)	2¹ × 3¹ = 6
lcm(12, 18)	2² × 3² = 36
gcd × lcm	6 × 36 = 216
a × b	12 × 18 = 216 ✅

실전 활용

GCD나 LCM 중 하나만 알면 다른 하나를 즉시 계산 가능

알고 있는 것구하는 것공식

gcd(a, b)	lcm(a, b)	lcm = (a × b) / gcd
lcm(a, b)	gcd(a, b)	gcd = (a × b) / lcm

예시

a = 12, b = 18, gcd = 6일 때 lcm은?

lcm = (12 × 18) / 6 = 216 / 6 = 36 ✅

💡 시험 핵심 단축키: 큰 수의 GCD가 어렵게 느껴지면, 유클리드 호제법(다음에 등장)으로 GCD를 먼저 구하고 → lcm = ab/gcd 공식으로 LCM을 즉시 계산. 이 콤보가 시험에서 시간을 절약한다.

---

12. 정수론 21~22강의 거대한 그림

정수론 파트 통합 정리

 

 

[21강] 정수의 기본
   나누어떨어짐 → 나눗셈 정리 → mod 연산
   ↓
   모듈로 합동 → 진법 변환 → 2진수 연산
   ↓
[22강] 소수의 세계
   소수·합성수 → 산술의 기본 정리 (소인수분해)
   ↓
   GCD, 서로 소, LCM
   ↓
   gcd × lcm = a × b
   ↓
[다음 단원] 암호학·관계·그래프

정수론의 응용 통합

응용 분야21강 개념22강 개념

해시 함수	mod 연산	—
암호학 (RSA)	모듈로 합동	소수, 서로 소
디지털 서명	모듈로 거듭제곱	큰 소수
컴퓨터 표현	진법 변환	—
분수 기약화	—	GCD
주기 동기화	—	LCM

---

📌 한눈에 보는 핵심정리

개념핵심

소수	1보다 큰 정수, 1과 자기 자신만 약수
합성수	1보다 큰 정수, 소수 아님
1의 위치	소수도 합성수도 아님
2의 특별함	유일한 짝수 소수
소수 무한성	유클리드 증명 (모순 증명)
산술의 기본 정리	모든 정수 = 소수의 곱 (유일)
소수 판별	√n까지만 확인
GCD	공통 약수 중 최대
GCD 계산	소인수분해 후 min 선택
서로 소	gcd(a,b) = 1, 합성수도 가능
LCM	공통 배수 중 최소
LCM 계산	소인수분해 후 max 선택
핵심 공식	gcd × lcm = a × b

---

🧠 예상문제 2제

문제 1. GCD와 LCM 종합 계산

두 수 120과 180의 GCD와 LCM을 모두 올바르게 구한 것은?

① gcd = 30, lcm = 720 ② gcd = 60, lcm = 360 ③ gcd = 12, lcm = 1800 ④ gcd = 60, lcm = 720

👉 정답: ②

1단계: 소인수분해

수분해

120	2³ × 3¹ × 5¹
180	2² × 3² × 5¹

2단계: GCD 계산 (min)

소수120 지수180 지수min

2	3	2	2
3	1	2	1
5	1	1	1

gcd(120, 180) = 2² × 3¹ × 5¹ = 4 × 3 × 5 = 60 ✅

3단계: LCM 계산 (max)

소수120 지수180 지수max

2	3	2	3
3	1	2	2
5	1	1	1

lcm(120, 180) = 2³ × 3² × 5¹ = 8 × 9 × 5 = 360 ✅

4단계: 검증

gcd × lcm = 60 × 360 = 21,600 a × b = 120 × 180 = 21,600 ✅

💡 시험 풀이 팁: GCD/LCM 문제는 소인수분해 표를 먼저 그리고, GCD는 min·LCM은 max만 정확히 적용하면 100% 풀린다. 그리고 gcd × lcm = a × b 공식으로 검증까지 하면 실수 없음.

---

문제 2. 서로 소와 산술의 기본 정리

다음 중 올바른 설명은?

① 두 합성수는 절대로 서로 소가 될 수 없다 ② 모든 양의 정수는 소수의 곱으로 유일하게 표현된다 ③ 1은 가장 작은 소수다 ④ gcd(a, b) × lcm(a, b) = a + b

👉 정답: ②

각 선택지 분석

번호분석평가

①	9와 10 모두 합성수지만 gcd(9, 10) = 1 → 서로 소	❌
②	산술의 기본 정리의 정확한 진술	⭕ 정답
③	1은 소수도 합성수도 아님. 가장 작은 소수는 2	❌
④	곱셈이 아니라 gcd × lcm = a × b (덧셈 아님)	❌

추가 검증 — ① 반례

두 합성수gcd서로 소?

9, 10	1	⭕
4, 9	1	⭕
8, 15	1	⭕
25, 49	1	⭕

→ 합성수끼리도 서로 소가 충분히 가능.

💡 추가 학습 — 시험 핵심 함정 정리:

함정진실

"1은 소수다"	1은 소수도 합성수도 아님
"서로 소면 둘 다 소수"	합성수끼리도 가능
"gcd × lcm = a + b"	gcd × lcm = a × b (곱셈)
"2는 합성수다 (짝수니까)"	2는 유일한 짝수 소수

이 4가지 함정만 명확히 구분해도 정수론 단답형의 80%를 맞출 수 있다.