What is the Relationship Between Modulo and Remainders in Math and Programming?

[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

2 + 2 = 1 modulo 3

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

2 + 2 = 1 % 3 = 1

 

[Mark44]

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

 

[jbunniii]

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

2 + 2 = 1 % 3 = 1

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

Using your % notation,

2 + 2 = 1 modulo 3

means the same thing as

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

 

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

 

[Mark44]

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.

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.

 

[SteveL27]

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.

So 5 = 11 (mod 2)

Didn't I say that?

 

[Mark44]

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

Math mod-n is a relation that returns true/false for every pair of numbers.

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.

 

[SteveL27]

5 ≠ 11, but 5 ##\equiv## 11 (i.e., 5 and 11 are in the same equivalence class). That was my point.

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

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.

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.

 

[rcgldr]

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

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.

negative numbers

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