# What is the order of $2$ in $(\mathbb{Z}/n\mathbb{Z})^\times$?

Is it there some theorem that makes a statement about the order of $2$ in the multiplicative group of integers modulo $n$ for general $n>2$?

-
The order is a divisor of $\phi(n)$. If $2$ is a square mod $n$, then the order is a divisor of $\phi(n)/2$. If the order is $n-1$, then $n$ is prime. – Hagen von Eitzen Mar 11 '13 at 12:46

Let me quote from this presentation of Carl Pomerance:

[...] the multiplicative order of $2 \pmod n$ appears to be very erratic and difficult to get hold of.

The presentation describes, however, some properties of this order. The basic facts have already been elucidated by @HagenvonEitzen in his comment.

-

As others have pointed out, this is not trivial in the slightest. There are a few things you can find out, as Hagen von Eitzen pointed out in the comments. I created the following plots for $n\in 1\ldots 1000,~~~~~ 1\ldots 10000, ~~~~~1\ldots 100000$.

There are certain things from this picture that are easy to make sense of, notably the highest line, which is $y = x-1$ and then the other prominent lines for small divisors of $n-1$. I am intrigued by the few points that lie between $n-1$ and $\frac{n-1}{2}$.

The first few elements of this appear to be: $$9,25,27,81,121,125,169,243,361,625,729,841...$$

Which are all powers of prime numbers, which makes sense. This is actually A108989, and these are those non-prime numbers $n$ for which the multiplicative order of $2$ modulo $n$ is $\phi(n)$.

I've also tallied the most common orders for the first $1,000,000$ odd integers and the first few were: $$\{2, 155171\}, \{4, 108716\}, \{8, 73643\}, \{12, 67834\}, \{6, 57771\}, \{1, 55868\}, \{16, 46866\}, \{24, 45317\}, \{48, 31026\}, \{32, 23299\}, \{36, 20669\}, \{96, 16278\}, \{72, 15858\}, \{20, 14476\}, \{10, 13413\}$$

See what you can make of that, it isn't in the OEIS.

-
See also the graph at math.stackexchange.com/questions/263243/… – Marc van Leeuwen Mar 11 '13 at 14:29

In general it is hard to say something about the order of an integer $a$ modulo $n$ (such that $a\neq -1$ or a perfect square) as $n$ varies. You may be interested to read about Artin's conjecture on primitive roots.

Essentially copied and pasted from the wikipedia article:

For example, take $a = 2$. The conjecture claims that the set of primes $p$ for which $2$ is a primitive root (i.e., those primes such that $2$ has the largest possible order modulo $p$, that is, $\text{ord}_p(2)= p-1$) has density $C_\text{Artin}=0.373955\ldots$. The set of such primes is (sequence A001122 in OEIS) $$S(2) = \{3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, ...\}.$$ It has $38$ elements smaller than $500$ and there are $95$ primes smaller than $500$. The ratio (which conjecturally tends to $C_\text{Artin}$) is $38/95 = 2/5 = 0.4$.

-