The Remainder Is Not Unique

It is somewhat surprising that for every given modulus m and number a, there are (infinitely) many valid remainders. Let’s look at another example:
We want to reduce 12 modulo 5. Here are several results which are correct according to the definition:

• 12 ≡2 mod 5, 2 is a valid remainder since 5/(12−2) or 5 x 2 + 2 = 12
• 12 ≡ 22 mod 5, 22 is a valid remainder since 5/(12−22) or 5 x (-2) + 22  = 12
• 12≡−3 mod 5, −3 is a valid remainder since 5/(12-(−3)) or 5 x 3 + (-3) = 12

There is a system behind this behavior. The set of numbers {. . . ,−8,−3,2,7,12,17,22, . . .} is called an equivalence class. There are 4 other equivalence classes for the modulus 5 and in total there are 5 because its modulus 5!

{. . . ,−9,−4,1,6,11,16,21, . . .} we can mark as A

{. . . ,−8,−3,2,7,12,17,22, . . .} we can mark as B

{. . . ,−7,−2,3,8,13,18,23, . . .} we can mark as C

{. . . ,−6,−1,4,9,14,19,24, . . .} we can mark as D

{. . . -10,−5,0,5,10,15,20, . . .} we can mark as E

The most important thing about equivalence class is that all Members of a Given Equivalence Class Behave Equivalently!! Here is example:

If I want to calculate 13 x 6 – 8 mod 5 I have to do it by calculator or at least think about it some time. Its 208-8 mod 5 and that is 0.

But because all members of a given equivalence class behave equivalently I can substitute the numbers with something that easy my calculations. I will now substitute the the numbers as we marked the classes:

C x A – C mod 5

Now I can put to the letter the easiest number from the equivalence classes as follows:

3 x 1 – 3 mod 5 = 0

I have same results with absolutely easy calculation.

Why is this important? Because the core operation of many practical public-key schemes is an exponentiation of the form X to E mod m, where x,e,m are very large integers, say, 2048 bits each. We want to compute 38 mod 7. The first method is the straightforward approach, and for the second one we switch between equivalent classes:

• 3 to 8 = 6561 ≡ 2 mod 7, since 6561 = 937 · 7+2 Note that we obtain the fairly large intermediate result 6561 even though we know that our final result cannot be larger than 6, because its mod 7, i.e. we have only 7 elements in finite set.
• Here is a much smarter method: First we perform two partial exponentiations:
  3 to 8 = 3 to 4 · 3 to 4 = 81 · 81
  We can now replace the intermediate results 81 by another member of the same equivalence class. The smallest positive member modulo 7 in the class is 4 (since 81 = 11 · 7+4). Hence: 38 = 81 · 81 ≡ 4 · 4 = 16 mod 7

From here we obtain the final result easily as 16 ≡ 2 mod 7. Note that we could perform the second method without a pocket calculator since the numbers never become larger than 81. For the first method, on the other hand, dividing 6561 by 7 is mentally already a bit challenging. As a general rule we should remember that it is almost always of computational advantage to apply the modulo reduction as soon as we can in order to keep the numbers small.

Which Remainder DoWe Choose?

By agreement, we usually choose r such that:
0 ≤ r ≤ m−1.
However, mathematically it does not matter which member of an equivalent class we use.