Modulo Arithmetic
Introduction
When dividing a number a by another number b, the result can either be a complete division with no remainder or leave a remainder.
For instance, consider dividing 15 by 5:
15÷5=3 with no remainder.
Here, 15 is divided by 5 with a quotient of 3 and no remainder. Thus, the quotient (q) is 3, and the remainder (r) is 0.
Now, let’s examine another example, dividing 17 by 5:
17÷5=3 remainder 2.
In this case, 17 divided by 5 gives a quotient of 3 and a remainder of 2. So, the quotient (q) is 3, and the remainder (r) is 2.
Therefore we can say, that when a number a is divided by a number b we can write it in the form a = q*b + r.
This form is called the Quotient-Remainder Form.
Let’s understand that in detail:
Quotient-Remainder Theorem
The Quotient-Remainder Theorem is a fundamental concept that states that for any integer a and any positive integer n, you can express a as: a=n×q+r where 0<=r<n
Here, q is the quotient and r is the remainder, where 0≤r<n.
This means when you divide a by n, you get a whole number quotient and a remainder that is always less than n.
For example, dividing 23 by 7 gives 23=7×3+2, where 3 is the quotient and 2 is the remainder.
Since we have learned the Quotient-Remainder Theorem, let’s jump to the main topic of this section Modular Arithmetic.
Modular Arithmetic
Modular arithmetic is an essential mathematical concept that revolves around the "mod" function, which focuses on finding remainders after division.
Often referred to as “clock arithmetic,” it is a system where numbers loop back after reaching a specific value called the modulus.
Learning modular arithmetic helps students understand how calculations behave cyclically, making it easier to handle problems involving large numbers, efficient algorithms, and secure encryption techniques.
Let’s explore modular arithmetic with a simple example:
Consider 17%5. Here, we are dividing 17 by 5 and finding the remainder.
When 17 is divided by 5, it goes 3 times (since 5×3=15) with a remainder of 2. So, 17%5=2.
This behavior is like a clock: if you move 17 hours ahead from 12 o'clock, you'll end up at 2 o'clock, showing how numbers wrap around in modular arithmetic.
Definition
Modular arithmetic involves working with numbers under a defined range, known as the modulus. For two integers a and b, and a positive integer n, a is said to be congruent to b modulo n if their difference is divisible by n.
This is written as a≡b (mod n)
For example, 17≡2 (mod 5) since 17 and 2 differ by a multiple of 5 (17 - 2 = 15, which is divisible by 5).
Let’s understand a theorem that would help us how to represent a number with the help of the quotient and remainder.
Modular Addition
Modular addition involves adding two numbers and then taking the result modulo a specified modulus.
(a+b) mod m=((a mod m)+(b mod m)) mod m
Compute the remainders of a and b when divided by m,
Add these remainders. Take the result modulo m.
Example:
Let a=14, b=9, and m=5 :
(14+9) mod 5 = ((14 mod 5)+(9 mod 5)) mod 5 = (4+4) mod 5 = 3.
Now, let’s prepare for the explanation of modular subtraction, which follows a similar approach but involves adjusting for negative results to ensure they fall within the valid range.
Modular Subtraction
Modular subtraction involves subtracting one number from another and then taking the result modulo a specified modulus. The formula is:
(a-b) mod m=((a mod m)-(b mod m)) mod m
Compute the remainders of a and b when divided by m, Subtract these remainders. Take the result modulo m.
Let’s try to understand it with some examples:
Example 1
Let a=14, b=9, and m=5 :
(14-9) mod 5 = ((14 mod 5)-(9 mod 5)) mod 5 = (4-4) mod 5 = 0.
Here, in the above example, we are getting our answer as 0 which is correct as it follows the properties of the Quotient - Remainder Theorem where 0<=r < m.
Example 2
Let a=11, b=19, and m=5 :
(11-19) mod 5 = ((11 mod 5)-(19 mod 5)) mod 5 = (1-4) mod 5 = (-3) mod 5.
Now the equation is getting simplified to -3 mod 5, so till now we have been taking a modulo of a positive number, Let’s understand how to take the modulo of a negative number.
Modulo with a negative number
When dealing with modular arithmetic, handling negative numbers can be tricky. The goal is to ensure that results are always non-negative and within the range from 0 to m−1.
If the computed remainder r is negative, it falls outside this range. Adding m shifts the result into the correct range.
Let’s understand with an example: Compute −7 mod 5
Compute Remainder: −7 mod 5 yields remainder -2 Because -7 mod 5 gives quotient as -1 and remainder as -2.
Since the remainder -2 does not lie in the range (0 to 4), add m to make it fall in the desired range, So -2 + 5 = 3.
So we can conclude, that when the remainder r is negative after performing the modulo operation, adding m shifts remainder(r) into the non-negative range, ensuring it falls between 0 and m−1.
This adjustment is crucial for maintaining consistency in modular arithmetic operations.
Therefore in the above example 2, to shift -3 to the desired range from 0 to m-1 we add it with 5, so after shifting the number becomes -3 + 5 i.e. 2.
So, now the equation for subtraction boils down to
(a-b) mod m=((a mod m)-(b mod m) + m) mod m
Modular Multiplication
Modular multiplication involves multiplying two numbers and then taking the result modulo a specified modulus.
(a×b) mod m=((a mod m)×(b mod m)) mod m
Compute the remainders of a and b when divided by m, Multiply these remainders and take the result modulo m.
Example:
Let a=14, b=9, and m=5:
So, (14×9) mod 5= ((14 mod 5)×(9 mod 5)) mod 5 = (4 × 4) % 5 = 16 % 5 = 1.
Modulo Division
Modulo division is different from modulo addition, subtraction, and multiplication.
(a/b) mod m is not equal to ((a mod m)/(b mod m)) mod m
It can be calculated as (a / b) mod m = (a * (inverse of b if exists)) mod m.
Let’s understand Modulo Inverse to find modulo division.
Modulo Inverse
The modular inverse of a number a modulo m is a number b such that:
(a×b) mod m = 1
In other words, b is the modular inverse of a if multiplying a by b yields a result congruent to 1 modulo m.
The modular inverse exists if and only if a and m are coprime (i.e., their greatest common divisor is 1).
Example: Let a=3 and m=7 :
We need to find b such that (3×b) mod 7=1.
Testing values, we find that 3×5=15 and 15 mod 7=1.
Thus, the modular inverse of 3 modulo 7 is 5.
For now, let's keep it to this only. We will discuss the modulo Inverse and modulo exponentiation in the detail in Basic Math 2 section.