Do integers modulo $n$ minus $\frac n 2$ (i.e. signed integers) still form a commutative ring?

Question

This is related to this (closed) question on programmers.sx.

I'm looking into the properties of (64bit signed) computer integers. My question is whether they do form a commutative ring as $\mathbb{Z}/n\mathbb{Z}$ does?

In my opinion those numbers ($\{-2^{63},\cdots,0,\cdots,2^{63}-1\}$) are kind of like $\mathbb{Z}/2^{64}\mathbb{Z}$ only with subtracting $2^{63}$ from every one of them, and this should change neither associativity nor distributivity.

Answer 1

From what you said, I'll assume that you're working in 64-bit 2s complement arithmetic. Your observation that this arithmetic is essentially the same as arithmetic in the ring $\mathbb{Z}/2^{64}\mathbb{Z}$ is correct, subject to some caveats. What I'm about to say holds for any $n\ge 1$ so to save typing, I'll restrict this example to $n=3$. In this arithmetic, the integers $\{-2^{n-1},\dotsc,2^{n-1}-1\}$ are represented using $n$ bits, and in the case $n=3$ we have $$\begin{array}{rccccccc} \mathbf{n}: & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3\\ \mathbf{(n)}: & 100 & 101 & 110 & 111 & 000 & 001 & 010 & 011 \end{array}$$ Here, $(k)$ denotes the 2s complement representation of the number $k$. I'll also use $\oplus, \otimes$, respectively, to indicate addition and multiplication in the 2s complement realm.

Here are the caveats I mentioned. Consider the sum $(-3)\oplus(-2)$. Addition in 2s complement is just binary addition of the representatives, so we have $101+110=1011$. This sum has two problems: first, the result is too large to fit in 3 bits (a carry), and, second, the result, $011$ is positive $(3)$ and the result of adding two negative numbers $(-3)$ and $(-2)$ shouldn't be positive (we have an overflow).

In many situations, if an operation causes a carry or an overflow, the operation is flagged and the result is considered to be an error. In that interpretation, the 2s complement numbers are not closed under addition or multiplication, so they can't possibly be "the same" ring as $\mathbb{Z}/2^n\mathbb{Z}$, which is closed under both operations.

However if you ignore the carry and overflow flags then you do have a faithful correspondence between $n2C$, the $n$-bit 2s complement numbers, and $\mathbb{Z}/2^n\mathbb{Z}$. The mapping, $f: n2C\rightarrow \mathbb{Z}/2^n\mathbb{Z}$ between these two sets is just about as simple as it could be: $f(k) = [k]$, where $[k]$ represents the residue class modulo $2^n$ where $k$ belongs.

Example: We saw above that $(-3)\oplus(-2)= (3)$. Then $(3)\mapsto [3]$. We also have $(-3)\mapsto [-3]$ and $(-2)\mapsto [-2]$ and (remembering we're working mod 8) $$ f((-3)\oplus(-2)) = f((3)) = [3] = [-5] = [-3]+[-2] = f((-3))+f((-2)) $$

The rest is just details. In technical terms, $f$ is an isomorphism between $n2C$ and $\mathbb{Z}/2^n\mathbb{Z}$. To establish this, we need to show

• $f$ is bijection, namely that if $a \ne b$ then $f(a)\ne f(b)$ and that every element in $\mathbb{Z}/2^n\mathbb{Z}$ is the image of some element in $n2C$. In other words, the two sets have the same elements, just renamed.
• $f$ preserves addition, namely $f((a)\oplus (b)) = f((a))+f((b))$
• $f$ preserves multiplication, namely $f((a)\otimes (b)) = f((a))\cdot f((b))$

In this situation, these three properties are easy to show, thus proving that $n2C$ and $\mathbb{Z}/2^n\mathbb{Z}$ are effectively the same objects.

Answer 2

The answer to your question depends on how you define the operations.

For instance what should $2^{63}-2$ plus $7$ be?

If you are willing to say that it is $-2^{63}+5$ then you are effectively caculating modulo $2^{64}$ so in $\mathbb{Z}/2^{64}\mathbb{Z}$.

One would say you chose $\{-2^{63},\cdots,0,\cdots,2^{63}-1\}$ as a set of representatives for the classes modulo $2^{64}$. Whether you choose this set of representative or $\{0,\cdots,2^{64}-1\}$ or $\{17,\cdots,2^{64}+16\}$ or still something is often irrelevant in a math context.

But if you do this the sign stops making sense.

If you do not use that definition for $2^{63}-2$ plus $7$ the question would be what else you use. You might say it is not defined, but then this is not a commutative ring anymore since in it addition is defined for any two elements.

However, it would still stay true that when you have an expressions where all the operations are defined, then they are distributive, associative, commutative. To see this note that you are really only working with usual integers and just disallow some that are too large.