Theorem
Let $N$ be a general odd number, which written as its prime factorisation is $N = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \dots {p_s}^{\alpha_s}$. If $x$ is chosen uniformly at random from $\mathbb{Z}^{*}_N$ (group of numbers coprime to $N$) and $r$ is the order of $x$ modulo N. Then \begin{equation} \mathbb{P} [r\text{ is even and }x^{r/2} \not\equiv -1 \text{ mod } N] \geq 1 - \frac{1}{2^{s}} \end{equation}
Proof
We need to show that, \begin{equation*} \mathbb{P} [r\text{ is odd or }x^{r/2} \equiv -1 \text{ mod } N] \leq \frac{1}{2^s} \end{equation*}
The Chinese remainder theorem states that $\mathbb{Z}^{*}_N \cong \mathbb{Z}^{*}_{{p_1}^{\alpha_1}} \times \mathbb{Z}^{*}_{{p_2}^{\alpha_2}} \times \dots \times \mathbb{Z}^{*}_{{p_s}^{\alpha_s}}$ from which we can deduce that choosing $x$ uniformly at random from $\mathbb{Z}^{*}_N$ is equivalent to choosing $x_i$ uniformly at random from $\mathbb{Z}^{*}_{{p_j}^{\alpha_j}}$.
Let $r_j$ be the order of $x_j$ modulo ${p_j}^{\alpha_j}$ and let $2^{m_j}$ be the largest power of $2$, which divides $r_j$. So $k_j 2^{m_j} = r_j$ and $k_j$ odd.
Assume that $r$ is odd, which implies that $r_j$ must be odd for each $j$ (so $m_j = 0$), which occurs with probability $2^{-s}$ (from a previous result).
Now assume that $r$ is even, but $x^{r/2} \equiv -1 \text{ mod } N$. Then $x^{r/2} \equiv -1 \text{ mod } {p_j}^{\alpha_j}$. This implies that $r_j$ does not divide $\dfrac{r}{2}$, to see this suppose $r_j \Big| \dfrac{r}{2} \implies cr_j = \dfrac{r}{2}$ and therefore $x_j^{r/2} \equiv x_{j}^{cr_j} \equiv (x_{j}^{r_j})^c \equiv 1 \text{ mod } {p_j}^{\alpha_j} \not\equiv -1 \text{ mod } {p_j}^{\alpha_j}$ giving a contradiction.
Therefore we must have that all $m_j$ are equal to a common value $m$.
It is proving this final statement where I am stuck. The notes, which I am using say;
"Because $r_j$ all divide $r$ and in fact $r$ is a common multiple of the $r_j$, so if one of the $m_j$ has an extra power of $2$ removing this the others should still divide $\dfrac{r}{2}$. But we have shown this is not true."
My Attempt of a Proof (WLOG $r_1$ has extra power of $2$) \begin{align*} r &= c r_1 r_2 \dots r_s \text{(since r is common multiple)}\\ r &= c (k_1 2^{m+1}) r_2 \dots r_s \\ \dfrac{r}{2} &= c (k_1 2^{m}) r_2 \dots r_s \end{align*} and therefore $r_j, \Big| \dfrac{r}{2}$ for $j = 2 \dots s$ the contradiction.
However, surely we can repeat this proof when all $m_j$ are equal an obtain the same contradiction? So where I am going wrong?
When you write $$r = c r_1 r_2 \cdots r_s \quad \text{(since r is common multiple)}$$ $c$ is not generally an integer, so it doesn't follow directly from $$ \frac{r}{2} = c (k_1 2^{m_1-1})r_2\cdots r_s $$ that $r_2\mid \frac{r}{2}$. It also relies on the facts that $2^{m_1}\mid r$ and $m_1>m_2$ (the last only being true WLOG when not all $m_j$ are equal).
If all $m_i=m_2$ then $2^{m_2}$ is the highest power of $2$ that divides the least common multiple of the $r_i$ and so may be the highest power of $2$ that divides $r$ (which may be any common multiple, possibly the LCM), in which case $r_2\not \mid \frac{r}{2}$. It is only guaranteed that $r_2 \mid \frac{r}{2}$ if $m_i>m_2$ for some $i$.
To illustrate, consider $N=13\times 29\times 53$ and $x=2$ whence $$ p_1=13,p_2=29,p_3=53 \\ r_1=12,r_2=28,r_3=52 \\ m_1=m_2=m_3=2 \\ r = \frac{1}{16} r_1 r_2 r_3 $$ The highest power of $2$ that divides $r$ is $2^2$ and none of $r_1,r_2,r_3$ divides $r/2$.