Reference no: EM132852446

Problem 1. Let σ_k(n) = Σ_{d|n, d≥1} d^k denote the k-th divisor sum function and let Φ denote the Euler phi (totient) function. Compute σ₀(84), σ₁ (2310), σ₂(2401), Φ(127), Φ(210), σ_-1(40)

Problem 2. Let f and g be multiplicative functions. Which of the following functions are multiplicative. Justify.
(1) f +g
(2) gf
(3) Σ_{d|n, d≥1} f(d)g(n/d)

Problem 3. In each case, find a function f such that F(n) = Σ_{d|n, d≥1} f (d)
(1) F(n) = (μ(n))²
(2) F(n) = n²
(3) F(n) = n
(4) F(n) = {1 n = m² where in is some integer.
                0 otherwise,

Problem 4. (1) Prove that if σ₀(n) is prime, then n is a prime power.
(2) Prove that σ₀(σ₀(n)) = 2 if and only if n = p^q-1 where p and q are prime.

Problem 5. Let n be an integer n ≥ 1.

(1) Let n = 21 compare the sets {d| d|n, d ≥ 1} and { n/d| d|n, d≥1}.
(2) Prove that if d runs over all positive divisors of n so does n/d.
(3) Show that nσ_-1(n) = σ₁(n) for all n ≥ 1.
(4) Prove that n is perfect if and only if σ_-1(n) = 2.

Problem 6. Let F(n) =  Σ_{d|n, d≥1} σ₀(d). Give a formula for F(n).

Problem 7. Let F(n) = Σ_{d|n, d≥1} μ(d)σ₀(d). Give a formula for F(n).

Problem 8. Let F(n) = Σ_{d|n, d≥1} μ(d)σ₁(d) Give a formula for F(n).

Problem 9. Show, by induction on n, that if n and in are positive integers, then 2^m - 1 divides 2^mn - 1.

Problem 10. Let n and in be positive integers. Use congruence properties to show that 2^mn ≡ 1 mod 2^m - 1.

Problem 11. Show that Φ(n²) = nΦ(n) for all positive integers.

Problem 12. Prove that there are infinitely many primes congruent to 3 mod 4.

Problem 13. Find another proof of infinitude of primes using Euler's phi function.

Problem 14. Prove that for any positive integer n, n = Σ_{d|n, d≥0} Φ(d)

Problem 15. Show that p is prime if and only if Φ(p) = 2.

Problem 16. Suppose f is a multiplicative arithmetic function. Let n = p₁^α1 ....... p_r^αr be the prime factorization of n. Assume p_i's are distinct. Prove that f (n) = f (p₁^α1) ..... f(p_r^αr).

Problem 17. Prove Lemma 7 in lectures

Problem 18. Let a, b be nonzero intergers. Prove that (a, b) = 1 if and only if a and b have no common prime divisor.