Suppose $N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m}$ is the prime factorization of an odd composite positive integer. Let $x$ is chosen uniformly at random from $\mathbb{Z}_N^*$, and $r$ be the order of $x$ modulo $N$. Then
$$
Pr(r\text{ is even and }x^{r/2}\neq -1\pmod{N})\geq 1-\frac{1}{2^m}
$$
or equivalently,$$
Pr(r\text{ is odd or }x^{r/2}= -1\pmod{N})\leq \frac{1}{2^m}
$$
By the Chinese Remainder theorem, choosing $x$ uniformly at random from $\mathbb{Z}_N^*$ is equivalent to choosing $x_j$ independently and uniformly at random from $\mathbb{Z}_{p_j^{\alpha_j}}^*$ such that $x=x_j(mod\;{p_j^{\alpha_j}})$ for each $j$.
Let, $r_j$ be the order of $x_j$ modulo $p_j^{\alpha_j}$, Let $2^{d_j}$ be the largest power of $2$ that divides $r_j$, $2^{d}$ be the largest power of $2$ that divides $r$.
Lemma : Let $p$ be an odd prime. Let $2^{d'}$ be the largest power of $2$ dividing $\phi(p^\alpha)$. Then with probability exactly one half $2^{d'}$ divides the order modulo $p^\alpha$ of a randomly chosen element of $\mathbb{Z}_{p^\alpha}^*.$
$$
Pr(2^{d'}|r)=Pr(2^{d'}\nmid r)=\frac{1}{2}
$$
Part 1
$r$ is odd then all $r_i$ are odd. $Pr(r_i\text{ is odd})\leq \frac{1}{2}$. Since the $x_i$ are chosen independently then $Pr(r\text{ is odd})\leq \frac{1}{2^m}$
$$
x^r=1\pmod{N}\implies x^r=1\pmod{p_i^{\alpha_i}}\\
x=x_i\pmod{p_i^{\alpha_i}}\implies x^r=x^r_i\pmod{p_i^{\alpha_i}}\\
\implies x^r_i=1\pmod{p_i^{\alpha_i}}\\
\implies r_i|r
$$
$\therefore$ If $r$ is odd then all $r_i$ are odd. From Lemma, $2^{d'}$ divides the group $\mathbb{Z}^*_{p_i^{\alpha_i}}$ into two sets : 1) $2^{d'}|r$ 2) $2^{d'}\nmid r$
Odd $r_i$ does not fall in the set 1 and not all elements in set 2 are odd, therefore the probability of obtaining odd $r_i$ is less than $1/2$, which proves the claim.
Part 2
If $r$ is even and $x^{r/2}=-1\pmod{N}$ then all the $r_i$ can be expressed as $2^d (odd\#)$ for some fixed $d$ and $Pr(r_i=2^d (odd\#))\leq 1/2$
$r$ is even and
$$
x^{r/2}=-1\pmod{N})\implies x^{r/2}=-1\pmod{p_i^{\alpha_i}}\\
x=x_i\pmod{p_i^{\alpha_i}}\implies x_i^{r/2}=-1\pmod{ p_i^{\alpha_i}}\\
\implies r_i|r\quad\&\quad r_i\nmid r/2\\
$$
As defined, $r_i=2^{d_i}(odd\;\#)=2^{d_i}\times \mathcal{O}_1$ and $r=2^d(odd\;\#)=2^d\times \mathcal{O}_2$
$$
r_i|r\implies d_i\leq d\\
r_i\nmid r/2\implies d_i>d-1\Longleftrightarrow d_i\geq d\\
\therefore d_i=d\quad \forall\quad i\\
i.e., r_i=2^d(odd\;\#)=2^{d}\times \mathcal{O}_1
$$
How do I proceed further making use of Lemma and prove the claim in part two and show that $Pr(r\text{ is even and }x^{r/2}\neq -1\pmod{N})\leq \frac{1}{2^m}$ ?
For Actual reference :
Best Answer
Lemma implies that exactly half the elements of $\mathbb{Z}^*_{p_j^{\alpha_j}}$ have $d_j=d'$ where $d'$ is the largest power of $2$ dividing $\phi({p_j^{\alpha_j}})$, i.e., $P$($d_j=d'$) $=1/2$
Therefore, $P$($d_j=$ any particular value) $\leq 1/2$
From part 2, when $r$ is odd then $r_j|r$ for each $j$ and this implies $r_j$ is odd.$\implies d_j=0$ for all $j$.
This concludes, when $r$ is odd or $x^{r/2}=-1\pmod{N}$ the value of $d_j$ is the same for all $j$.
Since $P$($d_j=$ any particular value) $\leq 1/2$ we can obtain
$P(r\text{ is odd or }x^{r/2}=-1\pmod{N})\leq1/2^m$