정수의 소인수분해는 약수의 개수와 합뿐 아니라 정수 위에 정의된 여러 함수의 구조를 결정한다. 이러한 함수를 number-theoretic function 또는 arithmetic function이라고 한다. 이 글에서는 약수 함수에서 출발하여 곱셈적 함수와 Möbius inversion을 정리한다.
Divisor-Counting Function
라 하자. 모든 양의 약수는
로 유일하게 표현된다. 각 지수 에는 개의 선택이 있으므로 약수의 개수는
이다.
이 홀수인 경우는 각 가 모두 짝수일 때뿐이다. 따라서
이다. 이는 약수를 와 로 짝지을 때도 확인할 수 있다.
Sum-of-Divisors Function
약수의 합은 각 소수 지수의 선택을 독립적으로 전개하여 계산한다.
예를 들어 이므로
이고
이다.
모든 약수의 곱
약수 와 를 짝지으면 각 쌍의 곱은 이다. 따라서
이다. 이 홀수인 완전제곱수에서도 가운데 약수 을 포함하면 같은 식이 성립한다.
Multiplicative Function
산술함수 가 일 때
을 만족하면 multiplicative라고 한다. 모든 에 대해 성립할 필요는 없다. 인 곱셈적 함수는 반드시 이다.
서로소인 의 약수는 , 의 곱 로 유일하게 나타나므로 와 는 모두 multiplicative이다.
더 일반적으로 가 multiplicative이면
도 multiplicative이다. 서로소인 에 대해 약수의 일대일 대응을 사용하면
을 얻는다.
Möbius Function
Möbius 함수 는 다음과 같이 정의된다.
즉 square-free 정수에서는 소인수 개수의 parity를 기록하고, 제곱 인수를 가지면 0이다. 정의와 서로소인 소인수분해를 사용하면 가 multiplicative임을 알 수 있다.
가장 중요한 항등식은
이다. 의 서로 다른 소인수가 개라면 0이 아닌 항은 그 소수들의 부분집합에 대응하고,
이다.
Möbius Inversion Formula
두 산술함수 가
를 만족하면
이다.
증명
오른쪽을 전개하면
안쪽 합은 , 즉 일 때만 1이고 나머지는 0이다. 따라서 전체 합은 만 남는다.
Möbius inversion은 “모든 약수에 대한 누적합”에서 원래 함수를 되찾는 장치이다.
Floor Function과 -Adic Valuation
은 인 가장 큰 이다. Factorial에서는 의 배수, 의 배수, 그 이상의 배수가 추가로 를 제공한다.
Legendre’s Formula
합은 이후 모두 0이므로 유한하다. 예를 들어
이다.
이 공식으로
임을 확인하면 이항계수가 정수라는 사실을 소인수 지수 관점에서 볼 수 있다.
약수합의 순서 교환
이면
이다. 왼쪽에서 는 의 배수 마다 한 번씩 등장하므로 정확히 번 세어진다.
정리
소인수분해는 와 의 곱 공식을 제공한다. 곱셈적 함수는 서로소인 정수의 구조를 분리하며, Möbius 함수는 약수 누적합을 역변환한다. Legendre’s Formula는 factorial에 포함된 소수의 지수를 floor 함수의 합으로 계산한다.
연습 문제
- 에 대해 과 을 구한다.
- 를 직접 계산한다.
- 을 구한다.
풀이
1번
이고
이다.
2번
30의 약수 중 square-free인 수는 모두이며
이다. 이는 인 일반 항등식과 일치한다.
3번
이다.