Multiplicative order tells us how long repeated multiplication takes to return to one. Primitive roots ask whether one element can generate an entire multiplicative group. Carmichael’s λ function records the universal exponent of the unit group. Cyclotomic polynomials package primitive roots of unity into exact algebraic objects.
These ideas appear separately in elementary number theory, but computationally they belong to one control layer. Order determines subgroup size. Subgroup size determines discrete-logarithm difficulty. λ(n) gives exponent bounds for modular arithmetic. Cyclotomic factorisations expose roots of unity, finite-field structure and polynomial components used throughout algebraic and computational number theory.
This is Guide 29 in the Bukit Timah Tutor Computational Number Theory series. It builds on Guide 2: Fast Modular Exponentiation and CRT, Guide 6: Discrete Logarithms and Guide 12: Arithmetic Functions and Möbius Inversion.
1. Multiplicative order
Let a be coprime to n. The multiplicative order of a modulo n, written ord_n(a), is the least positive integer r such that
a^r ≡ 1 (mod n).
The order exists because a lies in the finite group (Z/nZ)^×.
Lagrange’s theorem gives
ord_n(a) | φ(n),
but φ(n) is only an upper bound. The actual order may be much smaller.
2. A first exact example modulo 17
Consider a=4 modulo17.
4² =16 ≡−1 (mod17) 4⁴ ≡1 (mod17).
Neither 4 nor 4² equals one modulo17, so
ord_17(4)=4.
The element lives in a subgroup of size four inside the full multiplicative group of size16.
This matters immediately for discrete logarithms: an equation 4^x=h can only reach four residues and x is naturally defined modulo4.
3. Order testing when the group order is factored
Suppose the order N of the ambient cyclic group is known and factored:
N = q1^e1 ... qr^er.
Start with candidate order r=N. For each prime q dividing r, test whether
a^(r/q)=1.
If so, divide r by q and repeat while possible.
The result is the exact order of a. This algorithm is efficient when the factorisation of N is available.
4. Primitive roots
An element g is a primitive root modulo n when
ord_n(g)=φ(n).
Equivalently, g generates the entire unit group.
Not every modulus has primitive roots. The complete classification is:
n = 1, 2, 4, p^k, or 2p^k
where p is an odd prime.
For all other n, (Z/nZ)^× is not cyclic.
5. Verify that 3 is a primitive root modulo 17
The group F17* has order16=2⁴. To prove 3 has order16, it is enough to show
3^(16/2)=3^8 ≠1 (mod17).
Indeed
3^8 ≡16 ≡−1 (mod17), 3^16 ≡1 (mod17).
Therefore ord_17(3)=16.
The powers of 3 run through all nonzero residues before returning to one.
6. All primitive roots from one primitive root
If g generates a cyclic group of order N, then g^k is also a generator exactly when
gcd(k,N)=1.
Therefore a cyclic group of order N has exactly φ(N) generators.
For F17*, N=16, so there are
φ(16)=8
primitive roots. Starting from g=3, the exponents coprime to16 are
1,3,5,7,9,11,13,15.
Thus the eight primitive roots are the corresponding powers of3 modulo17.
7. Primitive roots and discrete logarithms
Once a primitive root g is chosen in F_p*, every nonzero element has a unique representation
g^x, x mod p−1.
This converts multiplicative questions into additive exponent questions.
For example, multiplication becomes addition of logs:
log_g(ab) ≡ log_g(a)+log_g(b) (mod p−1).
That identity powers index calculus and factor-base methods.
8. Euler’s theorem is not the sharpest universal exponent
Euler’s theorem says that for gcd(a,n)=1,
a^φ(n) ≡1 (mod n).
But φ(n) is often larger than necessary.
Carmichael’s function λ(n) is the smallest positive integer L such that
a^L ≡1 (mod n)
for every unit a modulo n.
In group language, λ(n) is the exponent of (Z/nZ)^×: the least common multiple of all element orders.
9. Carmichael λ on prime powers
For an odd prime p,
λ(p^k)=φ(p^k)=p^(k−1)(p−1).
For powers of two:
λ(2)=1, λ(4)=2, λ(2^k)=2^(k−2) for k≥3.
The last formula reflects the fact that the unit group modulo 2^k is not cyclic once k≥3.
10. Carmichael λ across coprime factors
If gcd(m,n)=1, CRT decomposes the unit group, giving
λ(mn)=lcm(λ(m),λ(n)).
More generally, factor n into prime powers and take the least common multiple of their λ values.
11. Worked example: λ(45)
Factor
45=9·5.
Then
λ(9)=φ(9)=6, λ(5)=4.
Therefore
λ(45)=lcm(6,4)=12.
Every integer coprime to45 satisfies
a^12≡1 (mod45).
Euler’s theorem would have used φ(45)=24. λ gives the sharp universal exponent.
12. Order always divides λ(n)
For every unit a modulo n,
ord_n(a) | λ(n) | φ(n)
whenever the divisibility λ(n)|φ(n) is interpreted through the standard finite-group setting.
Computationally, λ can therefore replace φ as a smaller initial candidate when searching for exact orders.
13. Carmichael numbers
A composite integer n is a Carmichael number when
a^(n−1) ≡1 (mod n)
for every a coprime to n.
Equivalently,
λ(n) | n−1.
The smallest example is561=3·11·17.
This explains why a single Fermat test can be fooled systematically by some composites. Stronger probable-prime tests use more group structure.
14. Roots of unity in a cyclic group
In a cyclic group of order N, the equation
x^m=1
has exactly
gcd(m,N)
solutions.
If g generates the group, those roots are powers of
g^(N/gcd(m,N)).
Primitive m-th roots are elements of exact order m, and exist exactly when m divides N.
15. From roots of unity to cyclotomic polynomials
The n-th cyclotomic polynomial Φ_n(X) is the monic polynomial whose complex roots are the primitive n-th roots of unity.
Its degree is
deg Φ_n = φ(n).
The fundamental factorisation is
X^n−1 = product over d|n of Φ_d(X).
This separates all roots of unity by exact order.
16. Möbius inversion formula for Φ_n
Applying multiplicative Möbius inversion to the divisor factorisation gives
Φ_n(X)=∏_(d|n) (X^d−1)^(μ(n/d)).
The negative exponents cancel in the complete product, leaving an integer polynomial.
This connects cyclotomic polynomials directly to the Möbius function from Guide12.
17. Worked cyclotomic example: Φ12
The primitive 12th roots are the roots of X^12−1 that have exact order12.
The cyclotomic polynomial is
Φ12(X)=X⁴−X²+1.
Its degree is4, matching
φ(12)=4.
The divisor factorisation is
X^12−1 = Φ1 Φ2 Φ3 Φ4 Φ6 Φ12.
18. Cyclotomic polynomials over finite fields
Over F_q, Φ_n may factor into several irreducible polynomials.
When gcd(q,n)=1, the degree of each irreducible factor of Φ_n over F_q equals the multiplicative order of q modulo n. The number of factors is therefore
φ(n)/ord_n(q).
This is a powerful bridge: an integer multiplicative-order computation predicts polynomial factorisation degrees over finite fields.
19. Example: Φ7 over F2
Since
ord_7(2)=3
because 2³=8≡1 mod7 while lower powers are not one, every irreducible factor of Φ7 over F2 has degree3.
Because φ(7)=6, Φ7 splits into exactly two irreducible cubic factors over F2.
This is the same order structure that governs extension degrees for roots of unity in finite fields.
20. Constructing finite fields with roots of unity
An n-th primitive root of unity exists in F_(q^k) exactly when
n | q^k−1
for gcd(n,q)=1.
The smallest such k is ord_n(q).
This tells an algorithm how large an extension field must be before a required transform root, cyclotomic element or multiplicative subgroup becomes available.
21. NTT design revisited
Guide14 used primitive N-th roots modulo a prime p for number-theoretic transforms.
The requirement
N | p−1
is simply the statement that F_p* contains an element of order N.
A candidate ω should be checked for exact order:
ω^N=1 and ω^(N/q) !=1 for every prime q|N.
Testing only ω^N=1 can accidentally select a smaller root and destroy transform invertibility.
22. Primitive-root search modulo a prime
To find a primitive root modulo prime p:
factor p−1
for g=2,3,4,...:
if g^((p−1)/q) !=1 mod p for every prime q|(p−1):
return g
The test works because every proper divisor of p−1 omits at least one prime factor from the full order.
For p=17, testing g=3 succeeds.
23. Order certificates
A claim that ord_n(a)=r can be certified by two kinds of checks:
a^r ≡1 (mod n) and a^(r/q) !=1 (mod n) for every prime q|r.
These checks prove no proper divisor of r can be the order.
The certificate is compact when r is factored.
24. Common mistakes
1. Assuming every modulus has a primitive root. 2. Confusing group size φ(n) with universal exponent λ(n). 3. Declaring an element primitive because g^φ(n)=1. Euler’s theorem makes that true for every unit.
4. Forgetting to test all prime divisors of the candidate order. 5. Assuming Φ_n is irreducible over every finite field. 6. Confusing an n-th root of unity with a primitive n-th root. 7. Using φ(n) when a smaller λ(n) bound is available. 8. Ignoring the condition gcd(q,n)=1 in finite-field cyclotomic order statements.
25. Practice set
1. Define ord_n(a). 2. Find ord_17(4). 3. Prove 3 is primitive modulo17. 4. How many primitive roots modulo17 exist?
5. State the classification of moduli with primitive roots. 6. Define λ(n). 7. Compute λ(16). 8. Compute λ(45).
9. How does λ compare with element orders? 10. Define a Carmichael number using λ. 11. How many solutions does x^m=1 have in a cyclic group of order N? 12. What is deg Φ_n?
13. State X^n−1 as a product of cyclotomic polynomials. 14. Compute Φ12. 15. Find ord_7(2). 16. Predict the irreducible factor degrees of Φ7 over F2.
26. Answers
1. The least positive r with a^r=1 modulo n. 2. Four. 3. 3^8=−1 and 3^16=1, so the order is16. 4. φ(16)=8.
5. 1,2,4,p^k and2p^k for odd prime p. 6. The exponent of the unit group modulo n. 7. λ(16)=4. 8. 12.
9. Every unit order divides λ(n). 10. Composite n with λ(n)|(n−1). 11. gcd(m,N). 12. φ(n).
13. X^n−1=∏_(d|n)Φ_d(X). 14. X⁴−X²+1. 15. Three. 16. Two irreducible cubic factors.
Sources and further study
Victor Shoup, A Computational Introduction to Number Theory and Algebra, gives a rigorous computational treatment of finite cyclic groups, orders and finite fields. NIST DLMF Chapter 27: Functions of Number Theory provides reference material on arithmetic functions, including Euler’s totient and related structures. Standard algebraic-number-theory texts develop cyclotomic polynomials and cyclotomic fields in greater depth.
Continue through Batch 08
Continue to Guide 30: Gaussian Integers, Euclidean GCD and Sums of Two Squares, Guide 31: Cornacchia’s Algorithm and Norm Equations, and Guide 32: Higher Power Residues, Character Sums and Cyclotomic Arithmetic.