Intro Number Theory—show gcd$(\phi(m), \phi(n)) > 1$ unless either $m$ or $n$ is $1$ or $2$

Question

Problem: Show gcd$(\phi(m), \phi(n)) > 1$ unless either $m$ or $n$ is $1$ or $2$, where $\phi(x)$ is the Euler-phi function.

Hint: Use the fact that $\phi(a)$ is even for $a > 2$

Thoughts: To be totally honest, I don't quite know how to start. It's been a long weekend already. Not asking you to flat-out do the proof, but understanding how to get the first few lines of a proof would certainly be appreciated. Not looking for anything super advanced, as this is an introductory course.

Answer 1

I will use $(a,b)$ to denote $gcd(a,b)$. Note that assuming the hint, if $m,n > 2$, then $(\phi(m), \phi(n)) \geq 2 > 1$. Now we need to show the hint. Since $m,n > 2$, we have that there are primes $p,q > 2$ dividing $n$ and $m$ respectively. Suppose that $p^{a} \mid n$ and $q^{b} \mid m$, for $a,b \geq 1$. Suppose that $p^{a}n_{1} = n$ and $q^{b}m_{1} = m$, for $n_{1} , m_{1} \in \mathbb{Z} : (m_{1},q) = (n_{1},p) = 1$.

Then since the $\phi$ function is multiplicative, that is, $\phi(xy) = \phi(x) \cdot \phi(y)$, for $(x,y) = 1$, we have that: $$ \phi(n) = \phi(p^{a})\phi(n_{1}) = (p-1)p^{a-1}\phi(n_{1}) \\ \phi(m) = \phi(q^{b}) \phi(m_{1}) = (q-1)q^{b-1}\phi(m_{1}) $$ Since $p,q > 2$ are primes, we have that $2 \mid p-1, q-1$. Hence, $(\phi(m), \phi(n)) \geq 2 > 1$, for $n,m > 2$, which is the claim.

EDIT: If $n = 2^{k} : k > 1$ (wlog) , then $\phi(n) = 2^{k-1}$, which is divisible by 2.

Answer 2

ISTS that $a\gt2\implies \varphi(a)$ is even, as pointed out.

First, if $a=p^n$, with $p$ prime, then it is easy to see that $\varphi(a)= p^n-p^{n-1}$ and is thus even.

Second, and finally, that $\varphi$ is multiplicative follows from the Chinese remainder theorem.