multiplicative function

마지막 수정 시각: 2020-10-26 22:03:12

수학에서 하도 자주 얻어맞아서, 이제 두드려 맞을 때마다 어디서 머리가 깨졌는지 적어놓기로 했다.

오늘은 Bash Plays with Functions 이 문제를 풀다 막혔는데, 어느 정도 성질을 찾은 다음 그걸로 최적화하려고 한참 애쓰다 실패했다.

그리고 힌트를 좀 얻고 싶어서 breakun님에게 수학 찬스를 쓴 결과.. 어느 정도의 사전 지식이 필요하다는 것을 알게 됐다. 이 문제를 해결하기 위해 필요했던 multiplicative function에 관한 성질을 아래에 정리해둔다.

정의

어떤 양의 정수 \(n\) 에 대해, \(ab = n, gcd(a, b) =1\) 이라고 하자. 이런 모든 \(a, b\)에 대해 \(f(n) = f(a)f(b)\) 가 성립할 경우 함수 \(f\)를 multiplicative function이라고 부른다.

성질

위 문제에서 \(f_0(n)\) 이 multiplicative function임은 쉽게 증명할 수 있다. 어떤 수 \(n\)의 소인수가 \(k\)개인 경우 \(f_0(n) = 2^k\)이기 때문에 자연스럽게 성립한다.

또, \(f_r(n) = \sum_{d \mid n} f_{r-1}(d)\)가 성립한다. 즉, \(f_r(n)\)은 자신의 모든 약수에 대해 \(f_{r-1}\) 을 적용한 것을 모두 더한 것과 같다. 이건 주어진 식을 전개해보면 쉽게 알 수 있는 사실이다.

여기까지 전개하고 나면, multiplicative function의 성질을 이용해야 한다. multiplicative function \(f\)에 대해, 함수 \(g\)를 다음과 같이 정의하자.

\[ g(n) = \sum_{d \mid n} f(d) \]

이 경우, 함수 \(g\) 역시도 multiplicative function이 된다. 간단하지만 아주 강력한 성질이다. 이 성질을 응용하면 \(f_0(n), f_1(n), f_2(n), \cdots, f_r(n)\)이 연쇄적으로 전부 multiplicative function이 되므로 해당 성질을 이용해 최적화해서 문제를 해결할 수 있게 된다. 이런 성질이 성립한다는 것만 알게 되면 원 문제를 해결하는 것 자체는 별로 어렵지 않으므로 생략.

그러면, 이제 왜 저런 성질이 성립하는지 한 번 증명해보자.

증명

multiplicative function \(f\)에 대해 함수 \(g\)를 \(g(n) = \sum_{d \mid n} f(d)\)과 같이 정의했다고 하자.

\[ g(n) = \sum_{d \mid n} f(d) \]

\(ab = n, gcd(a, b) = 1\) 이라고 하자. 이 경우, 위 식은 아래와 같이 쓸 수 있다.

\[ g(n) = \sum_{d \mid ab} f(d) \]

여기서, \(x \mid a, y \mid b\) 인 \(x\)와 \(y\)를 생각해보자. 각각 \(a\), \(b\)의 약수이고 \(gcd(a,b) = 1\)이므로 \(gcd(x,y) =1\)이다. 이 때, 위 식을 아래와 같이 바꿀 수 있다.

\[ g(n) = \sum_{x \mid a, y \mid b} f(xy) \]

\(ab\)의 약수는 임의의 \(a\)의 약수와 \(b\)의 약수를 곱한 것으로 표현되어야하기 때문이다. 여기서 \(f\)가 multiplicative function 이라는 것과, \(gcd(x, y) = 1\)이라는 성질을 이용해 \(f(xy) = f(x)f(y)\)로 풀어쓸 수 있다.

\[ g(n) = \sum_{x \mid a, y \mid b} f(x)f(y) \]

이제 \(x\)와 \(y\)가 독립적이므로,

\[ g(n) = \sum_{x \mid a} f(x) \cdot \sum_{y \mid b} f(y) \]

왼쪽 오른쪽이 각각 \(g\)의 정의와 일치하므로,

\[ g(n) = g(a)g(b) \]

따라서, 함수 \(g\) 역시도 multiplicative function이 됨을 알 수 있다.

응용

정수론 문제에서 어떤 함수가 주어져있을 때, 접근이 막막하면 위 성질이 성립하는지 한 번 시도해보는 것은 좋은 방법일 것 같다. 일단 오일러 피 함수, 약수의 k제곱의 합 등의 함수도 모두 multiplicative function의 성질을 만족한다고 한다. 뭔가 이게 성립하는 함수가 생각보다 많은 듯.

이 성질 자체가 그냥 웰노운인 것 같은데 나는 이걸 이 문제를 풀면서 오늘 처음 알았다(...) 수학 관련한 지식은 다들 어디서 배우는걸까? 흑흑