Login
OR
Don't worry. We'll fix this for you!
Imagine you have a clock showing hours from 1 to 12. If it is 9 o'clock now, what time will it be 5 hours later? You might quickly say 2 o'clock. This is because after 12, the clock resets back to 1. This kind of arithmetic, where numbers "wrap around" after reaching a certain value, is called modular arithmetic.
Modular arithmetic is essentially arithmetic with remainders. It plays a crucial role in number theory and is widely used in competitive exams, cryptography, computer science, and many real-life applications involving cyclic or repetitive patterns.
In modular arithmetic, numbers are considered equivalent if they leave the same remainder when divided by a fixed positive integer called the modulus. This idea helps simplify complex calculations by focusing only on remainders.
In this chapter, we will explore modular arithmetic from the ground up, starting with the division algorithm, moving to congruences, residue classes, and finally applications such as solving equations and cryptographic basics.
The foundation of modular arithmetic is the division algorithm. It formalizes the idea of dividing one integer by another and finding a quotient and remainder.
Division Algorithm Statement: For any integers \( a \) and \( b \) with \( b > 0 \), there exist unique integers \( q \) (quotient) and \( r \) (remainder) such that
This means when you divide \( a \) by \( b \), you get a quotient \( q \) and a remainder \( r \) such that the remainder is always less than the divisor \( b \).
graph TD A[Input integers a and b (b > 0)] A --> B[Calculate quotient q = floor(a / b)] B --> C[Calculate remainder r = a - bq] C --> D[Express a = bq + r] D --> E{Is 0 ≤ r < b?} E -->|Yes| F[Division Algorithm holds] E -->|No| G[Recalculate q and r]Using the division algorithm, we can define the concept of congruence modulo \( n \).
Definition: Two integers \( a \) and \( b \) are said to be congruent modulo \( n \) (written as)
This means \( a \) and \( b \) leave the same remainder when divided by \( n \), or equivalently, their difference \( a - b \) is exactly divisible by \( n \).
For example, \( 17 \equiv 5 \pmod{12} \) because \( 17 - 5 = 12 \), which is divisible by 12.
Figure: Numbers arranged on a circle divided into 7 parts representing residue classes modulo 7. Numbers congruent modulo 7 lie on the same segment.
The set of all possible remainders when dividing by \( n \) is called the set of residues modulo \( n \). These residues form residue classes, which are equivalence classes of integers having the same remainder modulo \( n \).
For example, modulo 5, the residue classes are:
Arithmetic operations such as addition, subtraction, and multiplication can be performed on these residue classes, and the results are taken modulo \( n \) to keep them within the set of residues.
Here are the addition and multiplication tables modulo 5:
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| x | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
These tables illustrate that modular arithmetic is closed under addition and multiplication, meaning the result always stays within the set of residues modulo \( n \).
Step 1: Express 12345 in parts to simplify modulo 7 calculation.
Write 12345 as \( 12000 + 345 \).
Step 2: Calculate \( 12000 \bmod 7 \).
Note that \( 12000 = 12 \times 1000 \).
Calculate \( 12 \bmod 7 = 5 \) and \( 1000 \bmod 7 \).
To find \( 1000 \bmod 7 \), divide 1000 by 7:
7 x 142 = 994, remainder = 6, so \( 1000 \equiv 6 \pmod{7} \).
Therefore, \( 12000 \equiv 5 \times 6 = 30 \equiv 30 \bmod 7 \).
Calculate \( 30 \bmod 7 \): 7 x 4 = 28, remainder 2, so \( 30 \equiv 2 \pmod{7} \).
Step 3: Calculate \( 345 \bmod 7 \).
7 x 49 = 343, remainder 2, so \( 345 \equiv 2 \pmod{7} \).
Step 4: Add the two remainders modulo 7:
\( 2 + 2 = 4 \), so \( 12345 \equiv 4 \pmod{7} \).
Answer: The remainder when 12345 is divided by 7 is 4.
Step 1: Understand that to solve \( 3x \equiv 4 \pmod{7} \), we need to find the modular inverse of 3 modulo 7.
The modular inverse of 3 modulo 7 is a number \( y \) such that \( 3y \equiv 1 \pmod{7} \).
Step 2: Find \( y \) by trial:
So, \( y = 5 \) is the modular inverse of 3 modulo 7.
Step 3: Multiply both sides of the original congruence by 5:
\( 5 \times 3x \equiv 5 \times 4 \pmod{7} \)
\( (5 \times 3) x \equiv 20 \pmod{7} \)
Since \( 5 \times 3 = 15 \equiv 1 \pmod{7} \), this simplifies to
\( x \equiv 20 \pmod{7} \).
Calculate \( 20 \bmod 7 \): 7 x 2 = 14, remainder 6, so \( x \equiv 6 \pmod{7} \).
Answer: The solution is \( x \equiv 6 \pmod{7} \), meaning all integers of the form \( x = 6 + 7k \) for any integer \( k \) satisfy the congruence.
Step 1: Recall that a number is divisible by 9 if the sum of its digits is divisible by 9.
This is because \( 10 \equiv 1 \pmod{9} \), so powers of 10 are congruent to 1 modulo 9.
Step 2: Sum the digits of 123456:
1 + 2 + 3 + 4 + 5 + 6 = 21
Step 3: Check if 21 is divisible by 9:
21 / 9 = 2 remainder 3, so 21 is not divisible by 9.
Answer: Therefore, 123456 is not divisible by 9.
Step 1: Note that the moduli 3, 5, and 7 are pairwise coprime.
Step 2: Compute the product of moduli:
\( N = 3 \times 5 \times 7 = 105 \).
Step 3: Define \( N_i = \frac{N}{n_i} \) for each modulus \( n_i \):
Step 4: Find the modular inverse \( M_i \) of \( N_i \) modulo \( n_i \), i.e., find \( M_i \) such that
\( N_i \times M_i \equiv 1 \pmod{n_i} \).
Step 5: Compute the solution using the formula:
\[ x \equiv \sum_{i=1}^{3} a_i N_i M_i \pmod{N} \]
where \( a_1 = 2, a_2 = 3, a_3 = 2 \).
Calculate:
\( x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \pmod{105} \)
\( x \equiv 140 + 63 + 30 = 233 \pmod{105} \)
Calculate \( 233 \bmod 105 \): 105 x 2 = 210, remainder 23.
Answer: \( x \equiv 23 \pmod{105} \). So the smallest positive solution is \( x = 23 \).
Step 1: Use modular exponentiation to simplify the calculation by repeatedly squaring and reducing modulo 13.
Step 2: Calculate powers of 7 modulo 13:
Step 3: Express 100 as sum of powers of 2:
100 = 64 + 32 + 4
Step 4: Calculate \( 7^{100} \equiv 7^{64} \times 7^{32} \times 7^{4} \pmod{13} \)
\( \equiv 9 \times 3 \times 9 = (9 \times 3) \times 9 = 27 \times 9 \pmod{13} \)
Calculate \( 27 \bmod 13 = 27 - 26 = 1 \), so
\( 7^{100} \equiv 1 \times 9 = 9 \pmod{13} \).
Answer: The remainder when \( 7^{100} \) is divided by 13 is 9.
When to use: When dealing with large numbers or powers in competitive exam problems.
When to use: To avoid large number computations and reduce calculation time.
When to use: When solving linear congruences where modular inverse is required.
When to use: When multiple modular equations need to be solved simultaneously.
When to use: Quick divisibility tests in exam settings.
Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.
Go to practice →
Your Score
Your Rank
| Rank | Name | Score |
|---|