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?

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.