odd numbers have multiplicative inverses modulo 2^n (even numbers do not).
? for(n=1, 8, print1(2^n,":"); for(j=1, 2^(n-1), i=2*j-1; print1(" ",lift(Mod(i,2^n)^-1))); print())
for example, in 4th line below, the reciprocals of 1 3 5 7 9 11 13 15 modulo 16 are 1 11 13 7 9 3 5 15 respectively. the product of each number multiplied by its reciprocal is a number of the form 16N+1.
2: 1
4: 1 3
8: 1 3 5 7
16: 1 11 13 7 9 3 5 15
32: 1 11 13 23 25 3 5 15 17 27 29 7 9 19 21 31
64: 1 43 13 55 57 35 5 47 49 27 61 39 41 19 53 31 33 11 45 23 25 3 37 15 17 59 29 7 9 51 21 63
128: 1 43 77 55 57 35 69 111 113 27 61 39 41 19 53 95 97 11 45 23 25 3 37 79 81 123 29 7 9 115 21 63 65 107 13 119 121 99 5 47 49 91 125 103 105 83 117 31 33 75 109 87 89 67 101 15 17 59 93 71 73 51 85 127
256: 1 171 205 183 57 163 197 239 241 27 61 167 41 19 53 223 225 139 173 151 25 131 165 207 209 251 29 135 9 243 21 191 193 107 141 119 249 99 133 175 177 219 253 103 233 211 245 159 161 75 109 87 217 67 101 143 145 187 221 71 201 179 213 127 129 43 77 55 185 35 69 111 113 155 189 39 169 147 181 95 97 11 45 23 153 3 37 79 81 123 157 7 137 115 149 63 65 235 13 247 121 227 5 47 49 91 125 231 105 83 117 31 33 203 237 215 89 195 229 15 17 59 93 199 73 51 85 255
they look quite random, but there are some patterns, like some early (e.g., 11, 13, 57) and late numbers (e.g., 51, 85) persisting through several exponents.
the randomness is reminiscent of multiplicative inverse modulo a prime number. however, prime numbers and powers of 2 are about as different as numbers can be.
the reciprocal of a reciprocal is itself, so most numbers pair with another (two-cycle). however, 1, (2^(n-1) - 1), (2^(n-1) + 1), and (2^n - 1) (the last one equivalent to -1) are always their own inverses (one-cycle).
previously: it is possible to set up a Galois field of order 2^n so that all nonzero elements (not just the odd elements) have reciprocals. the reduction operation becomes more complicated than integer modulo 2^n.
No comments :
Post a Comment