14 Oct
2016
14 Oct
'16
4:22 p.m.
Abelian group problems are nearly always easier when phrased additively. The map Z/nZ \to Z/nZ given by x \to ex has cyclic image <gcd(e,n)+nZ> of order n/gcd(e,n), cyclic kernel <n/gcd(e,n)+nZ> of order gcd(e,n). Thus, returning to the multiplicative world, the x \to x^e map modulo p has image of order (p-1)/gcd(e,p-1) and it is gcd(e,p-1)-to-1. Isolating out that fact about x \to ex modulo n makes various little arguments in elementary number theory inexorable rather than the least bit tricky. E.g., if g is a primitive root modulo p then the other primitive roots are exactly g^k for gcd(k,p-1)=1. Jerry Shurman