# modulo question

I thought you could only mod positive numbers but then I saw this

and became confused...How does this even work ? how can you have negatives?

\begin{align*} -8 &\equiv 7 \pmod{5}\\ 2 &\equiv -3 \pmod{5}\\ -3 &\equiv -8\pmod{5} \end{align*}

Actually....What I thought was that mod just means how many times a number goes into another number while leaving a remainder...

But after some reading I find that negative values can be equal to positive values as long as some value-remainder is divisible by the modulus. But it doesnt make sense to me that the remainderi n these equation is greater than the modulus AND that the remainder is positive while answer on left end is negative.

-
Does this help? -8=-2(5)+2,7=1(5)+2. Actually, all of those (-8,-3,2, and 7) leave a remainder of 2, thus are congruent mod 5. – Mike Feb 23 '12 at 8:45
In math the meaning of 'mod' differs from its meaning in programming. The programmers primarily see 'mod' as a binary remainder operator that spews out an integer as its value. For them the mathematicians 'mod' may be best interpreted as a comparison operator, i.e. one that has true/false as its value. If (a BIG if) your programming language specifies that the remainder is always non-negative, then the math notation $$a\equiv b \pmod{c}$$ means the same thing as (in my rusty C) $$(a\%c)==(b\%c).$$ Many programming specifications don't specify a positive remainder further complicating things. – Jyrki Lahtonen Feb 23 '12 at 9:06

There are two notions of "mod", but I'm afraid that your description is incorrect for both.

What you describe, "how many times a number goes into another number while leaving a remainder" is the following: If you are dividing $b$ by $a$, and you write $b = qa + r$ with $0\leq r \lt |a|$, then $r$ is called the "remainder", and $q$ is called the quotient. What you describe is $q$, the quotient.

Now, to the two notions of "modulo":

Modulo operation

This is very common in Computer Science. Here, $\bmod$ is a binary operation (like $+$, $-$, $\times$).

The precise definition varies from language to language. A common one is the following: if $a$ and $b$ are integers, and $a\neq 0$, then $b\bmod a$ (pronounced exactly like it's written) is defined to be the remainder when dividing $b$ by $a$. That is, if we write $b=qa + r$ with $0\leq r\lt|r|$, then $b\bmod a$ is defined to be $r$. Therefore, $7\bmod 3 = 1$ (because $7=2\times 3 + 1$), $43\bmod 13 = 4$ (because $42 = 3\times 13 + 4$), and $1001\bmod 13 = 0$ (because $1001 = 77\times 13 + 0$). This "mod" does indeed only give you nonnegative numbers.

There are other versions of the modulo operator; some, return the "residue class of smallest absolute value" (for example, modulo $3$ will return either $-1$, $0$, or $1$, rather than $0$, $1$, or $2$; and modulo $7$ will return $-3$, $-2$, $-1$, $0$, $1$, $2$, or $3$). Others, as robjohn mentions in comments, return a remainder of the same sign as $a$, others of the same sign as $b$.

Modulo relation

This is more common in mathematics. Given an integer $n$, we define a relation called "congruent modulo $n$" as follows: we say that two integers $a$ and $b$ are "congruent modulo $n$", written $a\equiv b \pmod{n}$, if and only if $b-a$ is a multiple of $n$. Note that $a$, $b$, and $n$ can be positive, negative, or zero.

This is what you are seeing: $-8\equiv 7\pmod{5}$ is true, because $7-(-8)=15$ is a multiple of $5$. $2\equiv -3\pmod{5}$ because $-3-2 = -5$ is a multiple of $5$. $-3\equiv -8\pmod{5}$ because $-8-(-3) = -5$ is a multiple of $5$.

Note that this is a relation: you don't get a number "out of it", like you do with the modulo operation above; this is a statement about whether two numbers are related.

Connection between the two notions

The simplest connection between the two concepts is the following:

Theorem. Let $a$ and $b$ be integers, and let $n\neq 0$ be a nonzero integer. Then $$a\equiv b\pmod{n}\textit{ if and only if } a\bmod n = b\bmod n.$$

That is: $a$ and $b$ are congruent modulo $n$ if and only if they leave the same remainder when divided by $n$.

Proof. Suppose that $a\equiv b\pmod{n}$, and write $a=qn + r$, $b=pn+s$, with $0\leq r\lt |n|$, $0\leq s\lt |n|$. Then $a\equiv b\pmod{n}$ if and only if $(qn+r)-(pn+s) = (q-p)n + (r-s)$ is a multiple of $n$; this occurs if and only if $r-s$ is a multiple of $n$, which occurs if and only if $|r-s|$ is a multiple of $n$.

But $0\leq |r-s|\lt|n|$; the only multiple of $n$ that has absolute value smaller than $|n|$ is $0$. So $r-s$ is a multiple of $n$ if and only if $|r-s|=0$, if and only if $r=s$. Since $r=a\bmod n$ and $s=b\bmod n$, we conclude that $a\equiv b\pmod{n}$ if and only if $a\bmod n = b\bmod n$. $\Box$

-
Beware that different programming languages use different conventions about the sign of the modulo operator. In only a few (the most notable being Pascal and ALGOL) is the result always positive. Most commonly it has the same sign as the dividend, but in a good number, it has the same sign as the divisor. Some languages have two functions; one of which has the sign of the dividend and the other has the sign of the divisor. Scheme is strange in that $\rm{mod}$ is $\ge0$ and $\rm{mod}_0$ is closest to $0$ (what is $3\;\rm{mod}_0\;6$?). – robjohn Feb 23 '12 at 17:11
@robjohn: Good point. Thanks. – Arturo Magidin Feb 23 '12 at 17:18

$a\equiv b\pmod c$ just means $b-a$ is divisible by $c$. There is no restriction to positive $a$ and/or $b$. Even $c$ could be negative, although there is little use for that, since $a\equiv b\pmod{-c}$ if and only if $a\equiv b\pmod c$.

-
so i guess i really shouldnt think of this as an equation b=q*b+remainder instead i should just take this as c/a-b. In the latter case it all makes sense but i dont see how this works for an equation.. – Raynos Feb 23 '12 at 6:44
It is true that if $a=cq+b$ then $a\equiv b\pmod c$, and it is true that if $a\equiv b\pmod c$ then there is an integer $q$ such that $a=cq+b$. But congruence is more general than remainder in that the remainder is (usually) taken to be non-negative and less than the (absolute value of the) divisor, while there is no such restriction in the congruence. – Gerry Myerson Feb 23 '12 at 11:04

In simple terms mod gives you remainder. Also if $a\equiv b\pmod{n}$, then $b\equiv a\pmod{n}$, because $n$ divides $(a-b)$, then $n$ also divides $(b-a)$. With the examples you had, for instance \begin{align*} -8 &\equiv 7 \pmod{5}\\ 2 &\equiv -3 \pmod{5}\\ -3 &\equiv -8\pmod{5} \end{align*}

$-8 \equiv 7 \pmod{5} \hspace{5pt} \Rightarrow \hspace{5pt} 7 \equiv -8 \pmod{5}$ or in other words $5$ divides $7-(-8) = 15$, i.e. $5 | 15$.

Just like with positive values you could add $5$, on the negative side you could also subtract $5$. For instance if $x \equiv 1 \pmod{5}$, then $x \equiv -4 \pmod{5}$ and also $x \equiv 6 \pmod{5}$.

In simple words that is all about mod. But if you study Number Theory, there are lot of interesting things you would learn.

-

Modulo for negative numbers may be defined differently for example x86 processors (standard PC and newer Macintoshes) defines it like that $$-a \mod n = -(a\mod n)$$ but mathematicians most often define it by using division algorithm: $$r = a \mod b$$ where $$a = bq + r\\ 0 \le r \lt b \\ q \in \mathbb Z$$

-