The formula works only for k > 0.
(I will presume that d and n are positive integers.) This is one of those "duh!" thoughts but I am messing up the proof somehow. I'd appreciate it is someone could take a look at it.Prove that if d divides n then divides .
First: If d|n then n = kd for some positive integer k. Using their decomposition into powers of primes, let
Now, we have that
So finally we get
Now, I thought that simplified expression to be kinda cool. But as I was thinking about it I checked:
So I've done something incorrectly. (Though I suspect the general structure of the proof is sound.)
I think I've got the general idea, but I can't find a good way to express the final answer.
, where i runs over the primes in the decomposition.
i and j run over the decompositions and have no restrictions
(The above definitions solve the problem of having 0 exponenets.)
Continuing we have
We need to have some care about primes common to both factor sets. So break the factors into two groups: primes common to both k and d (x), and not shared (y):
By construction the x product and y product are relatively prime, so we may factor:
So this leaves us with
Clearly the denominator is completely canceled by the factors in the numerator. But how do I show that? I'm a bit stumped on how to express this mathematically. (Perhaps because I need to get to bed!)
PS Is this problem really this abstract (and long)? This is rather more intense than the other problems in the set.