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 mod is the least positive number such that mod .
Trivial example: for any modulus, , so the order of is .
Example: mod , so the order of mod is .
But is the order of a number always defined?
No! When , the order of mod is always defined. When , the order of mod 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 mod is exactly , all numbers coprime to can be written as for some In this case, we call a primitive root. Primitive roots of will thus generate remainders mod . These numbers are exactly all of the numbers coprime to .
So, a primitive root for some prime will generate all remainders coprime to . That is, the primitive root will generate every remainder . Since a primitive root means that every number coprime to is a part of the same cycle, there will only be one color.
Example: what is the order of mod ?Thus the order of mod is , which also means that is a primitive root mod .
Power Result mod mod mod mod mod mod
The order of mod is illustrated below. Interact with the visual to learn the order of different numbers with respect to different moduli.
Modulus: | |||
Multiplicative mapping: |