# Help with function fi

1. Nov 12, 2012

### catala

Hi,

I need help in the following demonstration:

If $(m,n)=d$ then $\Phi(mn)=\frac{d}{\Phi(d)}\Phi(m)\Phi(n)$

Thank you very much for your support! :D

2. Nov 12, 2012

### PiAreSquared

Ok, so first begin by letting m= p$^{κ_{1}}_{1}$...p$^{κ_{r}}_{r}$ and n=p$^{β_{1}}_{1}$...p$^{β_{r}}_{r}$, where κ$_{i}$,β$_{i}$≥ 0 $\forall$i. Then (m,n)= p$^{δ_{1}}_{1}$...p$^{δ_{r}}_{r}$, where δ$_{i}$ = min{κ$_{i}$,β$_{i}$}. Then use the fact that $\Phi$(w) = w$∏^{i=1}_{r}$ (1-1/p$_{i}$), given that w = p$^{κ_{1}}_{1}$...p$^{κ_{r}}_{r}$ to rewrite $\Phi$(mn). At this point, it isn't too difficult to come up with the desired result. If you rewrite the right side of what you are trying to prove, it helps to at least see where you should go next.

Also, as a side note, $\Phi$ is spelled 'phi' :tongue: