1. 정수론(Number Theory)이란
정의
정수론은 정수와 나눗셈의 기본 속성 및 그 응용 분야를 탐구하는 수학의 한 분야.
작은 씨앗에서 거대한 나무로
정수론은 얼핏 보기에 단순한 정수와 나눗셈에서 시작하지만, 현대 정보 기술의 모든 기반이 여기서 자라난다.
정수론의 응용
| 해시 함수 | mod 연산 |
| 암호학 (RSA) | 소수, 모듈로 합동 |
| 디지털 서명 | 모듈로 거듭제곱 |
| 비트코인 | 큰 소수, 서로 소 |
| 의사 난수 생성 | 선형 합동법 |
| 에러 정정 코드 | 모듈로 합동 |
💡 충격 사실: 우리가 매일 사용하는 인터넷 보안, 비트코인, 카카오톡 메시지 암호화 — 이 모든 것이 수백 년 전부터 연구된 정수론의 응용이다. 가우스 시대의 순수 수학이 21세기 디지털 세상의 기반이 되었다.
2. 나누어떨어짐 (Divisibility) ⭐⭐⭐
정의
정수 a가 정수 b를 나눌 수 있다는 것은, b를 a로 나누었을 때 나머지가 0이 되는 것을 의미한다.
수학적 표현
a | b ⟺ b = ac를 만족하는 정수 c가 존재 (단, a ≠ 0)
기호 의미
| a | b | "a는 b를 나눈다" | b ÷ a의 나머지가 0 |
| a ∤ b | "a는 b를 나누지 못한다" | 나머지 존재 |
⚠️ 자주 헷갈리는 표기
| a | b | 관계 (참/거짓) |
| b / a | 값 (계산 결과) |
예: 3 | 12는 "참" (관계), 12 / 3은 "4" (값)
용어 정리
| 인수 | Factor | a (b의 인수) |
| 제수 | Divisor | a (b를 나누는 수) |
| 배수 | Multiple | b (a의 배수) |
예시
| 3 | 12 | ⭕ | 12 = 3 × 4 |
| 5 | 25 | ⭕ | 25 = 5 × 5 |
| 4 | 14 | ❌ | 14 = 4 × 3 + 2 (나머지 있음) |
| 2 | 0 | ⭕ | 0 = 2 × 0 |
짝수와 홀수의 정의
| 짝수 | 2 | n |
| 홀수 | 2 ∤ n |
3. 나누어떨어짐의 4대 절대 성질 ⭐⭐⭐
이 4가지 성질은 정수론 전체에서 가장 자주 사용된다.
4대 성질
| 1 | 0 나누기 | a | 0 | 모든 a에 대해 성립 |
| 2 | 합의 법칙 | a | b ∧ a | c → a | (b+c) | 2|4, 2|6 → 2|10 |
| 3 | 곱의 법칙 | a | b → a | bc | 2|4 → 2|12 |
| 4 | 삼단논법 | a | b ∧ b | c → a | c | 2|4, 4|8 → 2|8 |
직관적 이해
어떤 수든 0번 곱하면 0이므로, 0은 누구의 배수든 될 수 있다.
짝수 + 짝수 = 짝수, 3의 배수 + 3의 배수 = 3의 배수.
2의 배수에 무엇을 곱해도 결과는 2의 배수.
2가 4의 약수이고, 4가 8의 약수이면, 2도 8의 약수.
💡 시험 활용: 이 4가지 성질로 다양한 정수론 명제를 증명할 수 있다. 6강~10강의 증명 전략이 여기서 그대로 활용된다.
4. 나눗셈 정리 (Division Algorithm) ⭐⭐⭐
정의
임의의 정수 a와 양의 정수 d에 대해, a = dq + r을 만족하는 유일한 정수 q(몫)와 r(나머지)이 존재하며, 0 ≤ r < |d|.
사과 나누기 비유
14개의 사과를 3명에게 똑같이 나눈다.
- 몫 q = 4 (각 사람이 받는 개수)
- 나머지 r = 2 (남은 사과 개수)
- 남은 사과는 항상 나누는 수보다 작아야 함
4대 구성 요소
| 피제수 | Dividend | a | 나뉘는 수 |
| 제수 | Divisor | d | 나누는 수 (≠ 0) |
| 몫 | Quotient | q | q = ⌊a/d⌋ (바닥 함수) |
| 나머지 | Remainder | r | r = a − dq |
핵심 조건
0 ≤ r < |d| (나머지는 항상 제수보다 작고 0 이상)
계산 예제
a = 14, d = 3
| 1 | q = ⌊14/3⌋ = 4 |
| 2 | r = 14 − (3 × 4) = 14 − 12 = 2 |
| 3 | 검증: 14 = 3 × 4 + 2 ✅ |
| 4 | 조건 검증: 0 ≤ 2 < 3 ✅ |
음수 a의 경우 ⚠️
a = −14, d = 3은?
| 1 | q = ⌊−14/3⌋ = −5 (바닥 함수: −4.67 → −5) |
| 2 | r = −14 − (3 × (−5)) = −14 + 15 = 1 |
| 3 | 검증: −14 = 3 × (−5) + 1 ✅ |
| 4 | 조건 검증: 0 ≤ 1 < 3 ✅ |
💡 시험 함정: 음수에서 나머지는 항상 양수 또는 0이어야 한다. 14강의 바닥 함수 개념이 여기서 핵심이다.
5. mod 연산자 ⭐⭐⭐ 컴퓨터 과학의 필수
정의
a mod d는 정수 a를 양의 정수 d로 나누었을 때의 나머지 r만을 추출하는 연산.
공식
a mod d = a − d · ⌊a/d⌋
시계 비유
25시는 1시와 같다 → 25 mod 12 = 1
13시는 1시와 같다 → 13 mod 12 = 1
나눗셈 정리 vs mod
| 관심 대상 | 몫 q와 나머지 r 모두 | 나머지 r만 |
| 결과 | a = dq + r | a mod d = r |
mod 계산 예시
| 17 mod 5 | 2 (17 = 5×3 + 2) |
| 100 mod 7 | 2 (100 = 7×14 + 2) |
| 25 mod 12 | 1 (시계처럼) |
| 8 mod 8 | 0 |
| 0 mod 5 | 0 |
실생활 응용
| 시계 | 시간 mod 12 (또는 24) |
| 요일 계산 | 일수 mod 7 |
| 컴퓨터 프로그래밍 | C/Python의 % 연산자 |
| 배열 순환 | index mod 배열길이 |
| 해시 함수 | key mod 테이블크기 |
💡 프로그래밍 직결: Python·C·Java의 % 연산자가 바로 mod 연산자다. 17 % 5 = 2, 100 % 7 = 2. 매일 쓰는 연산이지만 그 수학적 정의는 정수론에서 왔다.
6. 모듈로 합동 (Congruence) ⭐⭐⭐ 시험 빈출
정의
두 정수 a와 b가 모듈로 m에 대해 합동(Congruent) 이라는 것은, m으로 나누었을 때 a와 b의 나머지가 동일함을 의미.
표기
a ≡ b (mod m)
동치 조건
a ≡ b (mod m) ⟺ m | (a − b) ⟺ ∃k ∈ ℤ, a = b + km
시계 세계 비유
시계는 12시간마다 한 바퀴를 돈다. 13시 = 1시, 25시 = 1시, 37시 = 1시 → 모두 mod 12에서 같은 그룹.
모듈로 m은 숫자의 세계를 m개의 구역으로 나누고, 같은 구역의 숫자들을 "같다"고 본다.
합동 판별 예시
17 ≡ 5 (mod 6) 인가?
| 17 | 17 = 6×2 + 5 |
| 5 | 5 = 6×0 + 5 |
→ 나머지 같음 → 합동 ✅
17 − 5 = 12, 12 = 6 × 2 → 6 | 12 ✅
→ 합동 성립
모듈로 합동의 연산 성질 ⭐
a ≡ b (mod m), c ≡ d (mod m)일 때:
| 덧셈 허용 | a + c ≡ b + d (mod m) |
| 곱셈 허용 | a · c ≡ b · d (mod m) |
응용 예제
17 ≡ 5 (mod 6), 8 ≡ 2 (mod 6)일 때:
| 17 + 8 = 25 ≡ 5 + 2 = 7 (mod 6) | 25 mod 6 = 1, 7 mod 6 = 1 ✅ |
| 17 × 8 = 136 ≡ 5 × 2 = 10 (mod 6) | 136 mod 6 = 4, 10 mod 6 = 4 ✅ |
💡 암호학 토대: 모듈로 합동의 연산 성질은 RSA 암호화의 핵심이다. (m^e mod n)을 효율적으로 계산할 수 있는 것이 이 성질 덕분이다.
응용 분야
| 해시 함수 | h(key) = key mod m |
| 의사 난수 생성 | x[n+1] = (a · x[n] + c) mod m |
| 암호학 | RSA, Diffie-Hellman |
| 에러 검출 | 체크섬 계산 |
7. 밑수 전개 (Base Expansion) ⭐⭐ 진법의 기초
정의
임의의 양의 정수 n을 1보다 큰 양의 정수 b(밑수)를 사용하여 유일하게 표현하는 방법.
공식
n = aₖbᵏ + aₖ₋₁bᵏ⁻¹ + ... + a₁b¹ + a₀b⁰
여기서 0 ≤ aᵢ < b, aₖ ≠ 0
10진수 분해 예제
165를 밑수 10으로 전개
| 100의 자리 | 1 | 10² = 100 | 100 |
| 10의 자리 | 6 | 10¹ = 10 | 60 |
| 1의 자리 | 5 | 10⁰ = 1 | 5 |
165 = 1·10² + 6·10¹ + 5·10⁰ = (165)₁₀
컴퓨터 세계의 4대 진법 ⭐
| 10진수 | Decimal | 10 | 0~9 | 일상 표준 |
| 2진수 | Binary | 2 | 0, 1 | 컴퓨터 내부 |
| 8진수 | Octal | 8 | 0~7 | 2진수 3자리 묶음 |
| 16진수 | Hexadecimal | 16 | 0~9, A~F | 메모리 주소, 색상 코드 |
진법별 같은 수 표현
10진수 165를 다른 진법으로:
| 10진수 | 165 |
| 2진수 | 10100101 |
| 8진수 | 245 |
| 16진수 | A5 |
💡 컴퓨터 과학 핵심: 컴퓨터는 0과 1만 이해한다 → 모든 데이터는 2진수로 저장. 인간이 보기 편하게 16진수로 표시 (예: HTML 색상 #FF5733).
8. 진법 변환 알고리즘 ⭐⭐⭐ 시험 단골
핵심 절차
10진수 n을 밑수 b의 진법으로 변환:
| 1 | n mod b 계산 → 가장 오른쪽 자릿수 |
| 2 | n := ⌊n/b⌋ 갱신 |
| 3 | n이 0이 될 때까지 1~2 반복 |
| 4 | 나머지를 아래에서 위로 읽기 |
진법 변환 예제 — 10진수 241 → 2진수 ⭐
| 1 | 241 | 1 | 120 |
| 2 | 120 | 0 | 60 |
| 3 | 60 | 0 | 30 |
| 4 | 30 | 0 | 15 |
| 5 | 15 | 1 | 7 |
| 6 | 7 | 1 | 3 |
| 7 | 3 | 1 | 1 |
| 8 | 1 | 1 | 0 (종료) |
결과 도출
나머지를 아래에서 위로 읽기: 1, 1, 1, 1, 0, 0, 0, 1
→ (11110001)₂
검증
1·128 + 1·64 + 1·32 + 1·16 + 0·8 + 0·4 + 0·2 + 1·1 = 128 + 64 + 32 + 16 + 1 = 241 ✅
공식 알고리즘 (의사코드)
procedure base_b_expansion(n: positive integer)
q := n
k := 0
while q ≠ 0
aₖ := q mod b {나머지를 자릿수로 저장}
q := ⌊q/b⌋ {몫으로 갱신}
k := k + 1
return (aₖ ... a₁ a₀)_b💡 시험 단골 패턴: "10진수를 2진수로 변환하시오" 또는 "16진수를 10진수로 변환하시오"가 거의 매번 출제된다. 표를 그려 단계별로 진행하는 것이 가장 안전한 풀이법.
거꾸로 — 다른 진법 → 10진수
(11110001)₂ → 10진수?
각 자릿수에 거듭제곱을 곱해 합산: 1·2⁷ + 1·2⁶ + 1·2⁵ + 1·2⁴ + 0·2³ + 0·2² + 0·2¹ + 1·2⁰ = 241
9. 2진수 덧셈 (Binary Addition) ⭐
핵심 원리
10진수 덧셈과 같지만, 0과 1만 사용하므로 합이 2가 되면 올림(carry) 발생.
비트 덧셈 진리표
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 ← 올림! |
| 1 | 1 | 1 | 1 | 1 ← 올림! |
2진수 덧셈 예제
1011 + 1101 = ?
1 1 1 (carry)
1 0 1 1
+ 1 1 0 1
---------
1 1 0 0 0| 1 (오른쪽) | 1 | 1 | 0 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 | 1 |
| 4 | 1 | 1 | 1 | 1 | 1 |
| 5 | — | — | 1 | 1 | 0 |
→ 결과: 11000
1011₂ = 11, 1101₂ = 13 11 + 13 = 24 = 11000₂ ✅
시간 복잡도
O(n) — n개의 비트에 대해 한 번씩만 순회
💡 컴퓨터 핵심: CPU의 ALU(산술논리연산장치) 가 매초 수십억 번 수행하는 연산이 바로 이 2진수 덧셈이다. 단순해 보이지만 모든 컴퓨터 연산의 기초.
10. 2진수 곱셈 (Binary Multiplication) ⭐
핵심 원리
10진수 곱셈과 유사하지만, 각 비트가 0 또는 1이라 매우 단순:
- 비트가 1이면 → a를 그 자리만큼 왼쪽으로 이동(Shift)
- 비트가 0이면 → 0
- 모든 부분 곱을 더함
핵심 슬로건
2진수 곱셈 = Shift + Add
2진수 곱셈 예제
101 × 110 = ?
| 0 | 0 | — | 0 |
| 1 | 1 | 1010 (101 × 10) | 1010 |
| 2 | 1 | 10100 (101 × 100) | 10100 |
0 1 0 1 0 (j=1)
+ 1 0 1 0 0 (j=2)
-----------
1 1 1 1 0→ 101 × 110 = 11110
101₂ = 5, 110₂ = 6 5 × 6 = 30 = 11110₂ ✅
시간 복잡도
| 기본 곱셈 | O(n²) |
| 카라추바 알고리즘 | O(n^1.585) ⭐ |
💡 고급 알고리즘: 1962년 카라추바(Karatsuba)는 분할 정복으로 n자리 곱셈을 더 빠르게 하는 알고리즘을 발견했다. 큰 수 곱셈에서 표준 알고리즘보다 훨씬 빠르며, 더 발전된 푸리에 변환 기반 알고리즘은 O(n log n)에 도달한다 (2019년 증명).
11. 종합 — 정수론 21강의 거대한 그림
21강 개념 흐름
나누어떨어짐 (a | b)
↓
나눗셈 정리 (a = dq + r)
↓
mod 연산자 (a mod d = r)
↓
모듈로 합동 (a ≡ b mod m)
↓
밑수 전개 (다양한 진법)
↓
진법 변환 알고리즘
↓
2진수 연산 (덧셈, 곱셈)핵심 통찰
정수론은 컴퓨터의 모국어다.
| 데이터 저장 | 2진수 (밑수 전개) |
| 메모리 주소 | 16진수 표기 |
| 해시 테이블 | mod 연산 |
| 암호화 | 모듈로 합동 |
| 산술 연산 | 2진수 덧셈·곱셈 |
📌 한눈에 보는 핵심정리
| 나누어떨어짐 (a | b) | b = ac, 정수 c 존재 |
| 4대 성질 | 0 나누기, 합·곱 법칙, 삼단논법 |
| 나눗셈 정리 | a = dq + r, 0 ≤ r < |d| |
| q와 r 계산 | q = ⌊a/d⌋, r = a − dq |
| mod 연산자 | a mod d = 나머지 r |
| 모듈로 합동 | a ≡ b (mod m) ⟺ m | (a−b) |
| 합동 연산 성질 | 덧셈·곱셈 모두 합동 보존 |
| 밑수 전개 | n = Σ aᵢ · bⁱ |
| 주요 진법 | 2진(컴퓨터), 16진(메모리), 8진, 10진 |
| 진법 변환 | mod와 ⌊÷⌋ 반복, 아래→위로 읽기 |
| 2진수 덧셈 | 비트별 합 + 올림(carry), O(n) |
| 2진수 곱셈 | Shift + Add, O(n²) (기본) |
🧠 예상문제 2제
문제 1. 진법 변환
10진수 53을 2진수로 변환한 결과는?
① 110011 ② 110101 ③ 101101 ④ 100101
👉 정답: ②
| 1 | 53 | 1 | 26 |
| 2 | 26 | 0 | 13 |
| 3 | 13 | 1 | 6 |
| 4 | 6 | 0 | 3 |
| 5 | 3 | 1 | 1 |
| 6 | 1 | 1 | 0 (종료) |
나머지를 아래에서 위로 읽기: 1, 1, 0, 1, 0, 1
→ (110101)₂ ✅
1·32 + 1·16 + 0·8 + 1·4 + 0·2 + 1·1 = 32 + 16 + 4 + 1 = 53 ✅
💡 시험 핵심: 진법 변환은 표 그려서 단계별로 진행하는 것이 가장 안전. 머릿속으로 풀면 무조건 한 단계 빠뜨린다. 나머지를 아래에서 위로 읽는 것도 절대 잊지 말 것.
문제 2. 모듈로 합동 응용
다음 중 a ≡ b (mod 7) 이 성립하는 (a, b) 쌍은?
① (15, 8) ② (20, 6) ③ (35, 14) ④ 모두 성립
👉 정답: ④
15 mod 7 = 1, 8 mod 7 = 1 → 합동 ✅ 또는 15 − 8 = 7, 7 | 7 ✅
20 mod 7 = 6, 6 mod 7 = 6 → 합동 ✅ 또는 20 − 6 = 14, 7 | 14 ✅
35 mod 7 = 0, 14 mod 7 = 0 → 합동 ✅ 또는 35 − 14 = 21, 7 | 21 ✅
→ 모두 mod 7에서 합동 → 정답 ④
💡 추가 학습: 모듈로 합동 판별은 두 가지 방법이 있다.
방법절차
나머지 비교 a mod m과 b mod m이 같은가? 차이의 약수 m이 (a − b)를 나누는가? 시험에서는 두 번째 방법이 빠를 때가 많다. 큰 수의 mod를 직접 계산하지 않고 차이만 보면 된다.
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-22] 소수와 GCD/LCM — 정수의 DNA를 분해하다 (0) | 2026.06.16 |
|---|---|
| [이산구조 특별편 3] 컴퓨터가 풀 수 없는 문제 — P vs NP와 튜링의 정지 문제 (0) | 2026.06.14 |
| [이산구조 개념-20] 알고리즘 복잡도 — 시간·공간·빅 오 표기법 (0) | 2026.06.13 |
| [이산구조 개념-19] 검색·정렬·탐욕 알고리즘 — 5가지 핵심 알고리즘 (0) | 2026.06.12 |
| [이산구조 개념-18] 알고리즘의 기초 — 정의·6대 특징·의사코드 (0) | 2026.06.11 |