# Prove lemma: order of $x\ \mathrm{mod}\ N$ is even with probability $1/2$

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.

• Hint 1: Well, if the order of $a \mod p$ for prime $p$ is $n$ and the order of $a \mod q$ for prime $q$ is $m$ then the order of $a \mod pq$ is the least common factor of $n$ and $m$. Hint 2: the non-zero equivalence classes modulo a prime form a cyclic group under multiplication. – fleablood Jul 19 '18 at 19:21
• Just checking: do you mean "least common multiple"? – J-J Jul 19 '18 at 19:32
• Yes I did mean multiple. – fleablood Jul 19 '18 at 21:54

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$.

• This is quite elegant. I'm just trying to figure out a rigorous argument for $-x$ having an even order. Do you have one? – J-J Jul 19 '18 at 19:49
• Yes, let me edit my answer to include a proof of that for you. – Myath Jul 19 '18 at 19:53
• @JyrkiLahtonen Thank you. I've replaced it with another claim that I think is correct this time. – Myath Jul 19 '18 at 20:29
• @Myath The last paragraph can be omitted: $-x$ having odd order leads to a contradiction, so the order must be even. – egreg Jul 19 '18 at 20:43
• @egreg You're right. I think it helps to see why the order is $2(2m+1)$ in addition to being even. – Myath Jul 19 '18 at 20:50