# The modulo operator

1. Jun 17, 2013

### swampwiz

I am confused about this. I have always thought that the modulo operator always has the result of a while number between 0 and the modulo divisor minus 1.

I presume that the terms are called:

a % b = c

a : dividend

b : divisor

c : remainder

a & b > 0 : a % b = b * [ ( a / b ) - INT( a / b ) ]

23 % 4 = 4 * [ ( 23 / 4 ) - INT( 23 / 4 ) ] = 4 * [ { 5 + ( 3 / 4 ) } - INT( { 5 + ( 3 / 4 ) } ) ]

= 4 * [ { 5 + ( 3 / 4 ) } - { 5 } ] = 4 * ( 3 / 4 ) = 3

I am not so sure about the arguments not being positive, but I would think that the divisor must be a positive integer, and a negative dividend is simply added to by some product of the divisor that results in a positive number, which then goes through the modulo operation.

a < 0

d : positive integer

a % b = ( a + d b ) % b

d > INT( | a | / b )

-23 % 4 :

d > INT( | -23 | / 4 ) = INT( 23 / 4 ) = 5 → let d = 6

-23 % 4 = [ -23 + ( 6 ) ( 4 ) ] % 4 = 1 % 4 = 1

And thus there is the relationship that

a % b = { b - [ ( - a ) % b ] } % b

such that if

( a / b ) = INT ( a / b ) → a % b = 0

( a / b ) ≠ INT ( a / b ) → a % b = b - [ ( - a ) % b ]

Finally, I was reading an excerpt from the book Love and Math by Edward Frenkel, in which there is the statement

So presuming that modulo has the same meaning as %, and my earlier definition is accurate, this would mean

2 + 2 = 1 % 3 = 1

2. Jun 17, 2013

### Staff: Mentor

Yes, "modulo" and "%" are synonymous. The % operator is used in many computer programming languages.

3. Jun 18, 2013

### jbunniii

No, it means that if you apply the "modulo 3 operator" to both sides, you get equality.

2 + 2 = 1 modulo 3

means the same thing as

((2 + 2) % 3) = (1 % 3)

4. Jun 18, 2013

### SteveL27

Mod is different in math and computer programming. In math, mod is a binary relation:

a = b (mod n) if n divides a - b

So 5 = 11 (mod 2)

But in programming languages, % is a binary operator, not a relation. So

5 % 2 = 1 and 11 % 2 = 1.

That's because '%' is defined as you indicate ... a % n is the unique b such that a = b (mod n) and 0 <= b < n.

The math and programming mods refer to the same underlying concept; but they are not exactly the same thing. People going from math to programming or vice-versa need to be aware of the distinction.

Math mod-n is a relation that returns true/false for every pair of numbers. Programming mod-n is a operator that returns a single number, given a number and a modulus.

5. Jun 18, 2013

### Staff: Mentor

I don't see the difference. Your example above, with 11 (mod 2) on one side, evaluates to 1. As an equation, you are bringing in another idea, that of equivalence classes. It probably should be written as 5 $\equiv$ 11 (mod 2), meaning that 5 and 11 are in the same equivalence class, modulo 2.

6. Jun 18, 2013

### SteveL27

Didn't I say that?

7. Jun 18, 2013

### Staff: Mentor

11 (mod 2) = 1
5 (mod 2) = 1
5 ≠ 11, but 5 $\equiv$ 11 (i.e., 5 and 11 are in the same equivalence class). That was my point.

Also, you said
The way I see it, 11 (mod 2) and 11 % 2 both evaluate to 1, and are just two ways of saying the exact same thing.

8. Jun 18, 2013

### SteveL27

Lazy markup on my part. I'll strive to do better. I've been writing 'a = b (mod n)' in ASCII for too long.

I would disagree with you on that point. The OP's question (as I understood it) concerned the difference between the math mod and the programming mod.

If you had a programming language that returned 11 in response to the syntax '5 % 2' that would be one heck of a defective programming language.

It's true in math that 5 and 11 are in the same equivalence class mod 2. But in programming, the '%' operator chooses a particular representative from each equivalence class; namely the representative between 0 and n - 1 (inclusive) where n is the modulus.

I would submit that the mathematical mod relation and the programmer's % have different semantics. This is the question the OP was asking about. The math and programming notions of mod do not exactly coincide. 5 % 2 = 11 is the wrong output for a programming language; even though it expresses a mathematical truth.

9. Jun 19, 2013

### rcgldr

That's true when using mod in a congruence relation which normally uses ≡ not =. The modulo operation means the same thing in math as it does in programming when it refers to remainders or modular (finite field) math.

In the case of programming languages division and remainder operations can vary depending if quotients are rounded towards zero (remainder has same sign as dividend) or rounded towards -∞ (remainder has same sign as divisor).

From a mathematical standpoint rouding towards -∞ is better because it's origin independent: if remainder = dividend % divisor, then remainder = (dividend ± (n * divisor)) % divisor, for any integer value of n.

Wiki articles:

http://en.wikipedia.org/wiki/Modular_arithmetic

http://en.wikipedia.org/wiki/Modulo_operation