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

Question

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?

Answer 1

So it seems there is a solution. I am not quite sure whether it is correct because it seems really artificial.

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:

\begin{align*} \vert \psi\left( n \right)^c \vert = \dfrac{1}{2} \vert P_a \cup \psi\left( n \right)^c \vert \leq \dfrac{1}{2} \vert \left( \mathbb{Z}/ n\mathbb{Z} \right)^\times \vert = \dfrac{1}{2} \phi\left( n \right). \end{align*}

If anyone may know where someone could find a proof for this I would be happy, because it feels really artificial and gives no insight.