I have to find out how many elements of $Z/8Z$ that satisfy the equation $x^{2}=1$
Clearly the solutions are the elements of $U(n)$ that have order $2$.
Manually I checked them to be $\bar 1$,$\bar 3$, $\bar 5$,$\bar 7$.
I can see that for any $n$, $n-1$ has order $2$ in $U(n)$ . What about the others like what are some theories to use here so as to find elements of a particular order in $Z_{n}$ without checking manually.
Thanks for any help.
This is for order $2$, general $n$. Factor $n$ as $2^{a_0}p_1^{a_1}\cdots p_k^{a_k}$ where the $p_i$ are distinct odd primes.
Modulo $2^{a_0}$, there is one element of order $\le 2$ if $a_0=1$, there are two if $a_0=2$, and there are four if $a_0\ge 3$. The situation for odd primes is simpler. Only $1$ and $-1$ have order $\le 2$ modulo $p_i^{a_i}$.
The only way to have order $\le 2$ modulo $n$ is to have order $\le 2$ modulo $2^{a_0}$ and the $p_i^{a_i}$ and order $2$ modulo at least one of these.
To produce all possibilities, we use the Chinese Remainder Theorem on all possible combinations of elements of order $\le 2$ modulo the prime powers in the prime power decomposition of $n$ (we throw away the one element of order $1$).
The situation is simplest when $n$ is odd. Then we get $2^k-1$ elements of order $2$.
For $2^a$ where $a\ge 3$, the elements of order $\le 2$ are $1$, $-1$, $2^{a-1}-1$, and $2^{a-1}+1$.
