That's a solid explanation, but it's not quite complete -- consider Z/3Z = {0, 1, 2}, all of whom have multiplicative inverses. An easy way to look at this is

That's a solid explanation, but it's not quite complete -- consider Z/3Z = {0, 1, 2}, all of whom have multiplicative inverses. An easy way to look at this is that the numbers are equivalent to {0, 1, -1} mod 3, and so the powers are {0^n, 1^n, and (-1)^n}, which is only a bijection for odd n (otherwise, 1^n = (-1)^n). Indeed, you can generalize this to the statement that even powers cannot be bijections for any base N > 2, as 1 != -1 mod N. I believe you'll find that the powers that are bijections are those relatively prime with phi(N) (as a consequence of the Chinese remainder theorem [0]), outside of the special case GP asked about: With (nontrivial) perfect square factors, there are nontrivial roots for n^2 = 0 mod N (namely: solutions other than 0 mod N). For instance, in octal, consider 4 * 4 = 16 (0o20 which ends in zero). Any greater powers of 4 in octal will also end in zero. [0] This is in fact critical to the decryptability of RSA, which requires that m^(e*d) = m mod N, or equivalently that for a given e, m^e is invertible for all choices of m, i.e. f(m) = m^e mod N is a bijection: https://crypto.stackexchange.com/questions/12255 https://crypto.stackexchange.com/questions/12255