Let $n\in\mathbb Z_{>0}$ and $a\in\mathbb Z$.
a) Prove $\overline a=\overline{-a}\iff \overline a=\overline0.$
b) Prove that
if $n$ is odd, then $\overline a=\overline{-a}\iff\overline a=\overline0,$
if $n$ is even, then $\overline a=\overline{-a}\iff\overline a=\overline0$ or $\overline a=\overline{n/2}.$
c) Prove that if $n>2$, then $\phi(n)$ is even.
I've shown a) and b). Here $\phi$ is the Euler function, defined by
$\phi(n)=\#\{a\in\mathbb Z\mid1\leq a\leq n, \gcd(a,n)=1\}$.
However, I have no clue how to use a) and b) to prove this. Could someone give me a hint? I was considering using induction.
Consider $\mathbb N$\ $m\mathbb N$. Assume that for some $n\in\mathbb N$, it holds that $\phi(n)$ is even. Now consider $n+1$. We know that $\phi(n+1)=\phi(n)$ if $\gcd(n+1,m)\neq 1$, and $\phi(n+1)=\phi(n)+1$ if $\gcd(n+1,m)=1$. But I should be able to show that we can only add 2, and not 1. But I wouldn't know how to proceed?
If $n$ is odd with $n>1$, you can pair up $a$ and $n-a$. If one of those is relatively prime to $n$, then so is the other.
If $n$ is even with $n > 2$, then $n/2$ is not relatively prime to $n$, hence the pairing used for the odd case still works.