I know that if $gcd(m,n)=p$, then both $m, n$ have $p$ as a factor.
I also know that for any prime $p$, $Φ(p)=p-1$.
Prove $gcd(m,n)=p\implies Φ(mn)=(p/p-1)Φ(m)Φ(n)$
426 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail AtThere are 2 best solutions below
On
This is a restatement of the previous answer, taking into account an oversight, to wit that one of $m,n$ might have more than one factor of $p$.
Suppose $(m, n) = p$. Then WLOG $m = pm^\prime$ and $n = p^kn^\prime$ and $(m^\prime, n^\prime)= 1$. Thus $$\varphi(m) = (p-1)\varphi(m^\prime) \\ \varphi(n) = (p^{k-1})(p-1)\varphi(n^\prime) \\ \varphi(mn) = \varphi(p^{k+1}m^\prime n^\prime) = \varphi(p^{k+1}) \varphi(m^\prime)\varphi(n^\prime).$$
Now $\varphi(p^{k+1}) = p^k(p-1)$ so we have
$$\varphi(p^{k+1})\varphi(m^\prime)\varphi(n^\prime) = p^k(p-1)\varphi(m^\prime)\varphi(n^\prime)\tag{1}$$
And $$\varphi(m)\varphi(n)=(p-1)\varphi(m^\prime)\cdot p^{k-1}(p-1)\varphi(n^\prime) \\ \varphi(m)\varphi(n)=p^{k-1}(p-1)^2\varphi(m^\prime)\varphi(n^\prime)$$
Thus $$\frac{p}{p-1}\varphi(m)\varphi(n)=\frac{p}{p-1}p^{k-1}(p-1)^2\varphi(m^\prime)\varphi(n^\prime)=p^k(p-1)\varphi(m^\prime)\varphi(n^\prime) \tag{2}$$
Note that the right hand expressions in (1) and (2) are identical, so the left hand expressions are perforce equal. $$\varphi(mn)=\varphi(p^{k+1})\varphi(m^\prime)\varphi(n^\prime) = \frac{p}{p-1}\varphi(m)\varphi(n)$$
We are done.
Suppose $(m, n) = p$. Then $m = pm^\prime$ and $n = pn^\prime$ and $(m^\prime, n^\prime)= 1$. Thus $$\varphi(mn) = \varphi(p^2m^\prime n^\prime) = \varphi(p^2) \varphi(m^\prime)\varphi(n^\prime).$$
Now $\varphi(p^2) = p(p-1)$ so we have
$$\varphi(p^2)\varphi(m^\prime)\varphi(n^\prime) = p(p-1)\varphi(m^\prime)\varphi(n^\prime).$$
Multiplying by $1 = \frac{p-1}{p-1}$ we get
$$p(p-1)\varphi(m^\prime)\varphi(n^\prime) = \frac{p\varphi(p)^2}{(p-1)}\varphi(m^\prime)\varphi(n^\prime) = \frac{p}{p-1}\varphi(pm^\prime)\varphi(pn^\prime) = \frac{p}{p-1}\varphi(m)\varphi(n).$$