# Thread: Euler Phi function problem.

1. ## Euler Phi function problem.

The problem is:

$m=2\prod p_{i}^{e_i}$ for i=1...k
where $k \geq 1$, $p_1,p_2,...p_k$ are odd primes in increasing order, and $e_1,...e_k$ are positive integers.

We're told that $m=\phi(n)$ for some odd, composite n.

Express the value of n in terms of $p_1,p_2,...p_k$ and $e_1,...e_k$.

I know since n is composite $\phi(n)$ is not equal to (n-1), but I'm not sure what to do elsewhere.

2. As in ...

Euler's totient function - Wikipedia, the free encyclopedia

... if...

$m= p_{1}^{e_{1}}\dots p_{k}^{e_{k}}$ (1)

... where the $p_{i}$ are distinct primes, then...

$\varphi(m)= (p_{1}-1)\cdot p_{1}^{e_{1}-1}\dots (p_{k}-1)\cdot p_{k}^{e_{k}-1}$ (2)

Merry Christmas from Italy

$\chi$ $\sigma$

3. Sorry, I made a big mistake in the problem. I know that for $\phi(m)$, but we're supposed to express $\phi(n)$.

4. I apologize because I didn't undestand exactly Your question ...

For the fundamental theorem of arithmetic any m can be expressed as...

$m= \prod_{i} p_{i}^{e_{i}}$ (1)

... so that any m doesn't have 'special properties'. If I understand correctly Your problem is, given m, to find the value of n for which is...

$\varphi (n) = n \cdot \prod_{p|n} (1-\frac{1}{p}) = m$ (2)

In general the equation (2), that supplies the 'inverse' of $\varphi (*)$, doesn't have a single solution and can be solved by 'systematic search'...

Merry Christmas from Italy

$\chi$ $\sigma$

5. Thanks all your help...but I found another mistake i made. DOH!

it's supposed to be $m=2\prod p_{i}^{e_i}$.

Sorry for all the mistakes but I appreciate your help so far.

6. Now the trace is evident! ...

If m and n are coprime, then is $\varphi(m\cdot n)=\varphi(m) \cdot \varphi (n)$ and because $\forall n >2$ $\varphi(n)$ is even , the only possibility if...

$m= 2\cdot \prod_{i} p_{i}^{e_{i}}$ (1)

... with $\forall i$ $p_{i}$ an odd prime number is that $m+1$ is prime. In such a case the equation $\varphi(n)=m$ has the two solutions $n=m+1$ and $n=2\cdot (m+1)$ ...

Merry Christmas from Italy

$\chi$ $\sigma$

7. ## More justification?

Hi,

I am interested in this problem as well. I'm not quite following your argument for why n = (m+1) and n = 2*(m+1) must be solutions to this problem. Could you provide more detail?

Thanks!

8. In the table reported in ...

Euler's totient function - Wikipedia, the free encyclopedia

... You can verify that $\forall n>2$ $\varphi (n)$ is an even number and the only n for which $4$ doesn't devide $\varphi (n)$ are $n=p$ and $n=2\cdot p$ , being p a prime number grater than 2. That is consequence of the basic property that if m and n are coprime, then $\varphi(m\cdot n)= \varphi(m)\cdot \varphi (n)$...

Merry Christmas from Italy

$\chi$ $\sigma$

9. ## Thanks

Ah yes, I see that now, thank you. However, in the problem it is stated that n is odd and composite. This means that neither of those solutions are valid for n, since p is prime and 2*p is even.

I believe I figured it out: n must only have 1 odd factor otherwise 2^k, where k is the number of odd factors of n, would have to divide m. Since m only has one factor of 2, then k=1. Since phi(n)=m, that odd prime must be 3, otherwise an additional factor of 2 would appear from phi(q^c)=q^c*(1-1/q), where n = q^c.

Therefore n = p^(e+1) = 3^(e+1), where p and e are the prime factor and power of m.

Thanks!