In the book Algorithms by Vazirani et al., a simple lemma is stated without proof:
Let $N$ be an odd composite, with at least two prime factors, and let $x$ be chosen uniformly at random between $0$ and $N-1$. If $\gcd(x,N)=1$, then with probability at least $1/2$, the order $r$ of $x \mod N$ is even.
Note: the order $r$ of $x$ modulo $N$ is the smallest positive integer $r$ such that $x^r \equiv 1\ \mathrm{mod}\ N$.
I've been trying to prove this, to no avail. The only hints I am given is that it may entail Fermat's Little Theorem or the Chinese Remainder Theorem.
A proof, a sketch of a proof, or even a reference to one would be appreciated.
Let $1 \le x \le N - 1$ and $\gcd(x, N) = 1$. If $x$ has odd order $2m+1$, then $-x$ has even order $2(2m+1)$. So for every odd-order $x$, there's a unique corresponding $-x$ of even order. So the number of even-order elements is at least half.
Proof that $-x$ has order $2(2m+1)$. This is a special case of the fact that if $a$ and $b$ are elements of an abelian group with order $m$ and $n$ respectively and $\gcd(m,n)=1$, then $ab$ has order $mn$.
Here is the proof of the order of $-x$. Let $n$ be the order of $-x$. Then $1 = (-x)^n = (-1)^nx^n$. Consider 2 cases: $n$ is odd or $n$ is even.
If $n$ is odd, then $x^n = -1$, $x^{2n} = 1$, which implies $2m+1$ divides $2n$, and hence $2m+1$ divides $n$. So $x^n = 1 = -x^n = -1$, which means $2 = 0 \mod N$. This is impossible since $N$ is odd.
If $n$ is even, then $1 = (-x)^n = x^n$, which implies that $2m+1$ divides $n$. Since $n$ is even, the smallest such $n$ is $2(2m+1)$. We verify that $(-x)^{2(2m+1)} = 1$.