Modular Arithmetic — The Maths of Remainders

Modular arithmetic is the mathematics of remainders — and it shows up everywhere from clock arithmetic to computer science to number theory problems in JEE. Once you understand the core idea, you’ll find it surprisingly powerful for solving problems that look impossibly complex at first glance. Finding the last digit of $7^{100}$ ? Finding the remainder when $2^{50}$ is divided by 7? Modular arithmetic handles these in seconds.

Key Terms & Definitions

Modulo operation: $a \mod m$ is the remainder when $a$ is divided by $m$ . For example, $17 \mod 5 = 2$ because $17 = 3 \times 5 + 2$ .

Congruence: We say $a \equiv b \pmod{m}$ (read: “a is congruent to b modulo m”) if $m$ divides $(a - b)$ . This means $a$ and $b$ give the same remainder when divided by $m$ .

Examples:

$17 \equiv 2 \pmod{5}$ (both give remainder 2 when divided by 5)
$25 \equiv 0 \pmod{5}$ (25 is divisible by 5)
$-3 \equiv 4 \pmod{7}$ (since $-3 - 4 = -7$ , divisible by 7)

Note on negative numbers: In modular arithmetic, we typically prefer positive remainders. $-3 \mod 7 = 4$ (since $-3 = -1 \times 7 + 4$ ).

Modulus (or modulo): The number $m$ in $\pmod{m}$ .

Residue: The remainder itself — the value of $a \mod m$ .

Complete Residue System modulo m: The set $\{0, 1, 2, ..., m-1\}$ — one representative from each congruence class.

Methods and Concepts

Properties of Congruences

If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$ , then:

Addition: $a + c \equiv b + d \pmod{m}$
Subtraction: $a - c \equiv b - d \pmod{m}$
Multiplication: $ac \equiv bd \pmod{m}$
Powers: $a^n \equiv b^n \pmod{m}$ for any positive integer $n$

These properties are the engine of all modular arithmetic calculations. They let us reduce large numbers to small residues at each step.

Finding Last Digits (mod 10)

The last digit of any number is its remainder when divided by 10 — that’s $n \mod 10$ .

The last digit of powers of 7:

$7^1 = 7$ , $7^2 = 49$ (last digit 9), $7^3 = 343$ (last digit 3), $7^4 = 2401$ (last digit 1), $7^5 = ...1$ (last digit 7)

The pattern repeats every 4 powers: 7, 9, 3, 1, 7, 9, 3, 1, …

Last digit of $7^{100}$ : $100 \div 4 = 25$ remainder 0, so $7^{100}$ has same last digit as $7^4 = 1$ .

Last digit of $7^{100}$ is 1.

This cyclicity of last digits is fundamental. Powers of 2 cycle with period 4 (2, 4, 8, 6). Powers of 3 cycle with period 4 (3, 9, 7, 1). Powers of 4 cycle with period 2 (4, 6). Powers of 5 always end in 5.

Fermat’s Little Theorem

For a prime $p$ and integer $a$ with $\gcd(a, p) = 1$ :

a^{p-1} \equiv 1 \pmod{p}

Immediate application: $a^p \equiv a \pmod{p}$

Example: Find $2^{50} \pmod{7}$

$7$ is prime, $\gcd(2,7) = 1$ , so $2^6 \equiv 1 \pmod{7}$ (Fermat’s)

$50 = 8 \times 6 + 2$

$2^{50} = (2^6)^8 \times 2^2 \equiv 1^8 \times 4 \equiv 4 \pmod{7}$

Remainder is 4.

Euler’s Theorem (Generalisation)

For $\gcd(a, m) = 1$ :

a^{\phi(m)} \equiv 1 \pmod{m}

where $\phi(m)$ is Euler’s totient function (count of integers from 1 to $m$ coprime to $m$ ).

For prime $p$ : $\phi(p) = p-1$ , recovering Fermat’s theorem.

For $\phi(m)$ calculation:

$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$
$\phi(mn) = \phi(m)\phi(n)$ when $\gcd(m,n) = 1$ (multiplicative)

Example: $\phi(12) = \phi(4)\phi(3) = 2 \times 2 = 4$ . The integers 1–12 coprime to 12 are: 1, 5, 7, 11 — indeed 4 of them.

Chinese Remainder Theorem (CRT)

If $m_1, m_2, ..., m_k$ are pairwise coprime and $N = m_1 m_2 \cdots m_k$ , then for any $a_1, a_2, ..., a_k$ , there is a unique $x$ with $0 \leq x < N$ such that:

x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad ..., \quad x \equiv a_k \pmod{m_k}

Example: Find $x$ such that $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$ .

List multiples: $x = 2, 5, 8, 11, 14, 17, 20, 23...$ (satisfying first condition) Check which gives remainder 3 when divided by 5: $8 \mod 5 = 3$ . ✓

Answer: $x = 8$ (and $x = 8 + 15k$ for any integer $k$ )

Solved Examples

Easy — CBSE Level

Q: What is the remainder when $2^{10}$ is divided by 3?

$2 \equiv -1 \pmod{3}$

$2^{10} \equiv (-1)^{10} = 1 \pmod{3}$

Remainder = 1. (No need to compute $2^{10} = 1024$ ; just work with the residue.)

Medium — JEE Main Level

Q: Find the last two digits of $3^{100}$ (i.e., $3^{100} \pmod{100}$ )

Use Euler: $\phi(100) = \phi(4)\phi(25) = 2 \times 20 = 40$

$\gcd(3, 100) = 1$ , so $3^{40} \equiv 1 \pmod{100}$

$100 = 2 \times 40 + 20$

$3^{100} = (3^{40})^2 \times 3^{20} \equiv 1 \times 3^{20} \pmod{100}$

$3^{10} = 59049 \equiv 49 \pmod{100}$

$3^{20} = (3^{10})^2 \equiv 49^2 = 2401 \equiv 1 \pmod{100}$

Last two digits of $3^{100}$ are 01.

Hard — JEE Advanced Level

Q: If $p$ is a prime and $p | a^2$ , prove that $p | a$ .

Suppose $p \nmid a$ . Then $\gcd(p, a) = 1$ (since $p$ is prime, its only divisors are 1 and $p$ ). But $p | a^2$ , meaning $a^2 \equiv 0 \pmod p$ . Since $\mathbb{Z}/p\mathbb{Z}$ is a field (for prime $p$ ), it has no zero divisors. So $a \cdot a \equiv 0 \pmod p$ implies $a \equiv 0 \pmod p$ , i.e., $p | a$ . Contradiction. Hence $p | a$ . $\square$

This result is the key lemma in the standard proof that $\sqrt{p}$ is irrational for any prime $p$ .

Exam-Specific Tips

JEE Main: Remainder problems are almost guaranteed. Key: know the cyclicity patterns for powers (units digits cycle with period dividing 4 for most digits). For mod 7, 11, 13, use Fermat’s Little Theorem. For mod 6, use direct computation since $\phi(6) = 2$ .

CBSE Class 10: “Divisibility and remainders” questions often ask: is $n^2 - 1$ divisible by 8 for odd $n$ ? Answer: Yes — $n \equiv 1, 3, 5, 7 \pmod 8$ for odd $n$ , and $n^2 \equiv 1 \pmod 8$ for all of these.

Common Mistakes to Avoid

Mistake 1: $a \equiv b \pmod m$ does NOT mean $a = b$ . It means they have the same remainder. $17 \equiv 2 \pmod 5$ , but $17 \neq 2$ .

Mistake 2: You cannot divide freely in modular arithmetic. $6 \equiv 4 \pmod 2$ does NOT mean $3 \equiv 2 \pmod 1$ after dividing by 2. Division is allowed only when the divisor is coprime to the modulus.

Mistake 3: Forgetting that powers cycle — computing $7^{100}$ by brute force instead of recognising the cycle of length 4 in the units digit.

Mistake 4: Applying Fermat’s Little Theorem with $p$ non-prime. FLT requires $p$ to be prime. For composite moduli, use Euler’s theorem with $\phi(m)$ .

Mistake 5: Getting the remainder of a negative number wrong. $-1 \mod 5 = 4$ (not -1). In modular arithmetic, remainders are always non-negative.

Practice Questions

Q1. Find the remainder when $100!$ is divided by 101.

101 is prime. By Wilson’s Theorem: $(p-1)! \equiv -1 \pmod p$ for prime $p$ . So $100! \equiv -1 \equiv 100 \pmod{101}$ . Remainder = 100.

Q2. What is the units digit of $3^{2025}$ ?

Powers of 3 cycle: 3, 9, 7, 1 (period 4). $2025 \div 4 = 506$ remainder 1. So $3^{2025}$ has same units digit as $3^1 = 3$ . Units digit = 3.

Q3. Show that $n^2 + n$ is always even.

$n^2 + n = n(n+1)$ . Among any two consecutive integers, one is even. So $n(n+1)$ is always even. Alternatively: $n \equiv 0$ or $1 \pmod 2$ . In either case, $n^2 + n \equiv 0 \pmod 2$ .

Q4. Find the last digit of $13^{2024}$ .

Units digit depends on $3^{2024}$ (since $13$ has units digit 3). Cycle of 3: period 4. $2024 \div 4 = 506$ remainder 0. Same as $3^4$ , units digit 1. Last digit = 1.

Q5. Find $x$ such that $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 3$ , with $0 \leq x < 12$ .

From first: $x = 1, 5, 9$ . Check mod 3: $5 \mod 3 = 2$ . ✓ x = 5.

Q6. Prove that $7 | (2^3 - 1)$ and find the smallest $n > 1$ such that $7 | (2^n - 1)$ .

$2^3 - 1 = 7$ , so $7 | 7$ . ✓ By Fermat: $2^6 \equiv 1 \pmod 7$ , so $7 | (2^6 - 1)$ . Check: $2^1=2, 2^2=4, 2^3=1 \pmod 7$ . So order of 2 mod 7 is 3. Smallest $n > 1$ : n = 3.

Q7. What is the remainder when $1! + 2! + 3! + ... + 100!$ is divided by 10?

$n! \equiv 0 \pmod{10}$ for $n \geq 5$ (contains factors 2 and 5). So remainder = $(1! + 2! + 3! + 4!) \mod 10 = (1 + 2 + 6 + 24) \mod 10 = 33 \mod 10 = \textbf{3}$ .

Q8. If $p$ and $q$ are primes and $p + q = 60$ , find all possible pairs.

One of $p$ or $q$ must be 2 (since if both are odd, their sum is even only if both odd — but $60 = \text{even}$ , so either both even or both odd; both even means both = 2, impossible for two primes summing to 60). So one is 2: $q = 58 = 2 \times 29$ . Not prime. OR: both can be odd, and sum to even (60). Try systematically: (7, 53) — both prime ✓; (11, 49) — 49 = 7², not prime; (13, 47) — both prime ✓; (17, 43) — both prime ✓; (19, 41) — both prime ✓; (23, 37) — both prime ✓; (29, 31) — both prime ✓. Pairs: (7,53), (13,47), (17,43), (19,41), (23,37), (29,31).

FAQs

Q: What’s the difference between mod and remainder in programming?

In mathematics, $a \mod m$ is always non-negative. In many programming languages, the % operator can return negative values for negative inputs. In Python, $-3 \% 5 = 2$ (matches mathematical modulo). In C/Java, $-3 \% 5 = -3$ (truncated division). This matters when translating maths to code.

Q: Why does Fermat’s Little Theorem have $p-1$ in the exponent?

Because the nonzero elements of $\mathbb{Z}/p\mathbb{Z}$ form a multiplicative group of order $p-1$ . By Lagrange’s theorem, the order of any element divides the group order. So $a^{p-1} \equiv 1$ . This is a clean algebraic reason.

Q: Is modular arithmetic used in real life?

Absolutely. RSA encryption — which secures every HTTPS connection — is based on Euler’s theorem in modular arithmetic. ISBN barcodes use mod 10. Credit card validation uses mod 10 (Luhn algorithm). GPS error correction uses modular codes.

Q: How do I find $\phi(m)$ quickly?

Factorise $m$ into prime powers: $m = p_1^{a_1} p_2^{a_2} \cdots$ . Then $\phi(m) = m \prod(1 - 1/p_i)$ over distinct prime factors. Example: $\phi(60) = 60(1-1/2)(1-1/3)(1-1/5) = 60 \times 1/2 \times 2/3 \times 4/5 = 16$ .

Q: When can we cancel in modular arithmetic?

If $ac \equiv bc \pmod m$ and $\gcd(c, m) = 1$ , then $a \equiv b \pmod m$ . If $\gcd(c, m) = d \neq 1$ , we can only cancel $c$ if we also reduce the modulus: $a \equiv b \pmod{m/d}$ .