# Negative modulus

In the programming world, modulo operations involving negative numbers give different results in different programming languages and this seems to be the only thing that Wikipedia mentions in any of its articles relating to negative numbers and modular arithmetic. It is fairly clear that from a number theory perspective $-13 \equiv 2 \mod 5$. This is because a modulus of $5$ is defined as the set $\{0,1,2,3,4\}$ and having $-13 \equiv -3 \mod 5$ would contradict that because $-3 \not\in \{0,1,2,3,4\}$. My question is then regarding a negative modulus. What definition of a modulus of $-5$ would make the most sense in number theory? One in which $13 \equiv -2 \mod -5$, one in which $13 \equiv 3 \mod -5$, or something else entirely?

• In number theory, "mod" is not used as an operator, it is a relation. So $13\equiv -2\pmod{-5}$ and $13\equiv 3\pmod{-5}$ are equally valid, as is $13\equiv 78\pmod{-5}$. As for $5$, same thing, $13\equiv 103\pmod{5}$ is just fine. Mar 11, 2015 at 21:27
• @AndréNicolas: That's a good point. However, what would make the most sense to use as the "reduced" form? For example, we don't go around saying that $\sqrt{9} = -3$.
– Matt
Mar 11, 2015 at 21:31
• There is in any case no need to use negative integers as moduli, since $a\equiv b\pmod{m}$ if and only if $a\equiv b\pmod{-m}$. As to what representatives to use as the "canonical" ones, for most purposes I would use $\{0,1,2,3,4\}$, although $-1$ is an often useful substitute for $4$, and more generally if $m=2k+1\gt 0$ then the using the numbers from $-k$ to $k$ can help speed up a computation. Mar 11, 2015 at 21:40
• @AndréNicolas: You should write that as an answer.
– Matt
Mar 11, 2015 at 21:46
• As long as the usual conventions are clear to you, task accomplished. Some people in Computer Science like to use mod as an operator, although I think for this purpose $\%$ is more common. I find the situation unfortunate, since people in Number Theory (who got there first) use mod in a different but related way. This can be a cause of unnecessary confusion, which is entirely avoided by the $\%$ notation. Mar 11, 2015 at 21:56

Negating the modulus preserves the congruence relation, by $\ m\mid x\color{#c00}\iff -m\mid x,\,$ so

$\quad a\equiv b\pmod m\iff m\mid a\!-\!b \color{#c00}{\iff} -m\mid a\!-\!b\iff a\equiv b\pmod {\!{-}m}$

Structurally, a congruence is uniquely determined by its kernel, i.e. the set of integers $\equiv 0.\,$ But this is a set of the form $\,m\Bbb Z,\,$ which is invariant under negation $\,-m\Bbb Z\, =\, m\Bbb Z$

When you study rings you can view this as a a special case of the fact that ideals are preserved under unimodular basis transformations, e.g. $\,aR + bR\, =\, cR + dR \$ if $\, (a,b)M = (c,d)\,$ for some matrix $\,M\,$ having $\ \det M = \pm1,\,$ e.g. $\ a\Bbb Z + b \Bbb Z\, =\, a\Bbb Z + (b\!-\!a)\,\Bbb Z,\,$ which is the inductive step in the Euclidean algorithm for the gcd (it computes the modulus $\,m=\gcd(a,b)\,$ corresponding to the congruence generated by $\,a\equiv 0\equiv b,\,$ i.e. $\,a\Bbb Z + b\Bbb Z = m\Bbb Z).\,$ When the ideal $= a\Bbb Z$ then this amounts to multiplying $\,(a)\,$ by a $\,1\times 1\,$ matrix $\,[u]\,$ with $\det = \pm1,\,$ i.e. $\, u = \pm1,\,$ yielding $\,a\Bbb Z = -a\Bbb Z,\,$ precisely the original equality

As for the choice of canonical reps for the congruence classes, it is your freedom to choose which system you find most convenient. For example, in manual computations it often proves most convenient to choose reps of least magnitude, e.g. $\, 0,\pm1,\pm2\,$ mod $\,5,\,$ e.g. the capability to to use $\,-1$ simplifies many things, e.g. compare $(-1)^n$ vs. $\,4^n.$

According to definition, $a\equiv b\ (\mod c)$ iff there exists $n\in \mathbb Z$ so that $a = b + nc$. In particular, all of the following statements are true:

• $-13\equiv 2\ (\mod 5)$
• $-13\equiv -3\ (\mod 5)$
• $-13\equiv -13\ (\mod 5)$
• $-13 \equiv 222\ (\mod 5)$
• $13 \equiv -2\ (\mod -5)$
• $13 \equiv 3\ (\mod -5)$
• $13 \equiv 13\ (\mod -5)$
• As I mentioned in a comment above, that is a good point and I had forgotten about it when writing this question, however what would make the most sense to use as the "reduced" form?
– Matt
Mar 11, 2015 at 21:32
• @Matt: Whatever is most useful in your context. Mar 11, 2015 at 21:37

The multiples of 5 are the exact same as the multiples of $-5$, it's just they're indexed differently. So $13 \equiv -2 \bmod -5$ is just as valid as $13 \equiv 3 \bmod -5$, since $13 = -3 \times -5 - 2 = -2 \times -5 + 3$.

It is true that $-3 \not\in \{0, 1, 2, 3, 4\}$. But $-3$ is in $\{0, -4, -3, -2, -1\}$. We could say that 2 and $-3$ are "representatives" of the same "coset" (I hope this doesn't sound like I'm inventing the terminology off the cuff). This coset consists of all numbers that are 2 more than a multiple of 5 or 3 less than a multiple of 5: $5n + 2$ or $5n - 3$, where $n$ is any integer.

Obviously there are infinitely many other numbers to represent a particular coset. But something like $13 \equiv 13 \bmod -5$ looks like an obfuscation. In general, for $a \equiv b \bmod c$, you want $|b| < |c|$. But the preference is usually for $b$ positive, unless $b = c - 1$, in which case mathematicians much prefer to write $a \equiv -1 \bmod c$. Look up Fermat's little theorem or Wilson's theorem for examples of this.