When is the kernel of the $(n-1)$-power map a proper subgroup?

Question

What is my question?

Recently I have been trying to learn The Miller–Rabin test and get stuck in detail as I posted in the title.

Firstly I will introduce some notions:

$L_n=\{ \alpha \in \mathbb{Z}^+_n : \alpha^{n-1}=1 \}$

$\mathbb{Z}^*_n=\{\alpha \in \mathbb{Z}^+_n: \exists \beta \in \mathbb{Z}^+_n\ \text{such that}\ \alpha \beta = 1\} $

The question is: if $n$ is an even composite, how to show that $L_n \subsetneq \mathbb{Z}^*_n$? (the operation is multiplication)

What is the motivation of the question?

For $a \in \mathbb{Z}$, define $[a]_n$ to be $\{x \in \mathbb{Z}:x \equiv a\mod n\}$ ; $x \equiv a\mod n$ means $x-a$ is an integer mutiple of $n$.

Define $\mathbb{Z}_n$to be $\{[a]_n:a \in \mathbb{Z}\}$

Define $\mathbb{Z}^+_n$ to be the set of non-zero elements in $\mathbb{Z}_n$;$|\mathbb{Z}_n^+|=n-1$

Given a positive integer $n>1$, I want to define a set $L_n \subseteq \mathbb{Z}^+_n$, such that:

1. If n is prime, then $L_n = \mathbb{Z}_n^∗$.
2. If n is even composite, $|L_n| ≤ c(n − 1)$ for some constant $c < 1$.

Now I want to prove that if we define $L_n$ as : $$\{\alpha \in \mathbb{Z}_n^+ : \alpha^{n-1}=1\}$$ then we are done.

Why abstract algebra is important in the question?

In fact, two operations have been defined on the set $\mathbb{Z}_n$: $$[a]_n + [b]_n := [a+b]_n$$ $$[a]_n * [b]_n := [a*b]_n$$ You can assume these two definitions are well-defined.Thus $\mathbb{Z}_n$ is a ring(in fact, a communative ring with uity). Moreover,$\mathbb{Z}^*_n$ is an abelian group under the multiplication $*$.

If we define a group homomorphism $\theta: \mathbb{Z}^*_n \to \mathbb{Z}^*_n$ as $\alpha \mapsto \alpha^{n-1}$, then $L_n$ is exactly the kernel of $\mathbb{Z}^*_n$; thus $L_n$ is a subgroup of $\mathbb{Z}^*_n$.

More about $\mathbb{Z}^*_n$

$\mathbb{Z}^*_n=\{ [a]_n:gcd(a,n)=1 \}$;$|\mathbb{Z}^*_n|=\varphi(n)$, where $\varphi$ is Euler's phi function.

If $n$ is a prime, then $$\mathbb{Z}^*_n=\{[a]_n:a=1,2,...n-1\}$$ which is a cyclic group of order $n-1$;thus, $L_n = \mathbb{Z}_n^∗$.

For even composite number $n$, if we can prove that $L_n \subsetneq \mathbb{Z}^*_n$, then by Lagrange Theorem,$|\mathbb{Z}^*_n|=t|L_n|$ for some integer $t>1$, we can conclude that $$|L_n|=\frac{1}{t}|\mathbb{Z}^*_n| \le \frac{1}{2}|\mathbb{Z}^*_n|\le \frac{1}{2}(n-1)$$

Answer 1

consider $[-1]_n$

Since $n$ is even, $(−1)^{n−1}=−1$, $-1$ is not in $L_n$.

But gcd(−1,n)=1, so $L_n$ is a proper subset

Thanks for the help of Jyrki Lahtonen :)