- #1

tarheelborn

- 123

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter tarheelborn
- Start date

- #1

tarheelborn

- 123

- 0

- #2

Petek

Gold Member

- 398

- 21

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

Petek

Petek

- #3

tarheelborn

- 123

- 0

- #4

Tinyboss

- 244

- 0

- #5

tarheelborn

- 123

- 0

- #6

Petek

Gold Member

- 398

- 21

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

tarheelborn

- 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

- 398

- 21

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

Share:

- Last Post

- Replies
- 9

- Views
- 684

- Replies
- 6

- Views
- 879

- Replies
- 15

- Views
- 3K

MHB
Matrices Proof

- Last Post

- Replies
- 5

- Views
- 758

- Last Post

- Replies
- 4

- Views
- 742

- Last Post

- Replies
- 12

- Views
- 559

- Last Post

- Replies
- 17

- Views
- 633

- Replies
- 1

- Views
- 498

- Last Post

- Replies
- 7

- Views
- 294

- Last Post

- Replies
- 21

- Views
- 592