Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

4 Answers 4

up vote 7 down vote accepted

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$

share|improve this answer
2  
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$.

share|improve this answer
    
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.

share|improve this answer

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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.