Finding $x$ that makes $x^2 ≡ 1 (\mathrm{mod} \ n)$, when $n$ is a composite number

Question

How do I find $x$, $( x > 1)$, that makes $x^2≡1 (\mathrm{mod} \ n)$, for any natural number $n$?

Answer 1

If $p\neq 2$ is prime then

$$x^2 \equiv 1 \pmod{p^k} \Leftrightarrow p^k |(x-1)(x+1) \,.$$

As $\gcd(x+1,x+1)|2$, and $p \neq 2$, we have $p^k |(x-1)(x+1) \Leftrightarrow p^k | x-1$ or $p^k |x+1$.

If $p=2$ then $2^k |(x-1)(x+1)$ if and only if $2^{k-1}|(x-1)$ or $2^{k-1}|x+1$. This fact follows immediately from the observation that if $x^2-1$ is even, then both $x+1, x-1$ are even and $\gcd(x-1,x+1)=2$.

let $n=p_1^{k_1}....p_k^{k_k}$.

Case 1 n is odd, or n is even but not multiple of $4$. Then $x^2=1 \pmod n$ if and only if $$x \equiv \pm 1 \pmod{p_i^{k_i}} \,;\, \forall 1 \leq i \leq k \,.$$

There are 2 possibilities for each prime; thus by the Chinese Remainder Theorem you get $2^k$ possible $x$. There are $2^k-1$ solutions $x \neq 1 \pmod{n}$ in this case.

Case 2 n is multiple of 4. WLOG $p_1=2$. Then $x^2=1 \pmod n$ if and only if $$x \in \{ \pm 1 ; \pm 1 + 2^{k_1-1} \} \pmod{2^{k_1}} \,.$$ $$x \equiv \pm 1 \pmod{p_i^{k_i}} \,;\, \forall 2 \leq i \leq k \,.$$

There are 4 possibilities for $2$ and 2 possibilities for each prime; thus by the Chinese Remainder Theorem you get $2^{k+1}$ possible $x$. There are $2^{k+1}-1$ solutions $x \neq 1 \pmod{n}$ in this case.

Answer 2

If $x^2 = 1 \mod n$, then $x^2 - 1 = 0\mod n$, so that $(x+1)(x-1) = 0\mod n$.

So given $n$, you need to find $x$ such that either

• $x = 1\mod n$, or
• $x = n-1\mod n$, or
• $x+1$ and $x-1$ are complementary factors of $n$.