Introduction
Modular arithmetic is a topic that will come under number theory, which roughly speaking is the study of integers and their properties. Modular arithmetic basically calculates the power of remainders when we solve problems. In modular arithmetic, the numbers that we deal with are integers and the operations that we use are addition, subtraction, multiplication and division. The main difference between modular arithmetic and the basic arithmetic we learned is that in modular arithmetic all operations are performed regarding a positive integer, i.e. the modulus.
It is a special type of arithmetic that consists of only integers. The objective of this article is to explain the basics of modular arithmetic and modular congruence. We will also understand the modular arithmetic formula and its various applications.
Modular Arithmetic Definition
In its most elementary form, Modular arithmetic is sometimes referred to as modulus arithmetic or clock arithmetic. We do arithmetic just like counting that resets to zero every time after a certain whole number N greater than one, known as the modulus (mod), has been reached.
Application of modular arithmetic is widely used in the field of computer science and cryptography.
Let n be a positive integer. We denote the set [0,1…(n-1)] by Zn .
Consider two integers x,y to be the same if x and y differ by a multiple of n, and we write this as x=y(mod n) and say that x and y are congruent modulo n. We may omit (mod n) when it is clear from the context. Every integer x is congruent to some y in Zn . When we add or subtract multiples of n from an integer x to reach some yZn , we can say that we are reducing x modulo n, and the value of y is the residue.
Modular Arithmetic Rules
Modular arithmetic follows the same rules as classical arithmetics follow.
Given below modular arithmetic rules
Suppose a,b,c and d are integers and m is a positive integer
Addition Rule
If \[a\equiv b (mod\ m)\] and
\[c\equiv d (mod\ m)\] , then
\[a + c \equiv b + d (mod\ m)\]
Modular Subtraction Rule
If \[a\equiv b (mod\ m)\] and
\[c\equiv d (mod\ m)\], then
\[a - c \equiv b - d (mod\ m)\]
Modular Arithmetic Multiplication Rule
If \[a\equiv b (mod\ m)\] and
\[c\equiv d (mod\ m)\], then
\[a \times c \equiv b \times d (mod\ m)\]
Given below are addition and multiplication modulo n satisfy the following properties:
(x + y) + z = x + (y + z)
(x. y)z = x(y. z)
x + 0 = 0 + x = x
1. x = x. 1
x + (n - x) = (n- x) + x = x
x + y = y + x
x. y = y. x
x. 0 = 0. x
(x + y) + z = x + (y + z)
(x. y)z = x(y. z)
x + 0 = 0 + x = x
1. x = x. 1
x + (n - x) = (n- x) + x = x
x + y = y + x
x. y = y. x
x. 0 = 0. x
Modular Multiplication
Here we have provided modular multiplication rules for two and three elements
\[(a \times b) mod\ m = ((a\ mod\ m) \times (b\ mod\ m) mod\ m)\]
\[(a \times b \times c) mod\ m = ((a\ mod\ m) \times (b\ mod\ m) (c\ mod\ m) mod\ m)\]
The same property we can apply for more than three numbers.
We will understand this with an example:
Example: Find the remainder of 151719 when we divide it by 7.
Solution: Here the numbers are 15,17 and 19. First, we will calculate the individual remainder.
If we divide 15 by 7 we will get 1 as the remainder.
If we divide 17 by 7 we will get 3 as the remainder.
If we divide 19 by 7 we will get 5 as the remainder.
Hence, the remainder of the expression \[\frac{(15\times 17\times 19)}{7}\] will be equal to \[\frac{(1\times 3\times 5)}{7}\].
So, the combined remainder will be equal to the remainder of \[\frac{15}{7}\] i.e. 1.
Division in Modular Arithmetic
We can define modular division only when the modular inverse of the divisor exists. The inverse of an integer ‘x’ is another integer ‘y’ such that it should follow (x*y) % m = 1 where m is known as the modulus.
Consider two number two number 5 and 3
If we have to find the value of 5 mod 3 the value will be 2. It means 2 is the remainder when we divide 5 by 3.
Application of Modular Arithmetic
Modular arithmetic is an extremely flexible problem-solving tool. The following topics are a few applications and extensions of its use:
Divisibility rules
Linear congruence
In Modular arithmetic in cryptography
Public encryption key
Private decryption key
Conclusion:
Consider four integers a,b,c,d and a positive integer m such that \[a\equiv b (mod\ m)\] and \[c\equiv d (mod\ m)\] In modular arithmetic, it holds the following identities
Addition \[a + c \equiv b + d (mod\ m)\]
Subtraction \[a - c \equiv b - d (mod\ m)\]
Multiplication \[a \times c \equiv b \times d (mod\ m)\]
Division \[\frac{a}{e} = \frac{b}{e}(mod \frac{m}{gcd(m,e)})\] where e is a [positive integer that divides a and b
Exponential form \[a^{e} \equiv b^{e} (mod\ m)\] where e is a positive integer.
FAQs on Modular Arithmetic
1.How do you calculate modulo congruence?
For a positive integer n, two integers a and b are said to be congruent modulo n (or a is congruent to b modulo n) if the integer a and b will give the same remainder when they are divided by n (or equivalently if a − b is divisible by n ). It can be expressed in the form of a ≡ b mod n.
2.What is a modular division used for?
Modulo division operation is a way to determine the remainder of a division operation. Instead of returning the result of the division, the modulo operation returns the whole number as a remainder.
3.What are the uses of modular arithmetic?
Following are the uses of modular arithmetic
Simple time calculations
Putting Items In Random Groups
Picking A Random Item
It is used in cryptography
