나무모에 미러 (일반/밝은 화면)
최근 수정 시각 : 2025-01-23 20:49:58

약수 함수


정수론
Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"		 공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수·배수 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 과일 분수방정식 문제 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
모듈러 역원 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론(국소체) · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

1. 개요2. 성질3. 활용

1. 개요

約數 函數 / Divisor function

특수함수의 하나로, 정의는 다음과 같다.

[math(\displaystyle \sigma_s(n) \equiv \sum_{d|n} d^{s}\quad)](단, [math(d)]는 [math(n)]의 약수, [math(s \in \mathbb{C},\,n \in \mathbb{N})])

즉, 자연수인 n의 약수를 [math(s)]제곱한 것을 모두 더한 것을 함숫값으로 내놓는 함수이다.

다만 s 값에 따라 약수 함수의 이름이 달라진다.
[math(\displaystyle \sum_{n\le x} d(n)=x \log x+(2\gamma-1)x+O(\sqrt{x}))]


[math(s)]에 복소수가 들어갈 수 있기 때문에, 복소수 [math(s)]에 대해서는 정의가 다음과 같이 바뀐다.

[math(\displaystyle \sigma_s(n) \equiv \sum_{d|n} d^{\Re(s)}\, ({\rm cis} \circ \ln)( d \, \Im(s)))]

[math({\rm cis})]는 허수지수함수, [math(\ln)]은 자연로그, [math(\Re, \Im)]는 각각 복소수의 실수부와 허수부를 뜻한다.

2. 성질

(1) [math(\sigma_1(n) = n+1)]이면 [math(n)]은 소수이다.
{{{#!folding [증명]
모든 수 [math(n)]은 [math(1)]과 [math(n)]을 약수로 가진다. 그럼 [math(\sigma_1(n)=1+n)]+(나머지 약수의 합)이다. 여기서 [math(\sigma_1(n) = n+1)]이므로 나머지 약수의 합이 0이기 때문에 [math(n)]의 약수는 [math(1)]과 [math(n)]뿐이다. 따라서 [math(n)]은 소수이다.
}}}
(2) [math(gcd(m, n) = 1)]이면 [math(\sigma_s(mn))]=[math(\sigma_s(m)\sigma_s(n))]이다
{{{#!folding [증명]
[math(m)]와 [math(n)]가 서로소일 때, [math(mn)]의 약수는 [math(m)]의 약수와 [math(n)]의 약수를 곱한 형태로 나타낼 수 있다.
즉, [math(mn)]의 약수 = {[math(d₁⋅d₂)] | [math(d₁)]은 [math(m)]의 약수, [math(d₂)]는 [math(n)]의 약수}이다.

[math(mn)]의 모든 약수들의 합은 [math(m)]의 약수들의 합과 [math(n)]의 약수들의 합의 곱으로 표현된다.
𝜎(mn) = ∑(d₁가 m의 약수) ∑(d₂가 n의 약수) (d₁⋅d₂).

이 식은 두 개의 독립적인 합으로 분리할 수 있다:
𝜎(mn) = (∑(d₁가 m의 약수) d₁) ⋅ (∑(d₂가 n의 약수) d₂).

여기서 ∑(d₁가 m의 약수) d₁ = 𝜎(m), ∑(d₂가 n의 약수) d₂ = 𝜎(n)이므로,
𝜎(mn) = 𝜎(m) ⋅ 𝜎(n).
}}}
(3) [math({\displaystyle d(p^k)=k+1})]
{{{#!folding [증명]
[math(p^k)]의 약수는 [math(1+p+p^2+.....+p^k)]이다. 이것들은 [math(k+1)]개이므로 [math({\displaystyle d(p^k)=k+1})]이다.
}}}
(4) [math(\sigma_1(p^k) = \frac{p^{k+1}-1}{p-1})]
{{{#!folding [증명]
[math(\sigma_1(p^k) = 1+p+p^2+.....+p^k = \frac{p^(k+1)-1}{p-1})]
}}}
(5) [math({\displaystyle \sigma_s(p^k) = \frac{p^{s(k+1)}-1}{p^s-1}})]
[증명]
[math({\displaystyle \sigma_s(p^k) = 1^s+p^s+p^{2s}+.....+p^{ks} = \frac{p^{s(k+1)}-1}{p^s-1}})]

3. 활용

가장 많이 쓰이는 용도는 완전수/부족수/과잉수 판별로, 이들은 진약수의 합이 어떤가에 따라 집합이 갈리기 때문이다.

덤으로 이를 이용해 소수를 정의하면 1이 소수가 아니라고 깔끔하게 정의된다.

이외에도 암호학에서 RSA 알고리즘의 소수 판별, 디리클레 급수와 같은 해석적 수론 문제에서 약수 함수가 활용된다.
[1] n번째 오각수의 일반항 [math(\frac{n(3n-1)}{2})]의 n자리에 정수를 넣은 것

분류