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.

  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 19 '18 at 19:21
  • $\begingroup$ Just checking: do you mean "least common multiple"? $\endgroup$ – J-J Jul 19 '18 at 19:32
  • $\begingroup$ Yes I did mean multiple. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.