- #1

- 123

- 0

- Thread starter tarheelborn
- Start date

- #1

- 123

- 0

- #2

Petek

Gold Member

- 363

- 8

Hint: Can you prove the result if d and n are both powers of the same prime p?

Petek

Petek

- #3

- 123

- 0

- #4

- 236

- 0

- #5

- 123

- 0

- #6

Petek

Gold Member

- 363

- 8

Your work isn't correct, but you're getting closer. Look at your expressions for phi(d) and phi(n). They're the same, which can't be right. Also, both expressions contain a "p", which wasn't used before.

Let's go back to my hint and just consider the case in which d and n are both powers of the same prime p. So we have that d = p^k and n = p^l. The assumption is that d|n. What can you then say about the relation between k and l?

Assuming that you got that part, now write phi(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1) and a similar expression for phi(p^l). Can you now see that phi(d)|phi(n)?

Finally, use the fact that phi is a multiplicative function (do you know what this means?) to derive the result when d|n and d and n could be any positive integers.

Petek

- #7

- 123

- 0

Now, if d|n and we let d and n be powers of the same prime p, then d=p^k and n+p^l implies k|l if k< l. Then phi(d)=phi(p^k)=p^k-p^(k-1)=p^(k-1)(p-1) and phi(n)=phi(p^l)=p^l-p^(l-1)=p^(l-1)(p-1).

I am not sure where to go with the multiplicative part. I know that phi is multiplicative, meaning that phi(dn)=phi(d)*phi(n) if (d,n)=1 which it clearly does in this case, but I'm not making a connection here. It seems to me if I got the k|l part right, then phi(d) | phi(n) follows from that, but that doesn't seem to be enough. Thanks so much for your help.

- #8

Petek

Gold Member

- 363

- 8

To use the fact that phi is multiplicative, write both d and n as the product of prime powers (using unique factorization). Now argue that phi(d) divides phi(n) by using what was proved in the preceding. For example, suppose that d = p^a q^b and n = p^c q^d, where p and q are distinct primes and d|n. Can you prove that phi(d) divides phi(n) here? Can you extend this argument to the general case?

Hope this helps.

Petek

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 11K

- Last Post

- Replies
- 1

- Views
- 5K

- Last Post

- Replies
- 11

- Views
- 12K

- Last Post

- Replies
- 4

- Views
- 8K

- Last Post

- Replies
- 6

- Views
- 3K

- Last Post

- Replies
- 14

- Views
- 5K

- Last Post

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 2K