Orbits, Orders and Primitive Roots

Six chairs, six people, one rule#

Six people sit in chairs numbered 1 to 6. A bell rings, and everyone moves by the same rule: the person in chair x moves to chair 3x, wrapped around mod 7. (“Mod 7” means take the remainder after dividing by 7.)

Does everyone get a chair? Does anyone collide? That question, asked carefully, is the whole topic.

The map x ↦ 3x mod 7#

The arrow ↦ is read “goes to”. Here is where everyone moves:

Every chair from 1 to 6 appears exactly once in the bottom row. No two people collide, so the map is injective (one-to-one). No chair is left empty, so it is surjective (onto). Both together make it a bijection. A bijection from a set to itself is also called a permutation of that set.

Why it is a bijection, and when it is not#

Suppose two chairs x and y were sent to the same place: 3x ≡ 3y (mod 7). Then 7 divides 3(x − y). Since 7 is prime and does not divide 3, it must divide x − y. With x and y both between 1 and 6, that forces x = y. So no collisions are possible.

The key fact was that 3 and 7 share no common factor. Change that and the map breaks. Try x ↦ 2x mod 8 on {0, 1, …, 7}: 2 · 0 = 0 and 2 · 4 = 8 ≡ 0. Two inputs collide, and the outputs are only 0, 2, 4, 6. Half the chairs stay empty.

Following one number around: its orbit#

Now keep ringing the bell. Watch one person only. The list of chairs they visit is called the orbit.

Start at 1 and multiply by 3 each time, mod 7:

1 → 3 → 2 → 6 → 4 → 5 → 1.

After six steps they are back where they started. On a finite set an orbit must eventually repeat, because there are only so many chairs. As a set the orbit is {1, 2, 3, 4, 5, 6}: this person visits every chair.

Written with powers, the chairs visited from 1 are 3¹, 3², 3³, … mod 7. The notation f²(x) means f(f(x)), the rule applied twice. It is not a square.

The multiplicative order#

The number of steps before you first return to 1 is called the multiplicative order of a mod p. It is the smallest positive k with a^k ≡ 1 (mod p).

Two quick ones by hand. For a = 2: 2, 4, 8 ≡ 1, so the order is 3. For a = 3: notice 3³ = 27 ≡ 6 ≡ −1, so 3⁶ ≡ (−1)² = 1, and the order is 6.

Look at the orders: 1, 3, 6, 3, 6, 2. Every one divides 6 = p − 1. That is no accident. Fermat’s little theorem says a^p−1 ≡ 1, and the powers of a repeat with period equal to the order, so the order must divide p − 1.

Primitive roots#

A number g is a primitive root mod p when its orbit visits every chair: the powers g, g², …, g^p−1 give all of 1, 2, …, p − 1. Equivalently, the order of g is p − 1, as large as possible.

• 3 is a primitive root of 7. Its powers are 3, 2, 6, 4, 5, 1: all six.
• 2 is not. Its powers are 2, 4, 1, and then they repeat. The chairs 3, 5 and 6 are never visited.

Mod 7 the primitive roots are exactly 3 and 5. Being prime does not make a number a primitive root (2 is prime and fails), and Fermat’s a^p−1 ≡ 1 holds for every a, so it cannot pick out primitive roots either.

The lecture’s homework, mod 11. The map x ↦ 5x mod 11 is a bijection on {1, …, 10} because gcd(5, 11) = 1. (You can even undo it: 5 · 9 = 45 ≡ 1, so multiplying by 9 reverses it.) For a primitive root, try 2: its powers mod 11 are 2, 4, 8, 5, 10, 9, 7, 3, 6, 1. All ten appear before the first 1, so 2 is a primitive root of 11.

Where this goes wrong#

• Forgetting to reduce. 2 · 4 = 8, and 8 must be written as 1 mod 7. Leaving it as 8 makes the orbit look longer than it is.
• Counting the start twice. The orbit 1 → 2 → 4 → 1 has three elements, not four.
• Assuming every map x ↦ ax is a bijection. Only when gcd(a, n) = 1. Check 2x mod 8.
• Mixing up order and primitive root. Every a has an order. Only the ones with order p − 1 are primitive roots.
• Reading f²(x) as a square. It means apply f twice.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.