the way to calculate the number of element in $\mathbb Z^*_n$ have order 2?

Question

I want to show that if $n=pq$ such that $p$ and $q$ are distinct odd primes the number of $\ (a,b)$ such that $a$ and $b \in \mathbb Z_n$ and $a\equiv a^{-1}\pmod n$ and $b(a+1)\equiv0\pmod n$ is $n+p+q+1$. thanks P.S:is the way to calculate the number of element in $\mathbb Z^*_n$ have order 2?

Answer 1

To begin with, $a \equiv a^{-1} \pmod n$ is equivalent to $a^2 \equiv 1 \pmod n$, and you have to take $a \in \mathbb Z^*_n$. We can use CRT to solve this equation: $$ \begin{cases} a^2 \equiv 1 \pmod p \\ a^2 \equiv 1 \pmod q \end{cases} $$ Both $\mathbb Z^*_p$ and $\mathbb Z^*_q$ are cyclic and have even size. That's why there are two solutions for each of the equations (you can check it e.g. by taking discrete logarithm of the equations). You can easily check that these ones fit: $$ \begin{cases} a \equiv \pm 1 \pmod p \\ a \equiv \pm 1 \pmod q \end{cases} $$

Now let's look at $b(a+1) \equiv 0 \pmod n$. Again, we can use CRT to search for solutions modulo $p$ and modulo $q$ separately. So we have equations: $$ \begin{cases} (a+1) b \equiv 0 \pmod p \\ (a+1) b \equiv 0 \pmod q \end{cases} $$ If $a \equiv 1 \pmod p$, then the equation $2b \equiv 0 \pmod p$ obviously has a single solution $b \equiv 0 \pmod p$, since $p$ is odd. If $a \equiv -1 \pmod p$, then the equation is just $0 \equiv 0 \pmod p$, so any $b \in \mathbb Z_p$ fits. There are $p$ solutions with $a \equiv -1$ and one solution with $a \equiv 1$, in total $p + 1$ solutions.

Speaking of solutions modulo $q$, it is quite the same: there are $q + 1$ solutions. Any pair of a solution modulo $p$ and a solution modulo $q$ can be combined to obtain a single solution modulo $n$ due to CRT. So there are $(p+1)(q+1) = n + p + q + 1$ solutions.

P.S. The elements in $\mathbb Z^*_n$ of order $2$ are exactly the square roots of $1$ minus the single trivial unit solution (which has order $1$). You can use CRT again to find number of square roots. For module $n = p^k$ with odd $p$, there are $2$ square roots, because $\mathbb Z^*_n$ is cyclic and has even size. For $n = 2^k$, there is $1$ root for $k = 1$, $2$ roots for $k = 2$, and $4$ roots for $k \ge 3$, which follows from the structure of multiplicative group. For example. with $n = 2^3 \cdot 5^2 \cdot 7$, there are $4 \cdot 2 \cdot 2 - 1 = 15$ elements or order $2$ in $\mathbb Z^*_n$. For $n = 2^2 * 3$, there are $4$ such elements.