MaVS

Number Orders

Lesson
Visual

In modular arithmetic, the order of a number is roughly its size. A number's order can be thought of as how much that number can be multiplied by itself until it repeats. Formally, the order of a number aa mod nn is the least positive number kk such that ak1a^{k} \equiv 1 mod nn.

Trivial example: for any modulus,1111^1 \equiv 1 , so the order of 11 is 11.
Example: 3213^2 \equiv 1 mod 44, so the order of 33 mod 44 is 22.

But is the order of a number always defined?

No! When gcd(a,n)=1gcd(a,n)=1, the order of aa mod nn is always defined. When gcd(a,n)1gcd(a,n) \neq 1, the order of aa mod nn is never defined.

In the visual, a number's order is represented by the length of its cycle. Notice numbers coprime to the modulus are always a part of a cycle, while numbers that share a divisor with the modulus are not.

 Modulus:
 Multiplicative mapping:

Primitive Roots

When the order of some number aa mod nn is exactly ϕ(n)\phi(n), all numbers coprime to nn can be written as aka^k for some kZ.k \in \Z. In this case, we call aa a primitive root. Primitive roots of nn will thus generate ϕ(n)\phi(n) remainders mod nn. These ϕ(n)\phi(n) numbers are exactly all of the numbers coprime to nn.

So, a primitive root for some prime pp will generate all p1p-1 remainders coprime to pp. That is, the primitive root will generate every remainder 1,,p11, \ldots, p-1. Since a primitive root means that every number coprime to pp is a part of the same cycle, there will only be one color.

Example: what is the order of 33 mod 77?
PowerResult
313^133 mod 77
323^222 mod 77
333^366 mod 77
343^444 mod 77
353^555 mod 77
363^611 mod 77
Thus the order of 33 mod 77 is 66, which also means that 33 is a primitive root mod 77.

The order of 33 mod 77 is illustrated below. Interact with the visual to learn the order of different numbers with respect to different moduli.

 Modulus:
 Multiplicative mapping: