# 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$.

Trivial example: for any modulus,$1^1 \equiv 1$ , so the order of $1$ is $1$.

Example: $3^2 \equiv 1$ mod $4$, so the order of $3$ mod $4$ is $2$.

## 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.

Modulus: | |||

Multiplicative mapping: |

## 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.

Example: what is the order of $3$ mod $7$?Thus the order of $3$ mod $7$ is $6$, which also means that $3$ is a

Power Result $3^1$ $3$ mod $7$ $3^2$ $2$ mod $7$ $3^3$ $6$ mod $7$ $3^4$ $4$ mod $7$ $3^5$ $5$ mod $7$ $3^6$ $1$ mod $7$ primitive rootmod $7$.

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.

Modulus: | |||

Multiplicative mapping: |