Euler Phi Function Problem

**ikurwae89** · November 11th 2010, 04:43 PM

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

**tonio** · November 11th 2010, 06:23 PM

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 $n=p^k\,,\,p$ a prime, then $\phi(n)=\phi(p^k)=p^{k-1}(p-1)=8\Longleftrightarrow p = 2\,,\,k=4$ , but then

$n$ has no odd prime divisors, thus

2) If $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 $\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

Thread: Euler Phi Function Problem

LinkBack

Thread Tools

Display

Euler Phi Function Problem

Similar Math Help Forum Discussions

Euler's phi-function.

Euler path and Euler circuit problem

Euler Phi function problem.

Again, phi euler function

Help with euler-phi function

Search Tags