| [ QuizWit ] in KIDS 글 쓴 이(By): guest ( ) 날 짜 (Date): 1996년02월12일(월) 20시19분53초 KST 제 목(Title): [Re] 최대 공약수의 합 \sum_{s,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(d) gcd(s, n/d) = \sum_{d|n} \varphi(d) \sum_{s=1}^n gcd(s, n/d) = \sum_{d|n} \varphi(d) d \sum_{c|n/d} \varphi(c) n/cd = \sum_{d|n} \varphi(d) \sum_{c|n/d} \varphi(c) n/c = \sum_{c|n} \varphi(c) n/c \sum_{d|n/c} \varphi(d) = \sum_{c|n} \varphi(c) (n/c)^2 = \sum_{k=1}^n gcd(k,n)^2 Q.E.D In general, \sum_{k=1}^n gcd(k,n)^m = \sum_{s_1,...,s_m=1}^n gcd(s_1,...,s_m,n). |