| [ QuizWit ] in KIDS 글 쓴 이(By): guest (earny) 날 짜 (Date): 1996년02월05일(월) 20시41분22초 KST 제 목(Title): [Re]최대 공약수의 합. 95KMO 4번 문제는 n=pq (p,q는 소수)일때 그 등식을 증명하라는 것이었죠. 그러나 n이 임의의 자연수일 때 그 등식은 성립하더군요. f(n)=\sum{k=1} \gcd{k,n)^2 g(n)=\sum{s=1}^n\sum_{t=1}^n \gcd{s,t,n} 으로 놓고 두 함수가 같은 함수임을 보이면 위의 문제는 증명되죠. 저는 일단 두 함수가 승법적 함수라는 걸 보이고 그 다음에 n=p^k에 대해서 두 함수가 같다는 것을 보여 결국 두 함수가 완전히 같은 함수임을 보였어요. 어떤 함수가 승법적 함수라는 것은 a,b가 서로소이면 f(ab)=f(a)f(b)이고, f(1)=1인 함수를 말하죠. 따라서 승법적 함수의 경우 임의의 자연수를 다음과 같은 형태로 나타내었을때� n=p_1^r_1 p_2^r_2 ... p_k^r_k f(n)=f(p_1^r_1)f(p_2^r_2)...f(p_k^r_k)되죠. 따라서 승법적 함수인 두 함수가 같은 함수라는 것을 보일때 n=p^k에 대해서만 같다는 것을 보이면 증명이 끝나죠. 이제 문제로 처음 문제로 돌아가서 f(n) 과 g(n)을 다음과 같은 형태로 바꿀수가 있죠. (단, \varphi 는 오일러 함수를 말합니다.) f(n)= \sum_{k=1}^n \gcd(k,n)^2 =\sum_{d|n} \varphi(n/d)*d^2 g(n)= \sum_{s=1}^n\sum_{t=1}^n \gcd(s,t,n) = \sum_{s=1}^n\sum_{t=1}^n \gcd(s,\gcd(t,n)) = \sum_{s=1}^n\sum_{d|n} \varphi(n/d)\gcd(s,d) = \sum_{d|n}\sum_{s=1}^n \varphi(n/d)\gcd(s,d) = \sum_{d|n}\varphi(n/d) \sum_{s=1}^n\gcd(s,d) = \sum_{d|n}\varphi(n/d) n/d \sum_{s=1}^d\gcd(s,d) = \sum_{d|n}\varphi(n/d) n/d \sum_{s|d} \varphi(d/s)*s 이렇게 고치고 나면 두함수가 승법적이라는 걸 보일수 있죠. n=ab (a,b는 서로소) d|n 인 d는 항상 a의 약수와 b의 약수의 곱으로 표현할 수 있죠. 즉 d=d_a*d_b (d_a|a, d_b|b) 이것을 이용하여 승법적이라는 것을 보일것입니다. f(ab)=\sum_{d|ab} \varphi(ab/d)*d^2 =\sum_{d_a*d_b|ab} \varphi(ab/(d_a*d_b)) (d_a)^2 (d_b)^2 =\sum_{d_a|a}\sum_{d_b|b} \varphi(a/d_a)\varphi(b/d_b) (d_a)^2 (d_b)^2 =\sum_{d_a|a}\varphi(a/d_a) (d_a)^2 \sum_{d_b|b} \varphi(b/d_b) (d_b)^2 =\sum_{d|a}\varphi(a/d) d^2 \sum_{d|b} \varphi(b/d) d^2 =\sum_{d|a}\varphi(a/d) d^2 * \sum_{d|b} \varphi(b/d) d^2 =f(a)f(b) g(ab)=\sum_{d|ab}\varphi(ab/d) ab/d \sum_{s|d} \varphi (d/s) s =\sum_{d_a*d_b|ab}\varphi(ab / d_a d_b) ab/d_a*d_b \sum_{s_a*s_b|d_a*d_b} \varphi((d_a d_b)/(s_a s_b)) s_a s_b =\sum_{d_a|a}\sum_{d_b|b} \varphi(a/d_a)\varphi(b/d_b) a/d_a b/d_b \sum_{s_a|d_a}\sum_{s_b|d_b} \varphi(d_a/s_a)\varphi(d_b/s_b)s_a s_b =\sum_{d_a|a}\sum_{d_b|b} \varphi(a/d_a)\varphi(b/d_b) a/d_a b/d_b \sum_{s_a|d_a}\varphi(d_a/s_a)s_a \sum_{s_b|d_b}\varphi(d_b/s_b)s_b =\sum_{d_a|a}\sum_{d_b|b} \varphi(a/d_a)\varphi(b/d_b) a/d_a b/d_b \sum_{s_a|d_a}\varphi(d_a/s_a)s_a * \sum_{s_b|d_b}\varphi(d_b/s_b)s_b =\sum_{d_a|a}\varphi(a/d_a)a/d_a\sum_{s_a|d_a}\varphi(d_a/s_a)s_a * \sum_{d_b|b}\varphi(b/d_b)b/d_b\sum_{s_b|d_b}\varphi(d_b/s_b)s_b =\sum_{d|a}\varphi(a/d)a/d\sum_{s|d}\varphi(d/s)s * \sum_{d|b}\varphi(b/d)b/d\sum_{s|d}\varphi(d/s)s =g(a)g(b) 따라서 두 함수 모두 승법적이라는 것을 보였다. 이제 n=p^k 일 때 두 함수의 값이 같다는 것만 보이면 되는데 n=p^k인 경우 직접 계산이 가능 하므로 계산해보면 f(p^k)=p^{2k}+p^{2k-1}-p^{k-1} g(p^k)=p^{2k}+p^{2k-1}-p^{k-1} 으로 똑같이 나오므로 위의 두 함수는 같은 함수이다. 위에서 f(p^k)을 구하는 것은 간단한데 g(p^k)을 구하는 과정은 상당히 복잡했음. 하지만 연습장 4장에 걸치는 노가다 계산으로 확실히 위와 같이 나오는 것을 확인 했음. 따라서 일반적으로 위의 함수 값을 구할 수 있음. |