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

지금까지는 정수 하나하나의 구조를 분석하거나, 두 정수 사이의 관계를 보는 일이 많았습니다. 그런데 정수론에서는 정수의 성질을 함수처럼 요약해서 보는 방식도 중요합니다. 이런 함수를 산술함수라고 합니다.

What this post covers

산술함수가 무엇인지 설명합니다.
대표적인 예로 $\varphi(n)$ , 약수의 개수 함수, 약수의 합 함수를 소개합니다.
소인수분해가 왜 이런 함수 계산의 핵심인지 정리합니다.
다음 글의 제곱잉여 입문으로 이어집니다.

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

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

산술함수란 무엇인가?

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

예를 들어

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

같은 함수들이 대표적입니다.

즉, 정수 하나를 숫자 하나로 요약하지만, 그 숫자 안에는 꽤 많은 구조 정보가 담깁니다. 이 글에서는 특히 “무엇을 세는 함수인가?”라는 관점으로 보면 이해가 쉬워집니다.

예시 1. 약수의 개수 함수

앞에서 본 것처럼

12 = 2^2 \times 3

이면 약수의 개수는

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

개입니다.

실제로 12의 약수는 1, 2, 3, 4, 6, 12입니다.

즉, $\tau(12)=6$ 입니다.

예시 2. 약수의 합 함수

12의 약수 합은

1+2+3+4+6+12 = 28

입니다. 따라서 $\sigma(12)=28$ 입니다.

약수의 개수뿐 아니라 약수 전체의 합도 정수의 구조를 반영합니다.

예시 3. 오일러 피 함수

앞 글에서 본 것처럼

\varphi(10)=4

입니다. 1, 3, 7, 9가 10과 서로소이기 때문입니다.

이 함수는 모듈러 세계에서 역원이 있는 원소가 몇 개인지와도 연결됩니다.

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

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

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

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

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

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

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

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

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

Common mistakes

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

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

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

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

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

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

Wrap-up

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

다음 글에서는 정수론의 더 깊은 영역으로 들어가는 맛보기로, 합동식 안에서 제곱이 되는 수를 다루는 제곱잉여를 소개하겠습니다.