Number TheoryDifficulty 50-958 tagged problems

Orders Modulo n

Orders Modulo n is the habit of using the period of powers modulo n to control cycles and exponent equations. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\operatorname{ord}_n(a) = \min\{ k \ge 1 : a^k \equiv 1 \pmod{n} \}, \qquad a^m \equiv 1 \iff \operatorname{ord}_n(a) \mid m$$

The order of $a$ mod $n$ is how long it takes powers of $a$ to cycle back to $1$, and any exponent giving $1$ must be a multiple of that order.

Why It Works

1
Let $d = \operatorname{ord}_n(a)$ (it exists when $\gcd(a,n)=1$, since $a^{\varphi(n)} \equiv 1$).
2
If $a^m \equiv 1$, divide $m = qd + r$ with $0 \le r < d$; then $a^r = a^{m - qd} \equiv a^m (a^d)^{-q} \equiv 1 \pmod n$.
3
Minimality of $d$ forces $r = 0$, so $d \mid m$.
4
In particular $d \mid \varphi(n)$, which narrows the order to a divisor of $\varphi(n)$.

Worked Examples

Example 1

Find the order of $2$ modulo $7$, and use it to find $2^{2026} \bmod 7$.

1
Powers of $2$: $2^1 = 2$, $2^2 = 4$, $2^3 = 8 \equiv 1 \pmod 7$.
2
The smallest exponent giving $1$ is $3$, so $\operatorname{ord}_7(2) = 3$.
3
Reduce the exponent mod $3$: $2026 = 3 \cdot 675 + 1$, so $2^{2026} \equiv 2^{1} \pmod 7$.
4
Therefore $2^{2026} \equiv 2 \pmod 7$.

Answer:

Order $3$; $2^{2026} \equiv 2 \pmod 7$.

Warm-up

Find the order of $2$ modulo $31$.

1
Since $31$ is prime, $\operatorname{ord}_{31}(2)$ divides $\varphi(31) = 30$, so the order is one of $1,2,3,5,6,10,15,30$.
2
Compute small powers: $2^5 = 32 \equiv 1 \pmod{31}$.
3
No smaller divisor works ($2^1 = 2$, and the only divisor of $5$ below $5$ is $1$), so the smallest exponent giving $1$ is $5$.
4
Therefore $\operatorname{ord}_{31}(2) = 5$.

Answer:

$5$

Contest level

Find the smallest prime $p$ for which $\operatorname{ord}_p(10) = 3$, i.e. the smallest prime $p$ such that the decimal $\tfrac{1}{p}$ repeats with period exactly $3$.

1
$\operatorname{ord}_p(10) = 3$ means $10^3 \equiv 1 \pmod p$ but $10^1 \not\equiv 1$, so $p \mid 10^3 - 1 = 999$ while $p \nmid 10 - 1 = 9$.
2
Factor $999 = 3^3 \cdot 37$. The prime factors are $3$ and $37$.
3
Discard $p = 3$: it divides $10 - 1 = 9$, so $\operatorname{ord}_3(10) = 1$, not $3$.
4
That leaves $p = 37$. Check $37 \nmid 9$, so the order divides $3$ but is not $1$, forcing $\operatorname{ord}_{37}(10) = 3$. Indeed $\tfrac{1}{37} = 0.\overline{027}$.

Answer:

$p = 37$

Olympiad / Challenge

Let $p$ be an odd prime. Prove that every prime divisor $q$ of $2^p - 1$ satisfies $q \equiv 1 \pmod{p}$ (hence $q \equiv 1 \pmod{2p}$).

1
Let $q$ be a prime with $q \mid 2^p - 1$, so $2^p \equiv 1 \pmod q$. Let $d = \operatorname{ord}_q(2)$; then $d \mid p$.
2
Since $p$ is prime, $d = 1$ or $d = p$. But $d = 1$ would mean $2 \equiv 1 \pmod q$, i.e. $q \mid 1$, impossible. So $d = p$.
3
By Fermat, $2^{q-1} \equiv 1 \pmod q$, so $d \mid (q - 1)$, i.e. $p \mid (q - 1)$, giving $q \equiv 1 \pmod p$.
4
Finally $q$ is odd (it divides the odd number $2^p - 1$), so $q \equiv 1 \pmod 2$; combined with $q \equiv 1 \pmod p$ and $\gcd(2,p)=1$, the CRT gives $q \equiv 1 \pmod{2p}$.

Answer:

Every prime factor $q$ of $2^p - 1$ satisfies $q \equiv 1 \pmod{2p}$.

Going Deeper

Generalization: the order $\operatorname{ord}_n(a)$ always divides $\varphi(n)$ (and divides the Carmichael $\lambda(n)$, the true universal exponent). An element whose order equals $\varphi(n)$ is a primitive root; primitive roots exist exactly for $n = 1, 2, 4, p^k, 2p^k$ with $p$ an odd prime. The key lemma $a^m \equiv 1 \iff \operatorname{ord}_n(a) \mid m$ is what makes 'find all exponents' problems finite.
Where it appears: the period of a repeating decimal $\tfrac1p$ equals $\operatorname{ord}_p(10)$; proving prime factors of $a^n - 1$ or Mersenne/Fermat numbers lie in fixed residue classes; pinning down the order of $2$ to bound divisors; and reducing astronomically large exponents to their residue modulo the order.
Pitfall: to reduce the exponent of $a^E \bmod n$, reduce $E$ modulo $\operatorname{ord}_n(a)$ — NOT modulo $\varphi(n)$ (which is only an upper bound) and never modulo $n$. Also, $a^m \equiv 1$ forces $\operatorname{ord}_n(a) \mid m$, but $a^m \equiv -1$ does NOT mean the order divides $m$; it means the order divides $2m$ but not $m$, so the order is even and equals $2 \cdot (\text{order of } a^? )$ — handle the $-1$ case separately.

Spot the Signal

Look for problems where the key step is using the period of powers modulo n to control cycles and exponent equations.
You can describe the hard part as using the period of powers modulo n to control cycles and exponent equations, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for orders modulo n, then rewrite the givens around it.
Name the relation that makes Orders Modulo n legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Orders Modulo n just because the surface looks familiar; verify the required condition first.
Applying Orders Modulo n because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let orders modulo n reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using the period of powers modulo n to control cycles and exponent equations.

Back to techniques

Number TheoryDifficulty 50-958 tagged problems

Orders Modulo n

Practice this technique Match my level

The Key Result

$$\operatorname{ord}_n(a) = \min\{ k \ge 1 : a^k \equiv 1 \pmod{n} \}, \qquad a^m \equiv 1 \iff \operatorname{ord}_n(a) \mid m$$

The order of $a$ mod $n$ is how long it takes powers of $a$ to cycle back to $1$, and any exponent giving $1$ must be a multiple of that order.

Why It Works

1
Let $d = \operatorname{ord}_n(a)$ (it exists when $\gcd(a,n)=1$, since $a^{\varphi(n)} \equiv 1$).
2
If $a^m \equiv 1$, divide $m = qd + r$ with $0 \le r < d$; then $a^r = a^{m - qd} \equiv a^m (a^d)^{-q} \equiv 1 \pmod n$.
3
Minimality of $d$ forces $r = 0$, so $d \mid m$.
4
In particular $d \mid \varphi(n)$, which narrows the order to a divisor of $\varphi(n)$.

Worked Examples

Example 1

Find the order of $2$ modulo $7$, and use it to find $2^{2026} \bmod 7$.

1
Powers of $2$: $2^1 = 2$, $2^2 = 4$, $2^3 = 8 \equiv 1 \pmod 7$.
2
The smallest exponent giving $1$ is $3$, so $\operatorname{ord}_7(2) = 3$.
3
Reduce the exponent mod $3$: $2026 = 3 \cdot 675 + 1$, so $2^{2026} \equiv 2^{1} \pmod 7$.
4
Therefore $2^{2026} \equiv 2 \pmod 7$.

Answer:

Order $3$; $2^{2026} \equiv 2 \pmod 7$.

Warm-up

Find the order of $2$ modulo $31$.

1
Since $31$ is prime, $\operatorname{ord}_{31}(2)$ divides $\varphi(31) = 30$, so the order is one of $1,2,3,5,6,10,15,30$.
2
Compute small powers: $2^5 = 32 \equiv 1 \pmod{31}$.
3
No smaller divisor works ($2^1 = 2$, and the only divisor of $5$ below $5$ is $1$), so the smallest exponent giving $1$ is $5$.
4
Therefore $\operatorname{ord}_{31}(2) = 5$.

Answer:

$5$

Contest level

Find the smallest prime $p$ for which $\operatorname{ord}_p(10) = 3$, i.e. the smallest prime $p$ such that the decimal $\tfrac{1}{p}$ repeats with period exactly $3$.

1
$\operatorname{ord}_p(10) = 3$ means $10^3 \equiv 1 \pmod p$ but $10^1 \not\equiv 1$, so $p \mid 10^3 - 1 = 999$ while $p \nmid 10 - 1 = 9$.
2
Factor $999 = 3^3 \cdot 37$. The prime factors are $3$ and $37$.
3
Discard $p = 3$: it divides $10 - 1 = 9$, so $\operatorname{ord}_3(10) = 1$, not $3$.
4
That leaves $p = 37$. Check $37 \nmid 9$, so the order divides $3$ but is not $1$, forcing $\operatorname{ord}_{37}(10) = 3$. Indeed $\tfrac{1}{37} = 0.\overline{027}$.

Answer:

$p = 37$

Olympiad / Challenge

Let $p$ be an odd prime. Prove that every prime divisor $q$ of $2^p - 1$ satisfies $q \equiv 1 \pmod{p}$ (hence $q \equiv 1 \pmod{2p}$).

1
Let $q$ be a prime with $q \mid 2^p - 1$, so $2^p \equiv 1 \pmod q$. Let $d = \operatorname{ord}_q(2)$; then $d \mid p$.
2
Since $p$ is prime, $d = 1$ or $d = p$. But $d = 1$ would mean $2 \equiv 1 \pmod q$, i.e. $q \mid 1$, impossible. So $d = p$.
3
By Fermat, $2^{q-1} \equiv 1 \pmod q$, so $d \mid (q - 1)$, i.e. $p \mid (q - 1)$, giving $q \equiv 1 \pmod p$.
4
Finally $q$ is odd (it divides the odd number $2^p - 1$), so $q \equiv 1 \pmod 2$; combined with $q \equiv 1 \pmod p$ and $\gcd(2,p)=1$, the CRT gives $q \equiv 1 \pmod{2p}$.

Answer:

Every prime factor $q$ of $2^p - 1$ satisfies $q \equiv 1 \pmod{2p}$.

Going Deeper

Generalization: the order $\operatorname{ord}_n(a)$ always divides $\varphi(n)$ (and divides the Carmichael $\lambda(n)$, the true universal exponent). An element whose order equals $\varphi(n)$ is a primitive root; primitive roots exist exactly for $n = 1, 2, 4, p^k, 2p^k$ with $p$ an odd prime. The key lemma $a^m \equiv 1 \iff \operatorname{ord}_n(a) \mid m$ is what makes 'find all exponents' problems finite.
Where it appears: the period of a repeating decimal $\tfrac1p$ equals $\operatorname{ord}_p(10)$; proving prime factors of $a^n - 1$ or Mersenne/Fermat numbers lie in fixed residue classes; pinning down the order of $2$ to bound divisors; and reducing astronomically large exponents to their residue modulo the order.
Pitfall: to reduce the exponent of $a^E \bmod n$, reduce $E$ modulo $\operatorname{ord}_n(a)$ — NOT modulo $\varphi(n)$ (which is only an upper bound) and never modulo $n$. Also, $a^m \equiv 1$ forces $\operatorname{ord}_n(a) \mid m$, but $a^m \equiv -1$ does NOT mean the order divides $m$; it means the order divides $2m$ but not $m$, so the order is even and equals $2 \cdot (\text{order of } a^? )$ — handle the $-1$ case separately.

Spot the Signal

Look for problems where the key step is using the period of powers modulo n to control cycles and exponent equations.
You can describe the hard part as using the period of powers modulo n to control cycles and exponent equations, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for orders modulo n, then rewrite the givens around it.
Name the relation that makes Orders Modulo n legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Orders Modulo n just because the surface looks familiar; verify the required condition first.
Applying Orders Modulo n because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let orders modulo n reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using the period of powers modulo n to control cycles and exponent equations.