# Modulo Operations in Programming With Negative Results

In programming, the modulo operation gives the remainder or signed remainder of a division, after one integer is divided by another integer. It is one of the most used operators in programming. This article discusses when and why the modulo operation yields a negative result.

Examples:

In C, 3 % 2 returns 1. However, -3 % 2 is -1 and 3 % -2 gives 1.

In Python, -3 % 2 is 1 and 3 % -2 is -1.

Hence, it’s evident that the same expression of -3 % 2 gives different results in different programming languages. This result is more related to mathematics rather than programming. The mathematics mentioned here will help in understanding the questions a little more easily. To understand why this happens, a little knowledge about Euclidean Division and a few points related to Modular Arithmetic is needed.

Euclidean Division: In arithmetic, Euclidean division or division with the remainder is the process of dividing one integer (the dividend) by another (the divisor), in such a way that it produces a quotient and a remainder smaller than the divisor.

Given two integers a and b ( where b ≠ 0 ), there exists unique integers q and r such that:

a = bq + r ( 0 ≤ r < |b| ) where, |b| denotes the absolute value of b.
In the above equation, each of the four integers has its own name i.e.,
a is called the dividend.
b is called the divisor.
q is called the quotient.
r is called the remainder.
For Example:
If a = 9 and b = 4, then q = 2 and r = 1, since 9 = 4 × 2 + 1.
If a = -9 and b = 4, then q = -3 and r = 3, since -9 = 4 × -3 + 3.
If a = 9 and b = -4, then q = -2 and r = 1, since 9 = -4 × -2 + 1.
If a = -9 and b = -4, then q = 3 and r = 3, since -9 = -4 × 3 + 3.
Explanations of the above examples:
The first example is self-explanatory as 9/4 gives quotient 2 and remainder 1.
The second example (-9/4) gives quotient -3 and not -2. This happens because if we take -2 as quotient then -9 = 4 × -2 + (-1). A remainder of -1 is generated which does not fulfill the conditions of the Euclidean division. It doesn’t make -9/4 = -2 wrong it is just not what we need in this case.
Modular Arithmetic: In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” when reaching a certain value, called the modulus.
Congruence: Given any integer N, called a modulus, two integers a and b are said to be congruent modulo N if they produce the same remainder when divided by N i.e.,
a = pN + r and b = qN + r, where 0 ≤ r < |N| is the common remainder.
Congruence modulo N is denoted as a ≡ b (mod N) where the parentheses means that (mod N) applies to the entire equation, not just to the right-hand side ( here b).
Examples:-5 ≡ 2 (mod 7)
-14 ≡ 19 (mod 11)
Analyzing the first example. -5 = 7 × -1 + 2 and 2 = 7 × 0 + 2. Both -5 and 2 leave the same remainder 2 when divided by 7. Hence, they are congruent to each other. Similarly, -14 = 11 × -2 + 8 and 19 = 11 × 1 + 8. Both -14 and 19 leave the same remainder 8 when divided by 11. Hence, they are congruent to each other.
Congruence Classes: Suppose a mod N leaves a remainder r when divided by N satisfying the condition 0 ≤ r < |N|. The set of all the integers congruent to a mod N is called the congruence class of the integer a mod N. For Example:
The congruence class of 3 mod 2 is {…, -5, -3, -1, 1, 3, 5, 7, … }.
The congruence class of 7 mod 4 is {…, -9, -5, -1, 3, 7, 11, … }.
Select any integer from the congruence class of the integer a mod N as a representative of that class. In mathematics, the least positive residue, the smallest non-negative integer that belongs to that class is chosen as the representative. For Example:
The representative of congruence class 3 mod 2 is 1.
The representative of congruence class 7 mod 4 is 3.
The Least positive residue is chosen because it is the remainder produced after the Euclidean division.
Representative is chosen by Programming languages:
If both a and N are positive, in all the programming languages, a mod N is the remainder of the Euclidean division. However, the difference in the result is observed when either a or N is negative or both are negative. The answer of a mod N then depends on the implementation of a mod N used by the programming language. The remainder produced by all the programming languages does follow a certain criterion i.e., |r| < |N|.
However, this still leaves a sign ambiguity if the remainder is non-zero, then two possible choices for the remainder occur, one negative (the greatest negative element of the congruence class of a mod N) and the other positive (the least positive element of the congruence class of a mod N). Other elements do not satisfy the criteria of |r| < |N|.
That is why there are different results when -3 mod 2 performed in C and Python. Both of them are producing the correct results. They are just not outputting the mathematically chosen representative of a mod N.
In C, -3 mod 2 returns -1, which is a member class of -3 mod 2. However, Python returns 1, which is again a member class of -3 mod 2. Also, both the answer returned to satisfy the given condition of |r| < |N|.
Implementations of % in Programming languages: Many programming languages like C, C++, Java, JavaScript use an implementation similar to the one given below. The remainder is returned according to the equation
r = a – N*trunc(a/N)
Below is the implementation of the above explanation:
C++14
#include
using namespace std;
int truncMod(int a, int n)
{
int q = a / n;
return a - n * q;
}
int main()
{
int a, b;
a = 9;
b = 4;
cout