# Thread: Euler Phi Function Problem

1. ## Euler Phi Function Problem

Suppose that n is a positive integer with E(n) = 8 .. E denotes Euler Phi Function

Show that if p is an odd prime divisor of n, then p=3 or 5

and hence find all possible values for n?

To be honest, I did this more intuitively, then systematically.. I arrive at the solution fo 15. Which makes sense, since p|15 .... and give me E(15) = 8

How would I approach this question in a more formal fashion ?

Thanks

2. Originally Posted by ikurwae89
Suppose that n is a positive integer with E(n) = 8 .. E denotes Euler Phi Function

Show that if p is an odd prime divisor of n, then p=3 or 5

and hence find all possible values for n?

To be honest, I did this more intuitively, then systematically.. I arrive at the solution fo 15. Which makes sense, since p|15 .... and give me E(15) = 8

How would I approach this question in a more formal fashion ?

Thanks

1) if $\displaystyle n=p^k\,,\,p$ a prime, then $\displaystyle \phi(n)=\phi(p^k)=p^{k-1}(p-1)=8\Longleftrightarrow p = 2\,,\,k=4$ , but then

$\displaystyle n$ has no odd prime divisors, thus

2) If $\displaystyle n=p_1^{a_1}\cdot\ldots\cdot p_m^{a_m}\,,\,a_i\in \mathbb{N}\,,\,p_i$ primes, at least one of which is odd, then $\displaystyle \phi(n)=n\displaystyle{\prod\limits^m_{k=1}\left(1-\frac{1}{p_k}\right)}$.

Continue from here, perhaps using induction on the number of different prime divisors of p...

Tonio