Cyclic group

A cyclic group is a group generated by one element: pick g, and every element is some power gʲ. Abstractly there is only one cyclic group of each order m, the integers mod m under addition, so every question about one reduces to arithmetic on exponents. The problems below use that in a single way. Each asks how many x satisfy a power congruence xᵏ ≡ c (mod n). Factoring candidates or testing residues one at a time would be the brute-force answer. Because the multiplicative group mod a prime is cyclic, the count is a single gcd.

The idea: one lemma

In a cyclic group of order m, the equation xᵏ = 1 has exactly gcd(k, m) solutions, and they form the unique subgroup of that order.

The proof is one line of exponent arithmetic. Write x = gʲ with 0 ≤ j < m. Then xᵏ = 1 ⇔ gʲᵏ = 1 ⇔ m | jk ⇔ m / gcd(k, m) divides j. That leaves gcd(k, m) choices of j. Three consequences carry most of the weight:

  • The power map x ↦ xᵏ is a bijection exactly when gcd(k, m) = 1. Its kernel is the solution set above. This is why RSA decryption works at all, and it is the starting point of RSA.
  • xᵏ = c has either zero solutions or exactly gcd(k, m). If there is one solution x₀, the full solution set is x₀ times the subgroup, a coset of the same size.
  • Subgroups are indexed by divisors. For every d | m there is exactly one subgroup of order d, and it is the set of dth roots of unity. If I can find one generator of it, the rest of the subgroup comes from repeated multiplication.

The lemma needs a cyclic group, so I have to know which groups qualify. For a prime p, (ℤ/pℤ)ˣ is cyclic of order p − 1; a generator is a primitive root. The same holds for (ℤ/pᵉℤ)ˣ with p odd, of order pᵉ⁻¹(p − 1). For a composite n, the Chinese remainder theorem splits (ℤ/nℤ)ˣ into a product of those prime-power groups, so solution counts multiply. That makes them a multiplicative function of n.

How each solution uses it

182 (RSA unconcealed messages). A message is unconcealed when mᵉ ≡ m (mod n). CRT splits n = pq into the two prime moduli. Mod p, either m ≡ 0, or mᵉ⁻¹ = 1 in a cyclic group of order p − 1, which by the lemma has gcd(e − 1, p − 1) solutions. So the count for each exponent is the closed form

N(e) = (1 + gcd(e − 1, p − 1)) · (1 + gcd(e − 1, q − 1))

Each candidate exponent then costs two gcds instead of n modular powers. The same lemma gives the floor of the scan: e must be odd and p − 1 is even, so each gcd is at least 2 and no exponent does better than 9. The solution still finds the minimum by scanning, and the floor serves as a check on the result.

272 (cube roots of unity mod n). Here k = 3 is fixed and n varies. Per prime power, the lemma gives gcd(3, |(ℤ/pᵉℤ)ˣ|) roots. That is 3 when p ≡ 1 (mod 3), 3 for 3ᵉ with e ≥ 2, and 1 otherwise. CRT multiplies the factors, so the count is 3ᵏ, where k counts those "good" factors. The problem stops being about congruences: it becomes a sum over integers with exactly five good factors. That is a depth-first search over prime powers combined with quotient blocking for the last prime. The group theory is used once, at the start. The rest of the work is enumeration.

421 (prime factors of n¹⁵ + 1). Swapping the order of summation turns the question into "for each prime p, how many n have n¹⁵ ≡ −1 (mod p)?" Since (−1)¹⁵ = −1, the solutions are −u for the 15th roots of unity u. By the lemma there are gcd(15, p − 1) ∈ {1, 3, 5, 15} of them, never zero (which is the statement's "always composite"). The second structural fact does the remaining work. A cyclic group of order 15 is the direct product of its subgroups of orders 3 and 5. So the solution builds the cube roots and the fifth roots separately, each from one modular exponentiation a^((p−1)/r), and multiplies the two lists together. The roots of unity page walks through that generator construction. This page only adds why it is enough: in a cyclic group, one generator of the subgroup gives you all of it.

C and Python

The group theory is the same in both languages. Where they differ is in carrying out the arithmetic that follows from it:

problem Python C
182 math.gcd, unbounded int four-line iterative gcd, long long
272 primesieve bindings, unbounded totals primesieve C library, __int128 accumulators (the larger test case exceeds 64 bits)
421 primes split into the four gcd classes up front, then vectorised powmod over numpy uint64 arrays; sums split into high/low 32-bit halves so the array sum can't wrap one scalar loop with a branch per prime, unsigned __int128 total and a hand-written formatter

421 is the case to study for integer width. Python's own integers are safe, but the numpy reduction underneath them wraps at 2⁶⁴ without any warning. The partition by gcd class matters for a different reason. Every prime in a class needs the same number of roots, and that uniformity is what lets the Python side treat the class as one array.

How to reason about it

  • The signal is an equation xᵏ ≡ c (mod p), or a count of fixed points of a power map. In either case, look at gcd(k, p − 1) before writing a loop. Usually that is the whole count, and the program only has to sum it over the right index set. This is reduce before coding in its purest form.
  • Factor the modulus first. The lemma applies per prime power, and CRT multiplies the results. Doing the work mod n directly hides the structure.
  • Mind the prime 2. (ℤ/2ᵉℤ)ˣ is not cyclic for e ≥ 3: it is C₂ × C_(2^(e−2)), a product of two cyclic groups rather than one. So x² ≡ 1 (mod 8) has four solutions, not gcd(2, 4) = 2. 272 gets away with it only because 3 is odd and the group's order is a power of two. For an even k, handle 2 by hand.
  • The same structure, combinatorially. "Cyclic" also describes rotations. A permutation's power σᵏ acts on each cycle of length ℓ as a rotation by k in C_ℓ, so it splits that cycle into gcd(k, ℓ) cycles. Counting necklaces up to rotation is Burnside's lemma over C_n, where rotation by j fixes c^gcd(j, n) colourings. The unsolved problems in the list (permutation powers, riffle shuffles, patterned cylinders, pizza toppings) use this side of the group.

Problems6 / 12

  • ● 0182 — RSA Encryption
  • ● 0272 — Modular Cubes, Part 2
  • ○ 0281 — Pizza Toppings
  • ● 0421 — Prime Factors of $n^{15}+1$
  • ○ 0483 — Repeated Permutation
  • ○ 0622 — Riffle Shuffles
  • ○ 0651 — Patterned Cylinders
  • ○ 0902 — Permutation Powers
  • ○ 0903 — Total Permutation Powers
  • ● 0930 — The Gathering
  • ● 0971 — Modular Polynomial Composition
  • ● 0995 — A Particular Pair of Polynomials