Prove that

d(n) are the positive factors of n. Ex: d(12) = 6 (the factors are 1, 2, 3, 4, 6, 12).

Printable View

- Nov 2nd 2009, 08:07 PMkyldn6Multiplicative Arithmetic Functions
Prove that

d(n) are the positive factors of n. Ex: d(12) = 6 (the factors are 1, 2, 3, 4, 6, 12). - Nov 3rd 2009, 05:10 PMtonio

Well, it took a while but I think I got it. Of course, using Dirichlet's product I suppose it could be way faster, but I'm assuming you haven't yet covered that, so let's try it the long way

Let be the prime decomposition of n, with . We'll need the following easy lemma:

Lemma: The number of positive divisors of n is

Now,by induction on n = the number of distinct prime divisors of n: if , then , and we're cool.

Assume now the claim's true for all natural numbers divisible by up to n-1 different primes, and let and define

, then:

, the 2nd equality being due to the inductive hypothesis and the fact that the factor appears

multiplying each and every one of the divisors of m , . Thus:

, since . Q.E.D.

Tonio - Nov 3rd 2009, 07:47 PMkyldn6
Thanks Tonio, I managed to work this one out and came up with the same proof you presented in the first half of you post. Thanks for verifying it.