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?
Answer
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.$
No comments:
Post a Comment