Overview
The order of an element modulo is a way to measure how quickly powers repeat back to .
For example, modulo ,
So the powers of first return to at exponent .
We say that the order of modulo is .
Definition
Let and be positive integers with
The order of modulo , written
is the smallest positive integer such that
The condition
is important. If is not relatively prime to , then the powers of may never become congruent to modulo .
Motivation
Suppose we want to find the remainder of
modulo .
Instead of computing the power directly, we look for a cycle.
Modulo ,
So
This means powers of repeat every exponents modulo .
Since
we get
The order turns a large exponent into a small one.
Basic Properties
If
then
Also,
if and only if
This is one of the most useful facts about order.
Why This Is True
Suppose
where
Then
Since
we get
If
then
But was the smallest positive exponent giving . Therefore,
So
Connection to Euler's Theorem
Euler's Theorem says that if
then
Therefore, the order of modulo must divide
So
This gives a powerful way to find the order: instead of testing every exponent, we only test divisors of .
For a prime , we have
So if is prime and , then
Finding the Order
To find
use the following method:
- Check that .
- Compute , if useful.
- List possible divisors of .
- Test powers of until the first one congruent to appears.
The smallest valid exponent is the order.
Worked Examples
Example 1
Find .
Compute powers of modulo :
The first exponent that gives is .
Therefore,
Example 2
Find .
Since
the order exists.
Now compute:
Thus
Example 3
Find the remainder when is divided by .
First find the order of modulo .
Compute:
Therefore,
Since , the order is
Now reduce the exponent:
So
The remainder is
Common Use in Contest Problems
Order is especially useful when a problem involves:
- Large powers modulo
- Divisibility of expressions like
- Repeating units digits
- Remainders with prime moduli
- Equations involving exponents
For example, if
then
This often turns a modular equation into a divisibility condition.
Key Contest Insight
The order of modulo is the period of the powers of modulo .
Once you know the order, large exponents can be reduced modulo that order.
The most important fact is
Strategy Tips
- Always check that
- For prime moduli, remember that the order divides
- For general moduli, the order divides
- Test divisors of from smallest to largest
- Once the order is known, reduce exponents modulo the order
- If the exponent leaves remainder , use the power corresponding to the full cycle
Common Pitfalls
- Forgetting that the order may not exist if
- Assuming the order is always
- Testing exponents randomly instead of using divisors of
- Reducing the base incorrectly
- Forgetting that the order is the smallest positive exponent giving
Practice Problems
| Status | Source | Problem Name | Difficulty | Tags | ||
|---|---|---|---|---|---|---|
Module Progress:
Join the Discord Community!
Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.
