[정수론](18)[약수들의 ϕ의 합]

F(n): n의 모든 양의 약수의 ϕ값의 합
예) F(6) = ϕ(1) + ϕ(2) + ϕ(3) + ϕ(6) = 1+1+2+2 = 6

 

F(n)의 성질

 

곱셈적 함수 성질

gcd(m ,n) = 1 이라먄 F(mn) = F(m)F(n)이다.
증명
    n의 양의 약수를 d1, d2, ..., dr
    m의 양의 약수를 e1, e2, ..., es라 하자.
    mn의 약수는 d, e를 조합한 것과 같다.
    따라서 F(mn) = ϕ(d1e1) + ϕ(d1e2) + ... + ϕ(dres)
    이때, gcd(m, n) = 1 이므로, 모든 d, e에 대해 gcd(d, e) = 1이다.
    따라서 ϕ(de) = ϕ(d)ϕ(e) 이다. (합성수라도 쪼개서 계산하면 됨.)
    F(mn) = ϕ(d1)ϕ(e1) + ϕ(d1)ϕ(e2) + ... + ϕ(dr)ϕ(es)
    = {ϕ(d1) + ϕ(d2) + ... + ϕ(dr)} * {ϕ(e1) + ϕ(e2) + ... + ϕ(es)}
    = F(m)F(n)

 

F(n) = n

증명

• n = 소수 p
  p의 약수는 1, p이다
  따라서 F(p) = ϕ(1) + ϕ(p) = 1 + (p-1) = p
  따라서 성립
• n = p^k
  p^k의 약수는 1, p, p^2, ..., p^k이다.
  따라서 F(p^k) = ϕ(1) + ϕ(p) + ... + ϕ(p^k)= 1 + (p-1) + ... + (p^k - p^(k-1)) = p^k
  여기도 성립!
• n = p^k*q^r (p, q = 소수)
  곱셈적 함수이므로, F(p^k*q^r) = F(p^k)F(q^r)
  = p^k * q^r이다.
  따라서 성립!!!