Hacker News Reader

Comment by tromp | Hacker News Reader

> what is the pattern here and what is the number-theoretic explanation for it?

We're working with numbers modulo 10, i.e. Z/10Z = {0,1,2,3,4,5,6,7,9}.

Its multiplicative subgroup consists of all the elements with a multiplicative inverse, which are {1,3,7,9}. Note that 1*1 = 1, 3*7 = 21 = 1 (mod 10), and 9*9 = 81 = 1 (mod 10). Its size is phi(10) = phi(2*5) = phi(2) * phi(5) = 1 * 4 = 4.

When computing powers, the exponent can be reduced modulo the size of the multiplicative subgroup: n^e mod m = n ^ {e mod phi(m) } mod m.

In this case of m=10, powers that are 1 or 3 mod 4 are bijections, others are not.

View on HN

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

> consider Z/3Z = {0, 1, 2}, all of whom have multiplicative inverses.

0 has no multiplicative inverse. 1 and 2 = -1 are their own inverse.

Accurate. I'm not sure why I wrote they all have inverses, or the point I was trying to make -- phi(3) = 2, so your provided equation already demonstrates that for all even e, n^e = n^0 = 1 mod m (which is obviously not a bijection for n > 2).

It may have worked better with phi(7) = 6: it's not immediately obvious that f(n) = n^3 mod 7 is not a bijection for n in Z/7Z, but easy to demonstrate nonetheless: 2^3 = 1 mod 7 = 1^3.

(That said, I think you hinted at the requirement of coprimality with phi when you pointed to "1 or 3 mod 4" instead of just saying "odd numbers" for 10.)

I think my follow-on point re: bases with non-square powers mapping multiple elements to zero is still correct and not covered by your explanation, though.

Reply on news.ycombinator.com