# simple 'why' question about modular arithmetic 13 mod 5

they say that 13/5 = 2 remainder 3, and therefore 13 mod 5 = 3 but 13/5 = 2.6 I do not know where they get the remainder 3 from

• Google "division theorem" for information that will help you. – GFauxPas Nov 10 '14 at 4:26
• . . . um, when you divide something, what does "remainder" mean? – imallett Nov 10 '14 at 6:42

Since $13 = 2 \cdot 5 + 3$, the remainder when $13$ is divided by $5$ is $3$.

It's not really correct to think of $\!\!\mod n$ as an operation returning integers $\{0, \dots, n - 1\}$ (as in, for example, the C operator $a\;\%\;b$); rather, $a = b\pmod{n}$ simply means that $n|(b - a)$. Here, $13=3\pmod{5}$ because $13 - 3 = 10$ is divisible by $5$.

(So, what's the problem just writing $13\pmod{5}= 3$? In general, we want to talk about relations like $a = b\pmod{X}$ for various "things" X (groups, ideals, vector spaces, etc.). For integers, we have a convenient choice of representative of the corresponding classes: Every integer $a$ satisfies $a = b\pmod{n}$ for exactly one choice of $b = 0, \dots, n - 1$. Such canonical representatives don't exist in general. More damningly, thinking about $a\to a\pmod{n}$ as a function or operation $\mathbb{Z} \to \mathbb{Z}$ rather than a relation means that expected, desirable properties fail to hold. For example, $5\pmod{3} = 2$ and $4\pmod{3} = 1$, but $(5\mod{3}) + (4\mod{3})$ would equal $3$, whereas $(5 + 4)\pmod{3} = 0$.) The same applies to multiplication, etc.

• As an aside, the C operator does not really behave like the modulo operator, it is the "remainder operator", which differs for negative values. For instance, (-3) % 2 = -1, because the solution to 2q + r = -3 where q = (-3) / 2 = -1 with / being integer division (round towards zero) is r = -1. But you would probably expect -3 mod 2 to be 1. Like I mentioned elsewhere, this is a trap many people fall into, as they mistakenly think a % b will always return values in [0, b), which is terribly wrong (and dangerous) for signed types. – Thomas Nov 10 '14 at 6:49
• @Thomas +1, There are at least 3 useful ways to define the modulo operator in programming - the modulus can get the sign of dividend, divisor or just be always positive. Which you're interested in depends on the problem. Programming languages don't have a concensus. – Kos Nov 10 '14 at 8:44
• @Thomas Actually the behavior of the C operator % is (potentially) even worse than you describe: the C99 standard says "If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined". I wouldn't trust an actual implementation farther than that. – David K Jan 2 '15 at 16:37

Do you know how to convert improper fractions into mixed fractions? That's basically what we're doing here: \begin{align*} \frac{13}{5} = \frac{2(5) + 3}{5} = 2 + \frac{3}{5} = 2\frac{3}{5} \end{align*} The leftover part that remains after taking out as many $5$'s as we could from $13$ is $3$, so that's our remainder.

13/5 = 2.6 means that 5 'fits' into 13 2 times and a an additional "0.6" time (that's the rest of the division)

So 13=5+5+0.6*5, 13=5+5+3.

What $13$ mod $5 = 3$ means is that you take $13$ and subtract $5$ repeatedly until you get a number less than $5$. $13-5=8$ and $8-5=3$. $3$ is less than $5$. Therefore, $13$ mod $5 = 3$.

Integer arithmetic--where the numbers that go into the operations and the results that come out are all integers--is important in mathematics and in practical applications of mathematics. In integer arithmetic, the result of $13 \div 5$ cannot be $2.6,$ because $2.6$ is not an integer: instead, $2.6$ is a rational number, which also has many important uses in mathematics and in practical applications but is not useful in this particular case.

I was taught integer division in school long before rational division. Possibly not all school curricula do it this way, but "$13$ divided by $5$ is $2$ with a remainder of $3$" is an old concept.