Modular Arithmetic
Modular arithmetic refers to performing arithmetic operations with integers modulo some number n. This creates a cyclic number system from 0 to n-1.
Operations like addition, multiplication, exponentiation are defined to “wrap around” back to 0 after reaching n-1.
Java example:
|
|
C++ example:
|
|
Python example:
|
|
Modular arithmetic appears frequently in combinatorics, number theory, cryptography, and computer algebra systems.
Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” after reaching a certain value, called the modulus. The notation for modular arithmetic is ( a \mod m ), which represents the remainder when ( a ) is divided by ( m ).
Explain the Code
Java
|
|
In Java, the %
operator provides the remainder. But in some cases, it can return a negative number, so the code ensures it’s positive.
C++
|
|
In C++, just like in Java, the %
operator is used for modulus. We also handle negative numbers similarly.
Python
|
|
Python’s %
operator is more forgiving with negative numbers but to maintain uniformity across languages, we use the same approach.
This code performs modular arithmetic, taking care of negative numbers to always return a positive result.
The %
operator is used twice in the code to ensure that the result is a positive number between 0 and (m-1), inclusive.
The first use of
%
, in(a % m)
, computes the initial remainder. However, in languages like Java and C++, this could be negative ifa
is negative.To correct for the negative case, we add
m
to the initial remainder. This doesn’t affect positive remainders but turns a negative remainder into a positive value.The second use of
%
, in((a % m) + m) % m
, takes the result and modulos it again bym
. This is to handle the cases where addingm
resulted in a value greater than or equal tom
.
So the double use of %
ensures that the result is always in the range [0, m-1]
.
Let’s consider m = 5
for the modular arithmetic operation ( a \mod 5 ).
Here is a table that shows the effect of the double use of %
on some sample values of a
:
( a ) | ( a \mod 5 ) | ( (a \mod 5) + 5 ) | ( ((a \mod 5) + 5) \mod 5 ) |
---|---|---|---|
7 | 2 | 7 | 2 |
-7 | -2 | 3 | 3 |
5 | 0 | 5 | 0 |
0 | 0 | 5 | 0 |
-5 | 0 | 5 | 0 |
The columns describe the following:
- ( a ): The original number.
- ( a \mod 5 ): The remainder of ( a ) when divided by 5.
- ( (a \mod 5) + 5 ): Add 5 to the remainder. This turns a negative remainder into a positive one.
- ( ((a \mod 5) + 5) \mod 5 ): Modulo 5 again to ensure the number is between 0 and ( m-1 ).
By following the values across each row, you can see how the double use of %
ensures that you end up with a positive value between 0 and ( m-1 ).