Number Theory • Topic 17

Order Modulo n

The order of an integer modulo $n$ measures "how long it takes" for its powers to cycle back to 1. This concept underpins primitive roots and cryptography.

Definition

Definition (Order)

Let

a

and

n

be coprime integers (

n > 1

). The multiplicative order of

a

modulo

n

, denoted

ord_{n} (a)

, is the smallest positive integer

k

such that:

a^{k} \equiv 1 (mod n)

Existence

The order exists if and only if

g cd (a, n) = 1

By Euler's Theorem, $a^{ϕ (n)} \equiv 1 (mod n)$ , so the set of such $k$ is non-empty. The order is the smallest element of this set.

Properties

1. Divisibility of Order

a^{m} \equiv 1 (mod n)

, then

ord_{n} (a)

divides

m

Corollary: $ord_{n} (a)$ always divides $ϕ (n)$ .

2. Powers

ord_{n} (a^{k}) = \frac{ord _{n} ( a )}{g c d ( k , ord _{n} ( a ))}

3. Primitive Roots

ord_{n} (a) = ϕ (n)

, then

a

is called a primitive root modulo

n

Practice Problems

Exercise (Problem 1)

Find the order of 2 modulo 7.

Exercise (Problem 2)

Prove that if

ord_{n} (a) = hk

, then

ord_{n} (a^{h}) = k

Exercise (Problem 3)

Let

p

be an odd prime. If

a

has order 3 modulo

p

, prove that

1 + a + a^{2} \equiv 0 (mod p)