[정수론 입문 시리즈 18편] 산술함수는 정수의 성질을 어떻게 숫자로 요약할까?

12라는 숫자의 프로필을 만들어 봅시다. 약수는 6개, 약수의 합은 28, 12보다 작거나 같은 수 중 12와 서로소인 수는 4개입니다. 이렇게 숫자 하나를 여러 관점에서 요약하면, 마치 프로그램에서 객체의 속성을 뽑아 보는 것처럼 정수의 특징이 한눈에 보입니다.

정수론에서는 이런 요약 도구를 산술함수라고 합니다. 어려운 이름처럼 보이지만, 핵심은 정수를 입력하면 그 정수의 특징을 숫자로 돌려주는 함수입니다.

What this post covers

• 산술함수가 무엇인지 설명합니다.
• 대표적인 예로 $\varphi(n)$, 약수의 개수 함수, 약수의 합 함수를 소개합니다.
• 소인수분해가 왜 이런 함수 계산의 핵심인지 정리합니다.
• 다음 글의 연속제곱법과 빠른 모듈러 거듭제곱으로 이어집니다.

이번 글에서 새로 나오는 용어

• 산술함수 (Arithmetic Function): 자연수에 대해 어떤 정수론적 정보를 대응시키는 함수입니다.
• 오일러 피 함수 (Euler Totient Function): $n$과 서로소인 수의 개수입니다.
• 약수 (Divisor): 어떤 수를 나누어떨어지게 하는 수입니다.
• 소인수분해 (Prime Factorization): 정수를 소수의 곱으로 나타내는 것입니다.

먼저 실험부터: 숫자 프로필 만들기

공식부터 외우기보다 작은 수의 프로필을 직접 만들어 보겠습니다. 아래 실험을 하고 나면, 산술함수는 단순히 그 결과를 함수 기호로 이름 붙인 것이라는 점이 보입니다.

실험 1. 12의 약수 함수

계산할 대상	손계산
약수	1, 2, 3, 4, 6, 12
약수의 개수	6개
약수의 합	1+2+3+4+6+12 = 28

따라서

$$\tau(12)=6, \qquad \sigma(12)=28$$

입니다.

실험 2. 18의 약수 함수

$$18 = 2 \times 3^2$$

18의 약수를 직접 나열하면

$$1, 2, 3, 6, 9, 18$$

이므로

$$\tau(18)=6, \qquad \sigma(18)=39$$

입니다.

실험 3. 서로소인 수 세기

$1$부터 $12$까지에서 12와 서로소인 수를 찾아 봅시다.

수	12와 서로소인가?
1	예
2	아니오
3	아니오
4	아니오
5	예
6	아니오
7	예
8	아니오
9	아니오
10	아니오
11	예
12	아니오

따라서

$$\varphi(12)=4$$

입니다.

산술함수란 무엇인가?

산술함수는 자연수 $n$을 입력받아 그 수의 정수론적 성질을 나타내는 값을 내놓는 함수입니다.

예를 들어

• $\varphi(n)$: $n$과 서로소인 수의 개수
• $\tau(n)$: 약수의 개수 함수
• $\sigma(n)$: 약수의 합 함수

같은 함수들이 대표적입니다. 즉, 정수 하나를 숫자 하나로 요약하지만, 그 숫자 안에는 꽤 많은 구조 정보가 담깁니다.

산술함수란 무엇인가?

산술함수는 자연수 $n$을 입력받아 그 수의 정수론적 성질을 나타내는 값을 내놓는 함수입니다.

예를 들어

• $\varphi(n)$: $n$과 서로소인 수의 개수
• $\tau(n)$: 약수의 개수 함수
• $\sigma(n)$: 약수의 합 함수

같은 함수들이 대표적입니다. 즉, 정수 하나를 숫자 하나로 요약하지만, 그 숫자 안에는 꽤 많은 구조 정보가 담깁니다.

패턴 발견

위 계산에서 어떤 패턴이 보이나요?

• 약수의 개수 $\tau(n)$는 약수를 “몇 개 만들 수 있는가”를 셉니다.
• 약수의 합 $\sigma(n)$는 만들어진 약수들을 모두 더합니다.
• 오일러 피 함수 $\varphi(n)$는 $n$과 공통 약수가 1뿐인 수를 셉니다.

겉보기에는 서로 다른 계산처럼 보이지만, 세 함수 모두 결국 $n$의 소인수분해 구조를 읽고 있습니다.

예를 들어

$$12 = 2^2 \times 3$$

에서 약수는 $2$를 $0,1,2$번 고르고, $3$을 $0,1$번 고르는 방식으로 만들어집니다. 그래서 약수 개수는

$$(2+1)(1+1)=6$$

이 됩니다. 핵심 패턴은 소수의 지수가 선택의 개수를 결정한다는 점입니다.

왜 소인수분해가 중요할까?

이 함수들은 겉으로는 서로 달라 보여도, 실제 계산은 대부분 소인수분해에 기대고 있습니다.

정수를 소수의 거듭제곱 꼴로 분해하면

• 약수를 몇 개 만들 수 있는지
• 약수의 합이 어떻게 쌓이는지
• 서로소인 수가 몇 개인지

를 체계적으로 계산할 수 있습니다.

즉, 소인수분해는 산술함수의 공통 기반입니다.

왜 이런 함수 관점이 필요할까?

앞부분의 정수론이 “한 문제를 푸는 도구”였다면, 산술함수는 “많은 정수를 한 방식으로 비교하는 도구”에 가깝습니다.

예를 들어 어떤 수는 약수가 많고, 어떤 수는 적습니다. 어떤 수는 서로소인 수가 상대적으로 많고, 어떤 수는 적습니다. 이런 차이를 함수값으로 요약하면 정수의 전반적인 패턴을 더 잘 볼 수 있습니다.

이론 정리

산술함수의 기본 계산

$n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$라면

$$\tau(n)=(a_1+1)(a_2+1)\cdots(a_k+1)$$

입니다. 또한

$$\sigma(p^a)=1+p+p^2+\cdots+p^a$$

이고, 서로 다른 소수 거듭제곱 부분의 약수 합은 곱으로 결합됩니다.

오일러 피 함수는

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$$

로 계산할 수 있습니다.

이 공식들은 단순한 암기 대상이 아니라, 손으로 약수를 만들고 서로소인 수를 세어 본 패턴을 압축한 결과입니다.

Python으로 확인하기

아래 코드는 작은 수에 대해 $\tau(n)$, $\sigma(n)$, $\varphi(n)$를 직접 세어서 확인합니다.

from math import gcd

def divisors(n):
    result = []
    for d in range(1, n + 1):
        if n % d == 0:
            result.append(d)
    return result

def tau(n):
    return len(divisors(n))

def sigma(n):
    return sum(divisors(n))

def phi(n):
    count = 0
    for a in range(1, n + 1):
        if gcd(a, n) == 1:
            count += 1
    return count

for n in [10, 12, 18]:
    print(n, "약수", divisors(n))
    print("tau =", tau(n), "sigma =", sigma(n), "phi =", phi(n))

실행하면 손으로 계산한 $\tau(12)=6$, $\sigma(12)=28$, $\varphi(12)=4$가 그대로 확인됩니다.

Common mistakes

1. 함수 기호만 외우고 무엇을 세는지 놓치는 실수

$\varphi, \tau, \sigma$는 각각 무엇을 세는지가 핵심입니다.

2. 산술함수를 완전히 독립된 주제로 생각하는 실수

실제로는 약수, 소인수분해, 서로소 같은 앞선 개념과 모두 연결되어 있습니다.

3. 계산을 전부 직접 세려고 하는 실수

작은 수에서는 가능하지만, 구조를 이해하면 소인수분해만으로 훨씬 체계적으로 계산할 수 있습니다.

Silverman 교재 연결

이 글은 Silverman 《친절한 수론 길라잡이》(경문사)의 다음 내용과 연결됩니다.

• 11장: 오일러 φ 함수와 중국인의 나머지 정리 - 오일러 $\varphi$ 함수는 산술함수 관점에서 법 $n$과 서로소인 잉여류의 개수를 세는 대표적인 예입니다.
• 14장: 산술함수 관련 내용 - 약수의 개수 $\tau(n)$, 약수의 합 $\sigma(n)$, 뫼비우스 함수처럼 정수의 약수 구조를 함수로 기록하는 관점과 연결됩니다.
• 관련 정리/예제: $\varphi$, $\tau$, $\sigma$는 모두 소인수분해와 약수 구조를 이용해 계산할 수 있다는 점이 핵심입니다.

연습 문제

아래 점검 퀴즈에서 학습한 내용을 확인해 보세요.

Wrap-up

이번 글에서는 산술함수라는 틀 안에서 오일러 피 함수, 약수의 개수 함수, 약수의 합 함수를 간단히 살펴봤습니다. 이 함수들은 정수의 성질을 숫자로 요약해 주는 도구입니다.

다음 글에서는 큰 거듭제곱을 법 $m$에 대해 빠르게 계산하는 연속제곱법을 소개하겠습니다.