5 ms·

I was surprised by the chart showing that there is a bijection between last digit of a number and last digit of the number's cube. In base 10, this works for e

by schoen 4y ago

I was surprised by the chart showing that there is a bijection between last digit of a number and last digit of the number's cube. In base 10, this works for every odd power but for no even power. (if you're given that a square ends in anything but 0 or 5, there are always two different possibilities for the last digit of the square root) Here are the powers (less than 100) for which this works in different bases (up to 25). Now I'm quite confused: what is the pattern here and what is the number-theoretic explanation for it? (Edit: It looks like the bases for which no power, except the trivial case of 1, has this property are exactly those bases that are divisible by a perfect square -- but I wouldn't have expected that and still don't know how to account for it.) 2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] 3 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 4 [1] 5 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 6 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 7 [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97] 8 [1] 9 [1] 10 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 11 [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99] 12 [1] 13 [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97] 14 [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97] 15 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 16 [1] 17 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 18 [1] 19 [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97] 20 [1] 21 [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97] 22 [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99] 23 [1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97] 24 [1] 25 [1]

tromp 4y ago
> 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.
- vitus 4y ago
  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
  - tromp 4y ago
    > 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.
    - vitus 4y ago

by schoen 4y ago

tromp 4y ago

> 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.

vitus 4y ago
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
- tromp 4y ago
  > 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.
  - vitus 4y ago