I am trying to understand a proof (from the German book "Einführung in die Kryptografie" by Johannes Buchmann) that there are at most $(n-1)/4$ non-witnesses against the primality of $n$ in the Miller-Rabin algorithm that are coprime to $n$.
The Miller-Rabin test is stated in the following way:
Let $s = \max\{r \in \mathbb{N}: 2^r \text{ divides } n-1\}$ and $d = (n-1)/2^s$. If $n$ is a prime number and if $a$ is a number coprime to $n$ then
$$ a^d \equiv 1 \pmod{n} \tag{A} $$
or there is a $r$ in the set $\{0,1,\ldots,s-1\}$ such that
$$a^{2^rd} \equiv -1 \pmod{n} \tag{B} $$
I have a problem with the following proof:
Let $n \ge 3$ be an odd composite number. We want to estimate how many numbers $a \in \{0,1,\ldots,s-1\}$ exist for which $\gcd(a,n-1) = 1$ and both $(A)$ and $(B)$ hold. If there is no such $a$ we are fi
We set the prime factorisation of $n$ to $n = \prod_{p\mid n} p^{e(p)}$.
The author considers the following two subgroups of $\mathbb{Z}_n^{\times}$ $$\begin{align*} K &= \{ a + n\mathbb{Z} : \gcd(a,n) = 1 \text{ and } a^{n-1} \equiv \pm 1 \pmod{p^{e(p)}} \text{ for all primes $p$ such that } p|n\}\\ L &= \{ a + n\mathbb{Z} : \gcd(a,n) = 1 \text{ and } a^{m} \equiv \pm 1 \pmod{n}\} \end{align*}$$
In the coure of the proof the author considers the groups $L$ and $K$ and distinguishes between them. I do not understand why these two groups are not just the same by the Chinese remainder theorem, as all $p^{e(p)}$ are pairwise coprime and $n$ is by definition the product of these $p^{e(p)}$. Could you tell me what I am getting wrong?