5.1배수와 약수
정수 b가 정수 a를 나머지 없이 나누면, b는 a의 약수(divisor)이고 a는 b의 배수(multiple)다. 기호로 b | a("b가 a를 나눈다").
큰 수가 어떤 작은 수의 배수인지는 배수 판정법으로 빠르게 알 수 있다. 이 판정법들은 마법이 아니라 진법(자릿값) 구조에서 자연스럽게 나온다.
| 나누는 수 | 판정 방법 | 예 |
|---|---|---|
| 2 | 끝자리가 짝수 | 1374 → 4는 짝수 ✓ |
| 3 | 각 자리 숫자의 합이 3의 배수 | 1374 → 1+3+7+4=15 ✓ |
| 4 | 끝 두 자리가 4의 배수 | 1372 → 72=4·18 ✓ |
| 5 | 끝자리가 0 또는 5 | 1375 → 5 ✓ |
| 9 | 각 자리 숫자의 합이 9의 배수 | 1377 → 1+3+7+7=18 ✓ |
| 11 | 홀수 자리 합 − 짝수 자리 합이 11의 배수 | 1364 → (4+3)−(6+1)=0 ✓ |
5.2진법 — 자릿값의 정체
우리가 쓰는 십진법에서 237은 2·10² + 3·10¹ + 7·10⁰을 뜻한다. 여기서 10을 밑(base)이라 한다. 밑은 10일 필요가 없다 — 컴퓨터는 2를 밑으로 쓴다(이진법).
밑이 b인 진법에서 각 자리는 b⁰, b¹, b², …의 자릿값을 갖고, 각 자리 숫자는 0부터 b−1까지다.
문제. 십진수 45를 이진법으로 나타내라.
풀이. 2로 계속 나누며 나머지를 기록한다. 45 ÷ 2 = 22…나머지 1, 22 ÷ 2 = 11…0, 11 ÷ 2 = 5…1, 5 ÷ 2 = 2…1, 2 ÷ 2 = 1…0, 1 ÷ 2 = 0…1. 나머지를 아래에서 위로 읽으면 101101. 검산: 32 + 8 + 4 + 1 = 45 ✓. ∎
5.3끝자리와 모듈러 산술
모듈러 산술(modular arithmetic)은 "나머지만 가지고 하는 계산"이다. 시계가 12를 넘으면 1로 돌아오듯, 일정한 수를 넘으면 처음으로 순환한다.
a와 b를 m으로 나눈 나머지가 같으면 "a ≡ b (mod m)"라 쓴다. 놀라운 사실은 — 덧셈·뺄셈·곱셈이 나머지끼리 그대로 통한다는 것이다. 거듭제곱의 끝자리, 요일 계산, 거대한 수의 나머지가 모두 여기서 풀린다.
a + c ≡ b + d , a · c ≡ b · d (mod m)
문제. 7¹⁰⁰의 일의 자리 숫자를 구하라.
풀이. 일의 자리는 곧 "mod 10에서의 값"이다. 7의 거듭제곱의 끝자리를 보자: 7¹→7, 7²→9, 7³→3, 7⁴→1, 그다음 7⁵→7… 주기 4로 순환한다(7, 9, 3, 1). 지수 100을 4로 나눈 나머지는 0 — 즉 주기의 마지막 자리에 해당한다. 따라서 끝자리는 1. ∎
5.4소수와 소인수분해
소수(prime)는 1과 자기 자신 외에 약수가 없는, 1보다 큰 정수다. 2, 3, 5, 7, 11, 13, … 소수가 아닌 1보다 큰 정수는 합성수(composite)다. (1은 소수도 합성수도 아니다.)
소수가 중요한 이유는 산술의 기본정리(Fundamental Theorem of Arithmetic)에 있다 — 1보다 큰 모든 정수는 소수들의 곱으로, 순서를 무시하면 오직 한 가지 방법으로 분해된다. 소수는 정수를 짓는 벽돌이다.
약수의 개수 = (a₁+1)(a₂+1)…(aₖ+1)
문제. 72의 양의 약수는 모두 몇 개인가?
풀이. 먼저 소인수분해한다: 72 = 8 × 9 = 2³ × 3². 약수 하나를 만들려면 2를 0~3번(4가지), 3을 0~2번(3가지) 골라 곱하면 된다. 곱의 법칙으로 약수의 개수는 (3+1)(2+1) = 4 × 3 = 12개. 약수를 일일이 적지 않고도 셀 수 있다. ∎
5.5최대공약수와 최소공배수
두 수의 최대공약수(GCD)는 둘 다 나누는 가장 큰 수, 최소공배수(LCM)는 둘의 공통 배수 중 가장 작은 수다. 소인수분해를 알면 둘 다 즉시 구한다 — GCD는 공통 소인수의 작은 지수, LCM은 모든 소인수의 큰 지수를 취한다.
문제. 48과 60의 최대공약수와 최소공배수를 구하라.
풀이. 소인수분해: 48 = 2⁴·3, 60 = 2²·3·5. GCD는 공통 소인수를 작은 지수로: 2² · 3 = 12. LCM은 등장하는 모든 소인수를 큰 지수로: 2⁴ · 3 · 5 = 240. 검산: 12 × 240 = 2880 = 48 × 60 ✓. ∎
5.6예제 모음 — 경시 문제 맛보기
문제. 어떤 수를 5로 나누면 3이 남고, 7로 나누면 4가 남는다. 이런 수 중 가장 작은 양의 정수는?
풀이. 5로 나눠 3 남는 수: 3, 8, 13, 18, 23, 28, …. 이 중 7로 나눠 4 남는 것을 찾는다. 3→3, 8→1, 13→6, 18→4 ✓. 답은 18. 검산: 18 = 5·3+3 = 7·2+4. (다음 해는 35씩 커진다 — 35는 lcm(5,7)이다.) ∎
문제. 2³ · 3⁵ · 5² · n이 완전제곱수가 되게 하는 가장 작은 양의 정수 n은?
풀이. 완전제곱수는 모든 소인수의 지수가 짝수다. 현재 지수는 2의 3(홀수), 3의 5(홀수), 5의 2(짝수). 홀수 지수를 짝수로 만들려면 2와 3을 각각 한 번씩 더 곱해야 한다. 따라서 n = 2 · 3 = 6. 그러면 2⁴·3⁶·5²로 모든 지수가 짝수. ∎