Share
Explore BrainMass

Combinatorial Study of φ(n), d(n) and σ(n).

Arithmetic Functions
Combinatorial Study of φ(n)

1. If gcd(m,n) = 1, then φ(m,n) = φ(m)φ(n).
Use this to give a proof that φ(n) = n Π(1 - 1/p)
p/n

2. Prove that d(n) is odd iff n is a perfect square.

3. Prove that σ(n) ≡ d(m)(mod 2) where m is the largest odd factor of n.

3.(2nd Part)
If σ(n) = 2n, n is a perfect number. Prove that if n is a perfect number , then
∑1/d = 2.
d/n

4. Evaluate σ(210), φ(100) and σ(999).

5. Evaluate d(47), d(63) and d(150).

See the attached file.

Attachments

Solution Preview

Arithmetic Functions
Combinatorial Study of φ(n)

1. If gcd(m,n) = 1, then φ(m,n) = φ(m)φ(n).
Use this ...

Solution Summary

This solution is comprised of a detailed explanation of the Combinatorial Study of φ(n), d(n) and σ(n).
It contains step-by-step explanation for the following problem:

1. If gcd(m,n) = 1, then φ(m,n) = φ(m)φ(n).
Use this to give a proof that φ(n) = n Π(1 - 1/p)
p/n

2. Prove that d(n) is odd iff n is a perfect square.

3.Prove that σ(n) ≡ d(m)(mod 2) where m is the largest odd factor of n.

3.(2nd Part)
If σ(n) = 2n, n is a perfect number. Prove that if n is a perfect number , then
∑1/d = 2.
d/n

4. Evaluate σ(210), φ(100) and σ(999).

5. Evaluate d(47), d(63) and d(150).

Solution contains detailed step-by-step explanation.

$2.19