PrevNext

Overview

The order of an element modulo nn is a way to measure how quickly powers repeat back to 11.

For example, modulo 77,

31≡3,3^1\equiv 3,
32≡2,3^2\equiv 2,
33≡6,3^3\equiv 6,
34≡4,3^4\equiv 4,
35≡5,3^5\equiv 5,
36≡1.3^6\equiv 1.

So the powers of 33 first return to 11 at exponent 66.

We say that the order of 33 modulo 77 is 66.

Definition

Let aa and nn be positive integers with

gcd⁡(a,n)=1.\gcd(a,n)=1.

The order of aa modulo nn, written

ord⁡n(a),\operatorname{ord}_n(a),

is the smallest positive integer kk such that

ak≡1(modn).a^k\equiv 1 \pmod n.

The condition

gcd⁡(a,n)=1\gcd(a,n)=1

is important. If aa is not relatively prime to nn, then the powers of aa may never become congruent to 11 modulo nn.

Motivation

Suppose we want to find the remainder of

21002^{100}

modulo 77.

Instead of computing the power directly, we look for a cycle.

Modulo 77,

21≡2,2^1\equiv 2,
22≡4,2^2\equiv 4,
23≡8≡1.2^3\equiv 8\equiv 1.

So

ord⁡7(2)=3.\operatorname{ord}_7(2)=3.

This means powers of 22 repeat every 33 exponents modulo 77.

Since

100≡1(mod3),100\equiv 1 \pmod 3,

we get

2100≡21≡2(mod7).2^{100}\equiv 2^1\equiv 2 \pmod 7.

The order turns a large exponent into a small one.

Basic Properties

If

ord⁡n(a)=d,\operatorname{ord}_n(a)=d,

then

ad≡1(modn).a^d\equiv 1 \pmod n.

Also,

am≡1(modn)a^m\equiv 1 \pmod n

if and only if

d∣m.d\mid m.

This is one of the most useful facts about order.

Why This Is True

Suppose

m=qd+r,m=qd+r,

where

0≤r<d.0\le r<d.

Then

am=aqd+r=(ad)qar.a^m=a^{qd+r}=(a^d)^q a^r.

Since

ad≡1(modn),a^d\equiv 1 \pmod n,

we get

am≡ar(modn).a^m\equiv a^r \pmod n.

If

am≡1(modn),a^m\equiv 1 \pmod n,

then

ar≡1(modn).a^r\equiv 1 \pmod n.

But dd was the smallest positive exponent giving 11. Therefore,

r=0.r=0.

So

d∣m.d\mid m.

Connection to Euler's Theorem

Euler's Theorem says that if

gcd⁡(a,n)=1,\gcd(a,n)=1,

then

aφ(n)≡1(modn).a^{\varphi(n)}\equiv 1 \pmod n.

Therefore, the order of aa modulo nn must divide

φ(n).\varphi(n).

So

ord⁡n(a)∣φ(n).\operatorname{ord}_n(a)\mid \varphi(n).

This gives a powerful way to find the order: instead of testing every exponent, we only test divisors of φ(n)\varphi(n).

For a prime pp, we have

φ(p)=p−1.\varphi(p)=p-1.

So if pp is prime and p∤ap\nmid a, then

ord⁡p(a)∣p−1.\operatorname{ord}_p(a)\mid p-1.

Finding the Order

To find

ord⁡n(a),\operatorname{ord}_n(a),

use the following method:

  1. Check that gcd⁡(a,n)=1\gcd(a,n)=1.
  2. Compute φ(n)\varphi(n), if useful.
  3. List possible divisors of φ(n)\varphi(n).
  4. Test powers of aa until the first one congruent to 11 appears.

The smallest valid exponent is the order.

Worked Examples

Example 1

Find ord⁡7(3)\operatorname{ord}_7(3).

Compute powers of 33 modulo 77:

31≡3(mod7),3^1\equiv 3 \pmod 7,
32≡9≡2(mod7),3^2\equiv 9\equiv 2 \pmod 7,
33≡6(mod7),3^3\equiv 6 \pmod 7,
34≡18≡4(mod7),3^4\equiv 18\equiv 4 \pmod 7,
35≡12≡5(mod7),3^5\equiv 12\equiv 5 \pmod 7,
36≡15≡1(mod7).3^6\equiv 15\equiv 1 \pmod 7.

The first exponent that gives 11 is 66.

Therefore,

ord⁡7(3)=6.\operatorname{ord}_7(3)=6.

Example 2

Find ord⁡15(2)\operatorname{ord}_{15}(2).

Since

gcd⁡(2,15)=1,\gcd(2,15)=1,

the order exists.

Now compute:

21≡2(mod15),2^1\equiv 2 \pmod{15},
22≡4(mod15),2^2\equiv 4 \pmod{15},
23≡8(mod15),2^3\equiv 8 \pmod{15},
24≡16≡1(mod15).2^4\equiv 16\equiv 1 \pmod{15}.

Thus

ord⁡15(2)=4.\operatorname{ord}_{15}(2)=4.

Example 3

Find the remainder when 520265^{2026} is divided by 1313.

First find the order of 55 modulo 1313.

Compute:

51≡5(mod13),5^1\equiv 5 \pmod{13},
52≡25≡−1(mod13).5^2\equiv 25\equiv -1 \pmod{13}.

Therefore,

54≡1(mod13).5^4\equiv 1 \pmod{13}.

Since 52≢1(mod13)5^2\not\equiv 1 \pmod{13}, the order is

ord⁡13(5)=4.\operatorname{ord}_{13}(5)=4.

Now reduce the exponent:

2026≡2(mod4).2026\equiv 2 \pmod 4.

So

52026≡52≡−1≡12(mod13).5^{2026}\equiv 5^2\equiv -1 \equiv 12 \pmod{13}.

The remainder is

12.12.

Common Use in Contest Problems

Order is especially useful when a problem involves:

  • Large powers modulo nn
  • Divisibility of expressions like am−1a^m-1
  • Repeating units digits
  • Remainders with prime moduli
  • Equations involving exponents

For example, if

am≡1(modn),a^m\equiv 1 \pmod n,

then

ord⁡n(a)∣m.\operatorname{ord}_n(a)\mid m.

This often turns a modular equation into a divisibility condition.

Key Contest Insight

The order of aa modulo nn is the period of the powers of aa modulo nn.

Once you know the order, large exponents can be reduced modulo that order.

The most important fact is

am≡1(modn)⟺ord⁡n(a)∣m.a^m\equiv 1 \pmod n \quad\Longleftrightarrow\quad \operatorname{ord}_n(a)\mid m.

Strategy Tips

  • Always check that gcd⁡(a,n)=1\gcd(a,n)=1
  • For prime moduli, remember that the order divides p−1p-1
  • For general moduli, the order divides φ(n)\varphi(n)
  • Test divisors of φ(n)\varphi(n) from smallest to largest
  • Once the order is known, reduce exponents modulo the order
  • If the exponent leaves remainder 00, use the power corresponding to the full cycle

Common Pitfalls

  • Forgetting that the order may not exist if gcd⁡(a,n)≠1\gcd(a,n)\neq 1
  • Assuming the order is always φ(n)\varphi(n)
  • Testing exponents randomly instead of using divisors of φ(n)\varphi(n)
  • Reducing the base incorrectly
  • Forgetting that the order is the smallest positive exponent giving 11

Practice Problems

StatusSourceProblem NameDifficultyTags

Module Progress:

Join the Discord Community!

Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.

PrevNext