Consider $m$ to be odd and prime. And $A = \{0, 1, 2, ..., 2m-1\}$ is the set of all remainders modulo $2m$.

Question

Consider $m$ to be odd and prime. And $A = \{0, 1, 2, ..., 2m-1\}$ is the set of all remainders modulo $2m$. How many elements $x$ in $A$ satisfy $x^2 \equiv 1 \mod{2m}$?

Answer 1

The solutions to $x^2\equiv 1\pmod p$ are $x\equiv \pm1\pmod p$, the only solution to $x^2\equiv 1\pmod 2$ is $x\equiv 1\pmod 2$. By the Chinese Remainder Theorem, we conclude that the solutions modulo $2p$ and taken from $\{0,\ldots, 2p-1\}$ are $1$ and $2p-1$. Now we have to count the members of these residue classes in $\{0,\ldots,2m-1\}$.

If $m$ is a multiple of $p$, say $m=kp$, we obviously find $2k$ such numbers, namely $2jp+1$ for $0\le j<k$ and $2jp-1$ for $1\le j\le k$.

Otherwise, if $m=kp+r$, $0<k<p$, we have $2jp+1$ for $0\le j\le k$ and $2jp-1$ for $1\le j\le k$, so a total of $2k+1$ such numbers.

The general answer is thus $$ \left\lceil \frac mp\right\rceil+\left\lfloor \frac mp\right\rfloor. $$

Answer 2

Hint $ $ Apply the following with $\ p=m,\ q = 2\ $ and $\ b,c = x\pm1 $

Lemma $ $ If $\,p\nmid q\,$ are primes and $\,\color{#c00}{q\mid b\!-\!c}\,$ then $\ pq\mid bc\iff pq\mid b\,$ or $\,pq\mid c$

Proof $\,\ pq\mid bc\iff pq\mid b\,$ or $\,pq\mid c\,$ or $\,\smash[b]{\underbrace{p\mid b,\,\color{#c00}{q\mid c}}}\,$ or $\,p\mid c,\,q\mid b\ $ by unique factorization.

By hypothesis $\,\color{#c00}{q\mid b\!\iff\! q\mid c},\,$ therefore $\,{p\mid b,\, \color{#c00}{q\mid c}}\iff p\mid b,\color{#c00}{q\mid b}\iff pq\mid b$

Similarly, the final case is equivalent to $\,pq\mid c$