modulo question

Solution 1:

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

Solution 2:

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

Solution 3:

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.

Solution 4:

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