# Homework Help: Number Theory Q re: Euler phi-function

1. Apr 15, 2012

### pjc11

1. The problem statement, all variables and given/known data

Let p be prime. Show that p n, where n is a positive integer, iff $\phi$(np) = (p-1)$\phi$(n).

2. Relevant equations

Theorem 1: If p is prime, then $\phi$(p) = p-1. Conversely, if p is a positive integer with $\phi$(p) = p-1, then p is prime.

Theorem 2: Let m and n be relatively prime positive numbers. Then $\phi$(mn) = $\phi$(m)$\phi$(n).

3. The attempt at a solution

Assume that p n.
By Theorem 2, $\phi$(np) = $\phi$(n)$\phi$(p).
By Theorem 1, $\phi$(np) = $\phi$(n)$\cdot$(p-1).
So, if p n, then $\phi$(np) = (p-1)$\cdot$$\phi$(n).

Now, assume that $\phi$(np) = (p-1)$\phi$(n).
By Theorem 1, $\phi$(np) = $\phi$(p)$\phi$(n), since p is prime.

...and, that's it. I can't use Theorem 2 to show that n and p are relatively prime, so I'm not entirely sure what to do next. p is prime, so n p, but I don't see anything to base a conclusion of p n.

Any help would be greatly appreciated!

2. Apr 15, 2012

### Dick

If a prime p doesn't divide n then aren't p and n relatively prime? A common divisor of p and n must divide p. Think about it.