Modular Arithmetic

INTRODUCTION

Modular arithmetic is a branch of mathematics that deals with remainders after division. It is often described as “clock arithmetic” because the numbers wrap around after reaching a certain value, just like the hours on a clock. This concept is fundamental to many areas of mathematics and technology, including cryptography, computer science, and number theory. By learning modular arithmetic, students gain a powerful tool for solving problems that involve remainders, periodicity, and congruence relationships.

In everyday life, modular arithmetic appears when we calculate the day of the week for a future date, determine the position of a clock hand, or encode messages in simple substitution ciphers. Understanding how numbers behave modulo a fixed integer allows us to simplify calculations, detect patterns, and design algorithms that are efficient and secure. For senior secondary students, mastering modular arithmetic opens doors to higher mathematics and practical applications in science and engineering.

MAIN CONTENT

Definition and Notation

In modular arithmetic we compare integers by their remainders when divided by a fixed positive integer called the modulus. Two integers $a$ and $b$ are said to be congruent modulo $n$ if they leave the same remainder upon division by $n$. This relationship is written as

The symbol $\equiv$ denotes congruence, and the subscript $n$ indicates the modulus. The integers $a$ and $b$ are called a congruent pair modulo $n$. For example, $17 \equiv 5 \pmod{12}$ because both $17$ and $5$ leave a remainder of $5$ when divided by $12$.

A worked example

Step 1: Find the remainder of $17$ when divided by $12$.

Step 2: $17 \div 12 = 1$ remainder $5$.

Step 3: Find the remainder of $5$ when divided by $12$.

Step 4: $5 \div 12 = 0$ remainder $5$.

Step 5: Since both remainders are $5$, we have $17 \equiv 5 \pmod{12}$.

Practice Questions

1. State whether $23 \equiv 7 \pmod{8}$.

2. Find a number $x$ such that $x \equiv 4 \pmod{9}$ and $0 \le x < 9$.

3. Verify that $45 \equiv 3 \pmod{12}$.

Answers

1. Yes, because $23$ leaves remainder $7$ when divided by $8$.

2. $x = 4$.

3. $45 \div 12 = 3$ remainder $9$; $9 \div 12 = 0$ remainder $9$, not $3$. Therefore the statement is false.

Basic Operations in Modular Arithmetic

The usual arithmetic operations—addition, subtraction, multiplication, and exponentiation—are well defined in modular arithmetic. If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then

and if $k$ is a positive integer,

These properties allow us to perform calculations modulo $n$ without computing large numbers.

A worked example

Step 1: Compute $7 + 5 \pmod{10}$.

Step 2: $7 + 5 = 12$.

Step 3: $12 \div 10 = 1$ remainder $2$.

Step 4: Thus $7 + 5 \equiv 2 \pmod{10}$.

Step 5: Compute $7 \times 5 \pmod{10}$.

Step 6: $7 \times 5 = 35$.

Step 7: $35 \div 10 = 3$ remainder $5$.

Step 8: Thus $7 \times 5 \equiv 5 \pmod{10}$.

Practice Questions

1. Find $9 - 4 \pmod{7}$.

2. Compute $3^3 \pmod{5}$.

3. Evaluate $(12 + 15) \times 4 \pmod{9}$.

Answers

1. $9 - 4 = 5$, $5 \div 7 = 0$ remainder $5$, so $5 \pmod{7}$.

2. $3^3 = 27$, $27 \div 5 = 5$ remainder $2$, so $2 \pmod{5}$.

3. $12 + 15 = 27$, $27 \div 9 = 3$ remainder $0$, $0 \times 4 = 0$, $0 \pmod{9} = 0$.

Properties of Congruence

Congruence modulo $n$ is an equivalence relation on the set of integers. It satisfies reflexivity, symmetry, and transitivity:

- Reflexive: $a \equiv a \pmod{n}$.

- Symmetric: If $a \equiv b \pmod{n}$ then $b \equiv a \pmod{n}$.

- Transitive: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$ then $a \equiv c \pmod{n}$.

These properties ensure that congruence classes are well defined and can be used to partition the integers into $n$ distinct sets.

A worked example

Step 1: Show that $14 \equiv 2 \pmod{6}$.

Step 2: $14 \div 6 = 2$ remainder $2$, so $14 \equiv 2 \pmod{6}$.

Step 3: Show that $2 \equiv 8 \pmod{6}$.

Step 4: $8 \div 6 = 1$ remainder $2$, so $8 \equiv 2 \pmod{6}$.

Step 5: By transitivity, $14 \equiv 8 \pmod{6}$.

Practice Questions

1. Verify that $19 \equiv 4 \pmod{5}$.

2. If $x \equiv 3 \pmod{7}$ and $y \equiv 3 \pmod{7}$, what can you say about $x - y$ modulo $7$?

3. Prove that $a \equiv b \pmod{n}$ implies $-a \equiv -b \pmod{n}$.

Answers

1. $19 \div 5 = 3$ remainder $4$, so true.

2. $x - y \equiv 0 \pmod{7}$.

3. Multiply both sides by $-1$: $-a \equiv -b \pmod{n}$.

Solving Simple Congruences

A linear congruence has the form $ax \equiv b \pmod{n}$. To solve it, we find an integer $x$ such that the equation holds. If $\gcd(a,n)=1$, then a unique solution modulo $n$ exists and can be found using the multiplicative inverse of $a$ modulo $n$. If $\gcd(a,n)\neq 1$, solutions exist only if $b$ is divisible by $\gcd(a,n)$.

A worked example

Step 1: Solve $3x \equiv 4 \pmod{7}$.

Step 2: Since $\gcd(3,7)=1$, find the inverse of $3$ modulo $7$.

Step 3: $3 \times 5 = 15 \equiv 1 \pmod{7}$, so $5$ is the inverse.

Step 4: Multiply both sides by $5$: $x \equiv 4 \times 5 \pmod{7}$.

Step 5: $4 \times 5 = 20 \equiv 6 \pmod{7}$.

Step 6: Thus $x \equiv 6 \pmod{7}$.

Practice Questions

1. Solve $5x \equiv 2 \pmod{9}$.

2. Determine whether $6x \equiv 4 \pmod{12}$ has solutions.

3. Find all solutions of $2x \equiv 8 \pmod{14}$.

Answers

1. $5^{-1}\equiv 2$, $x\equiv 4 \pmod{9}$.

2. $\gcd(6,12)=6$, $4$ is not divisible by $6$, so no solution.

3. $\gcd(2,14)=2$, divide by $2$: $x \equiv 4 \pmod{7}$, solutions $x=4,11$.

Applications of Modular Arithmetic

Modular arithmetic is used in many practical contexts. One common application is in determining the day of the week for a given date. Since there are $7$ days in a week, we can compute the day by taking the date modulo $7$. Another application is in cryptography: the RSA encryption algorithm relies on modular exponentiation and the Chinese Remainder Theorem to secure digital communication.

A worked example

Step 1: Find the day of the week for 15 March 2025, assuming 1 January 2025 is a Wednesday (day $3$ if we let Monday $1$).

Step 2: Compute the number of days from 1 January to 15 March: 31 (January) + 28 (February) + 15 = 74.

Step 3: $74 \div 7 = 10$ remainder $4$.

Step 4: Add the remainder to the starting day: $3 + 4 = 7$.

Step 5: Since $7$ corresponds to Sunday, 15 March 2025 falls on a Sunday.

Practice Questions

1. If 1 January 2026 is a Friday (day $5$), what day is 30 April 2026?

2. Compute $7^{4} \pmod{13}$.

3. In a simple Caesar cipher with shift $3$, what letter replaces $M$?

Answers

1. Days from 1 Jan to 30 Apr: 31+28+31+30=120; $120 \div 7 = 17$ remainder $1$; $5+1=6$ → Saturday.

2. $7^2=49\equiv10$, $7^4=(7^2)^2\equiv10^2=100\equiv9$; answer $9$.

3. $M$ shifted by $3$ gives $P$.

SUMMARY

Modular arithmetic simplifies problems involving remainders and periodicity by treating numbers as equivalent when they share the same remainder modulo a chosen modulus. The congruence relation $a \equiv b \pmod{n}$ forms the foundation of this system, allowing us to perform addition, subtraction, multiplication, and exponentiation in a modular context. By understanding the properties of congruence, solving linear congruences, and applying modular arithmetic to real-life scenarios, students gain a versatile mathematical tool that extends to advanced topics such as cryptography and number theory. Mastery of these concepts equips learners with the ability to recognize patterns, simplify calculations, and appreciate the elegance of mathematics in everyday life.

EVALUATION

1. Compute $14 \times 9 \pmod{11}$.

2. Solve $4x \equiv 3 \pmod{7}$.

3. Find the remainder when $1234^{5}$ is divided by $13$.

4. If $x \equiv 5 \pmod{9}$ and $x \equiv 2 \pmod{7}$, what is $x \pmod{63}$?

5. Determine whether $8x \equiv 6 \pmod{10}$ has a solution and find all such $x$ modulo $10$.