12
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Hagen von Eitzen Mar 11 '13 at 12:46
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.