1
$\begingroup$

After checking out khan academy "what is modular arithmetic" https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

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

can someone please explain?

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

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Nov 10 '14 at 6:49
  • $\begingroup$ @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. $\endgroup$ – Kos Nov 10 '14 at 8:44
  • $\begingroup$ @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. $\endgroup$ – David K Jan 2 '15 at 16:37
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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