Two's complement signed integers modulo $n$ lacks inverse for $-32768$: does addition still work?

Question

I have a computer program that needs to do addition using the int16_t type, i.e., signed 16-bit integers. Since this is a signed binary number, the largest positive value is $2^{15} - 1 = 32767$, expressed in binary as $0111111111111111_2$. When we add 1 to this, we get $1000000000000000_2$, or $-32768$ decimal. Further addition gives $1000000000000001_2 = -32767_{10}$, and so on. This means that $-32768$ does not have an additive inverse.

My question is: should I expect to be able to add and subtract numbers using signed integers modulo $2^{15}$, given that there is one element without an inverse and hence the set is not a group under addition? I wrote a test program, and addition seems to work as expected, but I may be missing a case.

Answer 1

You actually have two values for each residue class $\bmod 32768$ in the $16$ bit signed integers. In all cases they differ by $32768$. In the case of $-32768$ the other member of the class is $0$. Normally one would express the numbers $\bmod 32768$ using the range $0-32767$, which is exactly the set of nonnegative integers you have. Each has an additive inverse with $0$ and $16384$ their own inverses.

Answer 2

There is no use expecting what computers do which is called 'addition' to exactly mimic algebraic addition, because computers can only (natively, i.e without special programming) represent finitely-many algebraic values, hence only finitely-many algebraic sums. For some pairs their computer 'sum' matches their algebraic sum exactly; for other pairs, it only matches their algebraic sum if one explicily discards the carry-out (the 17th bit in your case); for still other pairs, the algebraic sum is too large to be represented, hence the 'sum' generated by the computer will be different from the algebraic sum. Part of programming is knowing how to either work within the limitations imposed by the finiteness of the machine's native 'numbers' or program to extend beyond those limits (i.e 'multi-precision arithmetic').

Answer 3

Of course −32768 has an inverse mod $2^{16}$! It's −32768! It's like 0 in that it's its own negative. It's actually more clear with unsigned representation where it's 32768. $32768 + 32768 = 65536$, but $65536 \equiv 0 \mod 2^{16}$, so as far as 16 bit integers are concerned, they're the same number.

The only reason it doesn't look like there's a negative is because we arbitrarily call any number with a leading 1 "negative" even when no such concept actually exists for modular integers. This runs into trouble specifically for 32768, since it's impossible to distinguish from its negative. Actually calling 0x8000 "negative" is like calling 0 "positive," when really neither are either.