# Euler Phi Help

• Sep 27th 2008, 06:38 AM
cutmeout
Euler Phi Help
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!
• Sep 27th 2008, 08:31 AM
o_O
For some power of a prime, $\displaystyle \varphi \left(p^n\right) = p^{n-1}(p-1)$.

And since $\displaystyle \varphi$ is a multiplicative function, let $\displaystyle m = p_{1}^{e_{1}}p_{2}^{e_{2}}\hdots p_{k}^{e_{k}}$ be the prime-power decomposition of $\displaystyle m$. Then: $\displaystyle \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 $\displaystyle \varphi (24)$, we would have: $\displaystyle \varphi (24) = \varphi (2^{3} \cdot 3) = \varphi(2^3) \cdot \varphi (3) = 2^{2} (1) \ \cdot \ 3^{0} (2) = 8$
• Sep 27th 2008, 11:15 AM
cutmeout
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.
• Sep 27th 2008, 10:40 PM
TwistedOne151
As o_O noted, $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$, and $\displaystyle \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 $\displaystyle 2^5\cdot5$. Note that the above tells us that $\displaystyle \phi\left(2^n\right)=2^{n-1}$. Thus, we need to find prime p and integer n≥1 such that $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$ is equal to five times a power of two (less than $\displaystyle 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 $\displaystyle \phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=20$
and 160=8*20, and $\displaystyle \phi(16)=\phi\left(2^4\right)=2^{4-1}=8$.
Thus 25*16=400 is one number n such that $\displaystyle \phi(n)=160$.
For the second, p=11, we have $\displaystyle \phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10$
and 160=16*10, and $\displaystyle \phi(32)=\phi\left(2^5\right)=2^{5-1}=16$.
Thus 11*32=352 is the second number n such that $\displaystyle \phi(n)=160$.
The third case, p=41, gives $\displaystyle \phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40$; here 160=4*40, and $\displaystyle \phi(8)=\phi\left(2^3\right)=2^{3-1}=4$.
Thus 41*8=328 is the third number n such that $\displaystyle \phi(n)=160$.

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

--Kevin C.
• Sep 28th 2008, 12:06 AM
Opalg
Quote:

Originally Posted by TwistedOne151
As o_O noted, $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$, and $\displaystyle \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 $\displaystyle 2^5\cdot5$. Note that the above tells us that $\displaystyle \phi\left(2^n\right)=2^{n-1}$. Thus, we need to find prime p and integer n≥1 such that $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$ is equal to five times a power of two (less than $\displaystyle 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 $\displaystyle \phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=40$ 5×4=20, not 40 !
and 160=4*40, and $\displaystyle \phi(8)=\phi\left(2^3\right)=2^{3-1}=4$.
Thus 25*8=200 is one number n such that $\displaystyle \phi(n)=160$.

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

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

Quote:

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

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

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

Quote:

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

Yet again, there are other possibilities...
• Sep 28th 2008, 12:53 PM
cutmeout
Thank you everyone; I understand it much better now.