1. Euler Phi function problem.

The problem is:

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

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

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

I know since n is composite $\displaystyle \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...

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

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

$\displaystyle \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

$\displaystyle \chi$ $\displaystyle \sigma$

3. Sorry, I made a big mistake in the problem. I know that for $\displaystyle \phi(m)$, but we're supposed to express $\displaystyle \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...

$\displaystyle 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...

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

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

Merry Christmas from Italy

$\displaystyle \chi$ $\displaystyle \sigma$

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

it's supposed to be $\displaystyle 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 $\displaystyle \varphi(m\cdot n)=\varphi(m) \cdot \varphi (n)$ and because $\displaystyle \forall n >2$ $\displaystyle \varphi(n)$ is even , the only possibility if...

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

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

Merry Christmas from Italy

$\displaystyle \chi$ $\displaystyle \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 $\displaystyle \forall n>2$ $\displaystyle \varphi (n)$ is an even number and the only n for which $\displaystyle 4$ doesn't devide $\displaystyle \varphi (n)$ are $\displaystyle n=p$ and $\displaystyle 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 $\displaystyle \varphi(m\cdot n)= \varphi(m)\cdot \varphi (n)$...

Merry Christmas from Italy

$\displaystyle \chi$ $\displaystyle \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!