Euler Phi Help

**cutmeout** · September 27th 2008, 06:38 AM

Hi everyone,

I need to find all integers n such that Phi(n) = 160 and as an extension, make a list of all primes that might possibly divide x if Phi(x) = 1000. I'm a bit lost on this and was wondering if anyone could give me a useful start? Thanks!

**o_O** · September 27th 2008, 08:31 AM

For some power of a prime, $\varphi \left(p^n\right) = p^{n-1}(p-1)$ .

And since $\varphi$ is a multiplicative function, let $m = p_{1}^{e_{1}}p_{2}^{e_{2}}\hdots p_{k}^{e_{k}}$ be the prime-power decomposition of $m$ . Then: $\varphi (m) = \varphi \left(p_{1}^{e_{1}}\right)\varphi\left(p_{2}^{e_{2 }}\right)\hdots \varphi\left(p_{k}^{e_{k}}\right)$

So if I were to find $\varphi (24)$ , we would have: $\varphi (24) = \varphi (2^{3} \cdot 3) = \varphi(2^3) \cdot \varphi (3) = 2^{2} (1) \ \cdot \ 3^{0} (2) = 8$

**cutmeout** · September 27th 2008, 11:15 AM

Right. I understand how to evaluate Phi(n), but I'm concerned with finding an n such that Phi(n) is equal to a given number.

**TwistedOne151** · September 27th 2008, 10:40 PM

As o_O noted, $\phi\left(p^n\right)=p^{n-1}(p-1)$ , and $\phi\left(p_{1}^{e_1}p_{2}^{e_2}\cdots p_{k}^{e_k}\right)=\phi\left(p_{1}^{e_1}\right)\ph i\left(p_{2}^{e_2}\right)\cdots\phi\left(p_{k}^{e_ k}\right)$ .

The prime factorization of 160 is $2^5\cdot5$ . Note that the above tells us that $\phi\left(2^n\right)=2^{n-1}$ . Thus, we need to find prime p and integer n≥1 such that $\phi\left(p^n\right)=p^{n-1}(p-1)$ is equal to five times a power of two (less than $2^5=32$ ). This needs either p=5 or p-1 is 5 times a power of 2.
This leaves us with p=5, p=11, or p=41.
The first has $\phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=20$
and 160=8*20, and $\phi(16)=\phi\left(2^4\right)=2^{4-1}=8$ .
Thus 25*16=400 is one number n such that $\phi(n)=160$ .
For the second, p=11, we have $\phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10$
and 160=16*10, and $\phi(32)=\phi\left(2^5\right)=2^{5-1}=16$ .
Thus 11*32=352 is the second number n such that $\phi(n)=160$ .
The third case, p=41, gives $\phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40$ ; here 160=4*40, and $\phi(8)=\phi\left(2^3\right)=2^{3-1}=4$ .
Thus 41*8=328 is the third number n such that $\phi(n)=160$ .

Working similarly, you can find the primes that might divide x if $\phi(x)=1000=2^3\cdot5^3$ .

--Kevin C.

**Opalg** · September 28th 2008, 12:06 AM

Originally Posted by TwistedOne151

As o_O noted, $\phi\left(p^n\right)=p^{n-1}(p-1)$ , and $\phi\left(p_{1}^{e_1}p_{2}^{e_2}\cdots p_{k}^{e_k}\right)=\phi\left(p_{1}^{e_1}\right)\ph i\left(p_{2}^{e_2}\right)\cdots\phi\left(p_{k}^{e_ k}\right)$ .

The prime factorization of 160 is $2^5\cdot5$ . Note that the above tells us that $\phi\left(2^n\right)=2^{n-1}$ . Thus, we need to find prime p and integer n≥1 such that $\phi\left(p^n\right)=p^{n-1}(p-1)$ is equal to five times a power of two (less than $2^5=32$ ). This needs either p=5 or p-1 is 5 times a power of 2.
This leaves us with p=5, p=11, or p=41.
The first has $\phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=40$ 5×4=20, not 40 !
and 160=4*40, and $\phi(8)=\phi\left(2^3\right)=2^{3-1}=4$ .
Thus 25*8=200 is one number n such that $\phi(n)=160$ .

So if we write $160=2^3\times20$ and use the fact that $2^3=\phi(2^4)$ then we get 25×16=400 as the first solution.

But there is another possibility here. Notice that $\phi(3)=3^0(3-1)=2$ . So we could write $160= 20\times2\times2^2 = \phi(5^2)\phi(3)\phi(8) = \phi(600).$

Originally Posted by TwistedOne151

For the second, p=11, we have $\phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10$
and 160=16*10, and $\phi(32)=\phi\left(2^5\right)=2^{5-1}=16$ .
Thus 11*32=352 is the second number n such that $\phi(n)=160$ .

Here again, you get more than one solution. Starting from 160=16×10 and using $10=\phi(11)$ , we need to find all the numbers n for which $\phi(n)=16$ :

$16=2^4=\phi(2^5)$ is one possibility. But so are
$16=2\times2^3=\phi(3)\phi(2^4)$ ,
$16=4\times2^2=\phi(5)\phi(2^3)$ ,
$16=2\times4\times2=\phi(3)\phi(5)\phi(2^2)$ , and finally
$16=\phi(17)$ .

Originally Posted by TwistedOne151

The third case, p=41, gives $\phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40$ ; again, 60=4*40, and $\phi(8)=\phi\left(2^3\right)=2^{3-1}=4$ .
Thus 41*8=328 is the third number n such that $\phi(n)=160$ .

Yet again, there are other possibilities...

**cutmeout** · September 28th 2008, 12:53 PM

Thank you everyone; I understand it much better now.

Thread: Euler Phi Help

LinkBack

Thread Tools

Display

Euler Phi Help

Similar Math Help Forum Discussions

Euler phi

Euler path and Euler circuit problem

Graph Theory - To Euler or not to Euler? With attempted working.

wats the relation between Fermat, Euler, Euler–Jacobi

euler phi-function

Search Tags