Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 8 down vote accepted

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.

share|cite|improve this answer

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

enter image description here

enter image description here

enter image description here

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.

share|cite|improve this answer
See also the graph at… – 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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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