Totient function and divisibility

Re: Totient function and divisibility

The formula works only for k > 0.

Re: Totient function and divisibility

Quote:

Originally Posted by

**emakarov** The formula

works only for k > 0.

Ah! So if a prime factor is missing...

I'll be back.

-Dan

Re: Totient function and divisibility

I think I've got the general idea, but I can't find a good way to express the final answer.

Let

, where i runs over the primes in the decomposition.

, ditto

i and j run over the decompositions and have no restrictions

(The above definitions solve the problem of having 0 exponenets.)

Continuing we have

and

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!)

-Dan

PS Is this problem really this abstract (and long)? This is rather more intense than the other problems in the set.

Re: Totient function and divisibility

Success! All I needed to finish the proof came to me just after I woke up. :)

If that sounds nerdy I woke up at 3 AM the other night working on one point compactification in my sleep.

-Dan