3 ms·
Integer addition is associative, even for fixed-bitwidth integers (which constitute "the integers modulo 2^n" for some bitwidth n; e.g. 8-bit bytes under additi
by groovy2shoes 10y ago
Integer addition is associative, even for fixed-bitwidth integers (which constitute "the integers modulo 2^n" for some bitwidth n; e.g. 8-bit bytes under addition form the group of integers modulo 2^8 (i.e., integers modulo 256)).
Note that both the full integers as well as the integers modulo n are groups under addition. As groups are more restrictive than semigroups, all groups are also semigroups (groups are semigroups that also have an identity element and where every element is invertible).
Integer multiplication also forms a semigroup (and in fact a monoid, due to identity), but not a full group due to zero not having an inverse. So, it's usually said that "the non-zero integers" form a group.
- im4w1l 10y agoYou mean integer multiplication in Z_p?
- groovy2shoes 10y agoWell, Z_n in this case, but yes.
- JadeNB 10y ago> Integer multiplication also forms a semigroup (and in fact a monoid, due to identity), but not a full group due to zero not having an inverse. Wait, what? Very few integers have multiplicative inverses (in the integers). If you meant to speak of modular inverses, then even that is false for composite moduli like 2^n (with n > 1), which may be why im4w1 (https://news.ycombinator.com/item?id=12113934 https://news.ycombinator.com/item?id=12113934) asked if you meant to work modulo a prime.
- groovy2shoes 10y agoAh, you're right. I don't know what I was thinking. Thanks for the correction!