Recognition
Use this algorithm when asked to:
- Find the order of an element.
- Count elements of order k.
- Find all elements of order k.
If
n = p * q
then
(ℤ/nℤ)* ≅ (ℤ/pℤ)* × (ℤ/qℤ)*
Always split with the Chinese Remainder Theorem (CRT).
Facts
|(ℤ/pℤ)*| = p−1, |(ℤ/nℤ)*| = (p−1)(q−1)
Each (ℤ/pℤ)* is cyclic.
ord(x) = lcm( ord(xp), ord(xq) )
A cyclic group has exactly
φ(d) elements of order d
(a) Find the Order of a
1. Factor n.
n = p * q
GAP
FactorsInt(n);
2. Compute orders modulo each prime.
Since
ap−1 ≡ 1 (mod p)
the order divides p−1.
Start with
t = p−1
Factor t.
For every prime divisor r:
while at/r ≡ 1 (mod p), t ← t / r
Idea: repeatedly shrink the exponent until it cannot be reduced.
Then
t = tp = ord(a mod p)
Repeat for q to obtain tq.
Useful GAP
FactorsInt(p-1);
PowerMod(a, e, p);
OrderMod(a, p); (verification)
3. Combine
ord(a) = lcm(tp, tq)
GAP
Lcm(tp, tq);
(b) Count Elements of Order k
1. List divisors
d1 | (p−1), d2 | (q−1)
GAP
DivisorsInt(p-1);
DivisorsInt(q-1);
2. Keep only
lcm(d1, d2) = k
3. Count
A cyclic group contributes
φ(d) elements of order d
Therefore
Σ φ(d1) · φ(d2)
lcm(d1,d2)=k
GAP
Phi(d);
(c) Find All Elements of Order k
1. Find valid sub-orders
List
d1 | (p−1), d2 | (q−1)
and keep only
lcm(d1, d2) = k
2. Find generators
Test small integers (2, 3, 5, …) until one passes:
g(p−1)/r ≢ 1 (mod p)
for every prime divisor r of p−1. Repeat for q.
GAP
GeneratorsPrimeResidues(p);
3. Build all subgroup elements
For each valid pair (d1, d2):
a = gp(p−1)/d1, b = gq(q−1)/d2
These produce one element of orders d1 and d2.
To obtain all elements:
am, 1 ≤ m < d1, gcd(m, d1) = 1
bn, 1 ≤ n < d2, gcd(n, d2) = 1
There are exactly
φ(d1), φ(d2)
such elements.
Manual shortcut:
- List 1, …, d−1.
- Cross out multiples of every prime factor of d.
- Remaining exponents are exactly the coprime ones.
4. Combine with CRT
For every pair (am, bn) solve
x ≡ am (mod p), x ≡ bn (mod q)
Each CRT solution has order k.
GAP
ChineseRem(a, p, b, q);