Homework 3

算数函数代写 You’ve already seen ϕ(n), the number of integers between 1 and n coprime to n. Here are three other “arithmetic” functions:

1 Arithmetic Functions – Basics

You’ve already seen ϕ(n), the number of integers between 1 and n coprime to n. Here are three other “arithmetic” functions:

σ(n), the sum of all the positive divisors of n (including n itself), 算数函数代写

τ (n), the number of positive divisors of n, and

µ(n), which is 0 if n is divisible by a square other than 1 and µ(n) = (1)k if n = p1p2 · · · pk, the product of k distinct primes.

An arithmetic function f : N C is called multiplicative if f(ab) = f(a)f(b) for all a and b that are relatively prime. It is called totally multiplicative if f(ab) = f(a)f(b) for all a and b.

Problem 1. 算数函数代写

(a) Come up with (and prove!) a closed formula for σ(n) and τ (n) in terms of the prime factorization of n (similar to, if

(b) Show that σ(n)ϕ(n) < n2 for n 2.1

算数函数代写
算数函数代写

(c) Show that all of ϕ, σ, τ , and µ are multiplicative. Which ones are totally multiplicative?

Problem 2. If f and g are arithmetic functions, defifine

(a) Show that f g = g f and (f g) h = f (g h). 算数函数代写

(b) Find an arithmetic function id such that id f = f for all f.

(c) When can you fifind “-inverses (i.e. f and g are -inverses iffff f g = id)?