Let $n$ be an odd integer with $i$ prime factors. how many values of $x (mod\ n)$ are there for which $x^2 ≡ 1 (mod\ n)$?
I used Legendre's symbol to find the following:
Let $x$ be such that $x^2 ≡ 1 (mod\ n)$.
for each prime factor $p$ of $n$, we have $(\frac{x^2}{p})=(\frac{1}{p})=1 \Rightarrow (\frac{x}{p})=\pm 1$.
so we have two possibilities for each prime factor which gives a hint that we have $2^i$ of such possibilities. But how to prove that this is exactly the number of values $x\ mod\ n$ such that $x^2 ≡ 1 (mod\ n)$?
Thank you for your help.
Let $M$ be an odd integer. Write $M=\prod_{i=1}^{\ell} p_i^{e_i}$ where $p_i$ is an odd prime and $e_i$ is a positive integer i.e., precisely $\ell$ distinct primes $p_1,p_2,\ldots, p_{\ell}$ all odd divide $M$.
An integer $x \in \mathbb{Z}/M\mathbb{Z}$ satisfies $x^2 \equiv 1$ mod $M$; $M$ odd iff $x \mod p^{e_i}_i \in \{-1,1\}$ for each $i=1,2,\ell$. [We sketch the proof of this for each integer $e_i \ge 2$; make sure you see this is true for $e_i=1$. Let $a \in \mathbb{Z}$ be such that $a^2 \equiv 1$ mod $p^{e}$; $p$ an odd prime and $e$ an integer at least 2. Now let $c$ be such that $(a+c)^2 \equiv 1$ mod $p^e$. Then note that this implies $c(2c+a) \equiv 0$ mod $p^e$. This is true if $c \equiv 0$ mod $p^e$ or $2c+a \equiv 0$ mod $p^e$. We now show that this is true only if $c \equiv 0$ or $2c+a \equiv 0$ mod $p^e$. Suppose both $c, 2c+a \not \equiv 0$ mod $p^e$. Then $p|c$ and $p|(2c+a)$. But this is impossible, as $a^2 \equiv 1$ mod $p^e$ implies gcd$(a,p)=1$.]
Thus by the Chinese Remainder Theorem and the fact that $1 \not \equiv -1$ mod $p^e$ for all odd primes $p$ and all positive integers $e$, there are $2^{\ell}$ such elements $x \in (\mathbb{Z}/M\mathbb{Z})^{\times}$.
Now, for each integer $j \ge 3$ there are precisely 4 elements in $\mathbb{Z}/2^j\mathbb{Z}$ that square to 1; namely $\pm 1, \pm 1 +2^{j-1}$. What about $j=1$ and $j=2$? So finally, can you say, how many integers square to 1 in $\mathbb{Z}/N\mathbb{Z}$; $N$ an even integer?