Consider $m$ to be odd and prime. And $A = \{0, 1, 2, ..., 2m-1\}$ is the set of all remainders modulo $2m$. 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}$?
 A: 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.  $$
A: 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$
