# Modulo and euclidean division - Is Wikipedia correct or not?

In the Wikipedia article describing the Modulo operation, Raymond T. Boute introduces the Euclidean Definition, where the remainder is always positive and therefore consistent with Euclidean Division.

a (the Dividend) modulo n (the Divisor) where q is the quotient and r is the remainder.

$q \in \mathbb{Z}$

$a = n \times q + r\,$

$0 \leq r < |n|$

Two corollaries being:

$n > 0 \Rightarrow q = \left\lfloor \frac{a}{n} \right\rfloor$

$n < 0 \Rightarrow q = \left\lceil \frac{a}{n} \right\rceil$

equivalently:

$q = sgn(n) \left\lfloor \frac{a}{\left|n\right|} \right\rfloor.$

When I verified these statements using Python, I got incorrect results using a -Dividend and a +Divisor. Specifically, I had a = -1.0, n = 7.0 and I was expecting a quotient of 0.0 and a positive remainder of 1.0.

In the Wikipedia article on Euclidean Division it states that the remainder is the only term that needs to be positive.

However, if we have a -Dividend, a zero quotient, and a required positive remainder, then:

-a == n x zero + r

becomes incorrect because:

-a == +r

Therefore, in Euclidean Division, we cannot have a -Dividend?

Where am I reasoning incorrectly?

Many thanks, David.

UPDATE_______________________________________________

Your clarifications have helped me a lot, and have moved me to laughter, when realising my own insanity.

I've always believed Mathematics to be a visual art. Probably because of the visual proof of Pythagorus's Theorem et al. When I expect that something should be visualisable, I get confused if I cannot visualise it.

When reading about Euclidean Division, the visual example made perfect sense, only when a >= 0, b > 0, q >= 0, r >= 0

@ @ @    @ @ @    @ @ @    @ @ @    @


13 swirls (a) divided by 4 (b) gives a (q) of 3 and a (r) of 1

a == bq + r => 13 == 4 * 3 + 1, or 13 swirls == 4 quotients of 3 + a remainder of 1

Which is visually and linguistically intuitive.

But when you have:

-7 swirls (a) divided by 3 (b) giving a (q) of -3 and a (r) of 2, because -7 == 3 * -3 + 2; I become visually lost.

How can -3 go into -7, 3 times and leave remainder 2?

The reason for this confusion is because during the Khan Academy addition videos, I visualised Integers > 0 being Violet Circles, Integers == 0 being Green Circles, and Integers < 0 being Red Circles.

In my head 2 - 2 == 2 + -2 == 2 Violet Circles merging with 2 Red Circles == the creation of 1 Green Circle.

Kind of like Particles Annihilating each other to create other Particles.

The comments system loses all formatting, so my related comments are here:

@Caveman, thank you for constructing those beautiful natural number asterisk sets.

Let's be totally clear on this:

13/4 is 3 sets of 4 union 1 set of 1,


or less ambiguously,

A set of 13 natural numbers asterisks divided into 4 equal natural amounts
is 3 sets of 4 union 1 set of 1.


or if we want to think fractionally,

A set of 13 real number asterisks divided into 4 equal fractional amounts
(of desired and sensible accuracy) is 3 sets 4 + 1/4.


In reality, you cannot divide 12 oranges by -4 oranges because -4 oranges is a figment of your Cartesian imagination.

The notion of a negative amount has been patched by mathematicians to make it a credible public concept. Complex Numbers are an extension of this insanity.

There's no such thing a a negative orange or a negative amount of pizza. You can only divide them into smaller amounts up until you reach the limits of known reality; the Planck length.

The notion of a negative amount is an intellectual conspiracy eloquently constructed to obfuscate reality.

Sure, you can subtract a positive amount from a positive amount, but you cannot do this if the result is negative. 2 oranges minus 3 oranges is not defined in Natures reality.

Negative amounts have been constructed by intellectual Magicians.

I still love you (there's no such thing as negative love; only positive hatred)

From the History Of Negative Numbers:

Although the first set of rules for dealing with negative numbers was stated in the 7th century by the Indian mathematician Brahmaputra, it is surprising that in 1758 the British mathematician Francis Maseres was claiming that negative numbers

"... darken the very whole doctrines of the equations and make dark of the things which are in their nature excessively obvious and simple" .

-
Check your programming, that looks right. –  user68067 Mar 22 '13 at 21:11
You can't have a zero quotient when the $a<0$. (Don't use clever things like "-Dividend" when you also have $a,q,$ etc. That's just confusing. Write $a<0$.) –  Thomas Andrews Mar 22 '13 at 21:19
One further thing to be aware of about the (integer) modulo operator in Python. Taken from the Python documentation: "Python’s x % y returns a result with the sign of y." (See math.fmod). –  kahen Mar 22 '13 at 21:24
When $a<0$ how can $$q=\left\lfloor \frac{a}{|n|}\right\rfloor = 0?$$ If $x<0$ then $\lfloor x\rfloor<0$. –  Thomas Andrews Mar 22 '13 at 21:35
@kahen, what Python (or any other programming language) does has no bearing on what the mathematical definition of the term is (and moreover there might be conflicting definitions, but not in this case). –  vonbrand Mar 22 '13 at 22:14

A quotient of $0.0$ and remainder of $1.0$ is obviously wrong: $7\cdot0+1=1\ne-1=a$.

If $a=-1.0$ and $n=7.0$, you should expect a quotient of $-1$ and a remainder of $6$:

$$-1=7\cdot(-1)+6\;.$$

And this is exactly what the formula $$q=\left\lfloor\frac{a}n\right\rfloor=\left\lfloor\frac{-1}7\right\rfloor=-1$$ gives you.

If you make $a=1$ and $n=-7$, you get

$$\left\lceil\frac{a}n\right\rceil=\left\lceil\frac1{-7}\right\rceil=0$$

and a remainder of $1$, and indeed $1=(-7)\cdot0+1$. It appears that you performed the first calculation, with $a=-1$ and $n=7$, when you thought that you were performing the second, with the signs reversed.

(By the way, the remainder is not always positive in Euclidean division: it’s always non-negative.)

-
@Thomas: Because I’m responding to what he wrote, even if that may be just an artifact of the Python code. –  Brian M. Scott Mar 22 '13 at 21:21
Brain death on my part. Sorry. –  Thomas Andrews Mar 22 '13 at 21:22
@Thomas: Isn’t it amazing how often we can undergo brain death and keep plugging along? :-) –  Brian M. Scott Mar 22 '13 at 21:22
Yeah. I often ignore sloppiness like this in the question, because the questioner is asking a question, hence confused. Then when I read an answer that repeats the sloppiness, since I literally completely ignored it the first time, I don't realize it was in the question. –  Thomas Andrews Mar 22 '13 at 21:24
@Dave: $13$ divided by $-4$? Think of starting with $13$ stars and repeatedly removing $4$ of them until none are left. $3$ removals take you to $*$, so you’re not yet done. One more takes you in the hole by $3$ stars. Thus, it requires $4$ removals, but then you have to add back in $3$ to get to $0$. And sure enough, $13=(-4)(-4)+3$, with quotient $-4$ and non-negative remainder $3$. –  Brian M. Scott Mar 23 '13 at 1:59

This is just a comment I would like to add that this part has a mistake

@ @ @    @ @ @    @ @ @    @ @ @    @

13 swirls (a) divided by 4 (b) gives a (q) of 3 and a (r) of 1


In fact 13/4 = 3 + 1/4, that is 13 divided by 4 is 3 with remainder 1.

To visualize this I fill 4 columns up with 13 points like this:

* * * *
* * * *
* * * *
*


and for another example 19 divided by 5

* * * * *
* * * * *
* * * * *
* * * *


is 3 with remainder 4.

-
It should be clear from these pictures that for any numbers a, b we may find q and r such that $a = bq + r$ with $r \le b$. On the other hand the division algorithm is done in a different more efficient way than this. –  user58512 Mar 23 '13 at 3:30

Like many situations, there are a number of different conventions, many of them are even useful. The important thing is that whichever conventions for quotients and remainders you use, that they be consistent.

And when you get to choose a convention, choose the one most suitable to your purposes.

-