Modular Arithmetic Definition Formula Properties and Solved Examples
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 Concepts Properties and Problem Solving
1. What is modular arithmetic?
Modular arithmetic is a system of arithmetic where numbers "wrap around" after reaching a certain value called the modulus. It studies numbers under a fixed modulus using the concept of congruence. For example, in modulo 5 arithmetic:
- 7 ≡ 2 (mod 5) because 7 leaves remainder 2 when divided by 5.
- 12 ≡ 2 (mod 5) since 12 − 2 = 10 is divisible by 5.
2. What does “a ≡ b (mod n)” mean?
The statement a ≡ b (mod n) means that a and b leave the same remainder when divided by n. Equivalently, it means:
- n divides (a − b), or
- a − b is a multiple of n.
3. How do you calculate a number modulo n?
To calculate a number modulo n, divide the number by n and take the remainder. Steps:
- Divide a by n.
- Find the remainder r.
- Write the result as a ≡ r (mod n).
4. What are the basic rules of modular arithmetic?
The basic rules of modular arithmetic allow addition, subtraction, and multiplication under a modulus. If a ≡ b (mod n) and c ≡ d (mod n), then:
- Addition: a + c ≡ b + d (mod n)
- Subtraction: a − c ≡ b − d (mod n)
- Multiplication: ac ≡ bd (mod n)
5. How do you solve a congruence equation?
To solve a linear congruence like ax ≡ b (mod n), find x that satisfies the equation under the modulus. Steps:
- Check that gcd(a, n) divides b.
- If gcd(a, n) = 1, find the modular inverse of a.
- Multiply both sides by the inverse.
6. What is a modular inverse?
A modular inverse of a under modulus n is a number x such that ax ≡ 1 (mod n). A modular inverse exists only if gcd(a, n) = 1. Example:
- Find inverse of 4 mod 9.
- 4 × 7 = 28 ≡ 1 (mod 9).
7. What is the difference between modulus and remainder?
The modulus is the number you divide by, while the remainder is the result left after division. In 17 mod 5:
- Modulus = 5
- Remainder = 2
8. How is modular arithmetic used in real life?
Modular arithmetic is used in systems where numbers cycle within a fixed range. Common applications include:
- Clock arithmetic (12-hour or 24-hour time systems)
- Cryptography (RSA encryption)
- Computer science (hash functions, cyclic data structures)
9. What is clock arithmetic in modular arithmetic?
Clock arithmetic is modular arithmetic with modulus 12 (or 24) used to measure time. On a 12-hour clock:
- 10 + 5 = 15
- 15 ≡ 3 (mod 12)
10. What are common mistakes in modular arithmetic?
Common mistakes in modular arithmetic usually involve incorrect handling of remainders or inverses. Frequent errors include:
- Forgetting to reduce the final answer modulo n.
- Assuming a modular inverse exists when gcd(a, n) ≠ 1.
- Incorrect subtraction with negative numbers (always convert to a positive remainder).
