Euler's Totient Function and a Subset of Z/nZ

Suppsoe we are given an integer $n$. Define \begin{align*} \psi \left( n \right) = \left| \left\{ a \in \mathbb{Z}/ n\mathbb{Z}^\times \vert a^{n-1} \neq 1\right\} \right| \end{align*} Show: if $\psi \left( n \right) \geq 1$, it holds that $\psi \left( n \right) \geq \frac{1}{2} \phi \left( n \right)$, where $\phi \left( n \right)$ is the totient function.

I do not really have an idea how to solve this. I would be happy to get some hints.

At the moment I know: $\phi \left( n \right) = |\mathbb{Z} / n\mathbb{Z}^\times|$ and I believe there is a way to reduce the problem to using Euler's Totient Theorem, but I am stuck at the first assumption in the theorem being $gcd\left(a , n \right) = 1$.

Edit: I think we can inspect two cases: $n$ being prime and $n$ being not prime.

Let $n$ be a prime number then it holds that $\phi \left( n \right) = n-1$. With Euler's Totient Theorem we get $a^{\phi\left( n \right)} = a^{n-1} \equiv 1 \, mod \, (n)$ meaning $\psi\left( n \right) = 0$ and the assumption is not fullfilled.

Now we do know that $n$ has to be not prime, meaning $n$ is even and $n\neq 2$, any suggestions how to proceed?

• The assumption $\gcd(a,n)=1$ holds automatically, because we're only interested in $a\in \Bbb Z/n\Bbb Z^\times$. – Arthur Nov 25 '15 at 17:09
• @Arthur well, thank you. do not how i did not realise that. – Abbraxas Nov 25 '15 at 17:11
• No worries, it happens to all of us. – Arthur Nov 25 '15 at 17:12

Because $\psi\left( n \right) \geq 1$ it follows $\exists a \in \psi\left( n \right)$ and we look at the set $\psi\left( n \right)^c$ in $\mathbb{Z}/n\mathbb{Z}^\times$. Now we construct a set $P_a$ by using $a \in \psi\left( n \right)$ and $b \in \psi\left( n \right)^c$. Define: \begin{align*} P_a:=\left\{ ab \vert a \in \psi\left( n \right) \text{and}\, b \in \psi\left( n \right)^c \right\} \end{align*} Then it holds that $\vert P_a \vert = \vert \psi\left( n \right)^c\vert$, as one can see by $ab = a\hat b \Leftrightarrow b = \hat b$, because the group of units is a ring. Furthermore, one can show that $P_a \cap \psi\left( n \right)^c = \emptyset$. This can be shown by using Fermat's little theorem: \begin{align*} & c \in P_a \cap \psi\left( n \right)^c = \emptyset \quad c=ab \text{ in fact } c=bb \\ \Rightarrow &a = bc^{-1} = bc^{\phi\left( n \right)-1} \\ \Rightarrow &a^{n-1} \equiv b^{n-1}\left(c^{n-1}\right)^{\phi\left( n \right)-1} \equiv 1 \, mod \, n \end{align*} The last implication is false because $a \in \psi\left( n \right)$.
Because $P_a,\psi\left( n \right)^c \subset \left( \mathbb{Z}/ n\mathbb{Z}\right)^\times$, $P_a \cap \psi\left(n \right)^c = \emptyset$ and $\vert P_a \vert = \vert \psi\left( n \right)^c \vert$ it holds: