Number Orders

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 $a$ mod $n$ is the least positive number $k$ such that $a^{k} \equiv 1$ mod $n$.

But is the order of a number always defined?

No! When $gcd(a,n)=1$, the order of $a$ mod $n$ is always defined. When $gcd(a,n) \neq 1$, the order of $a$ mod $n$ 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.

Primitive Roots

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

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

The order of $3$ mod $7$ is illustrated below. Interact with the visual to learn the order of different numbers with respect to different moduli.