Modular Arithmetic

Overview

Welcome to the chapter on Modular Arithmetic, a foundational concept in Number Theory that is indispensable for a wide array of applications in computer science and data science. At its core, modular arithmetic is about working with integers and their remainders after division, effectively creating a system where numbers "wrap around" upon reaching a certain value. This cyclical nature allows us to model phenomena that repeat, manage finite data structures, and perform computations efficiently within constrained systems.

For your CMI studies, a solid grasp of modular arithmetic is not merely academic; it's a critical skill for understanding and solving problems in computational mathematics. You'll find its principles underpinning essential data science domains such as cryptography (e.g., public-key encryption, hashing algorithms), error detection and correction codes, random number generation, and efficient data indexing. Proficiency in this area is frequently tested in CMI examinations, not just for direct application but also as a fundamental tool for tackling more complex algorithmic and computational challenges. Mastering this chapter will equip you with a powerful mathematical toolkit, enhancing your problem-solving capabilities and preparing you for advanced topics in secure data handling and efficient algorithm design.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Congruence Relations | Define congruence and explore its fundamental properties. |
| 2 | Operations in Modular Arithmetic | Perform addition, subtraction, multiplication, and division. |

---

Learning Objectives

---

Now let's begin with Congruence Relations...

Part 1: Congruence Relations

Introduction

Congruence relations form a fundamental building block in number theory, providing a powerful framework for analyzing divisibility and remainders. This topic is essential for the CMI Masters in Data Science exam as it underpins various algorithms and theoretical concepts in cryptography, error-correcting codes, and computational number theory. Understanding congruence allows us to simplify complex arithmetic problems by focusing on the properties of integers modulo a given number. These notes will cover the core definitions, properties, and applications of congruence relations, preparing you to tackle diverse problems in the CMI exam effectively.

---

---

Key Concepts

1. Definition and Basic Properties

The congruence relation $a \equiv b \pmod m$ establishes an equivalence relation on the set of integers $\mathbb{Z}$.

Properties of Congruence:

Reflexivity: For any integer $a$, $a \equiv a \pmod m$.

Explanation:* $a-a = 0$, and $m$ divides $0$ (since $0 = 0 \cdot m$).

Symmetry: If $a \equiv b \pmod m$, then $b \equiv a \pmod m$.

Explanation:* If $m \mid (a-b)$, then $a-b=km$. This implies $b-a = -km = (-k)m$, so $m \mid (b-a)$.

Transitivity: If $a \equiv b \pmod m$ and $b \equiv c \pmod m$, then $a \equiv c \pmod m$.

Explanation:* If $m \mid (a-b)$ and $m \mid (b-c)$, then $a-b = k_1m$ and $b-c = k_2m$ for some integers $k_1, k_2$.
Adding these equations: $(a-b) + (b-c) = k_1m + k_2m$

Since $k_1+k_2$ is an integer, $m \mid (a-c)$, so $a \equiv c \pmod m$.

Algebraic Properties:

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

Addition: $a+c \equiv b+d \pmod m$.

Explanation:* $(a+c)-(b+d) = (a-b)+(c-d)$. Since $m \mid (a-b)$ and $m \mid (c-d)$, $m$ divides their sum.

Subtraction: $a-c \equiv b-d \pmod m$.

Explanation:* Similar to addition, $m$ divides $(a-b)$ and $m$ divides $(c-d)$, so $m$ divides $(a-b)-(c-d)$.

Multiplication: $ac \equiv bd \pmod m$.

Explanation:* $ac-bd = ac-bc+bc-bd = c(a-b) + b(c-d)$. Since $m \mid (a-b)$ and $m \mid (c-d)$, $m$ divides both terms, and thus their sum.

Exponentiation: $a^n \equiv b^n \pmod m$ for any positive integer $n$.

Explanation:* This follows from repeated application of the multiplication property.

Division (with caution): If $ac \equiv bc \pmod m$, then $a \equiv b \pmod{m/\gcd(c,m)}$.

Explanation:* If $ac \equiv bc \pmod m$, then $m \mid c(a-b)$. Let $d = \gcd(c,m)$. Then $m = d \cdot m'$ and $c = d \cdot c'$ where $\gcd(c',m')=1$.
So $d \cdot m' \mid d \cdot c' (a-b)$, which implies $m' \mid c'(a-b)$.
Since $\gcd(c',m')=1$, we must have $m' \mid (a-b)$.
Thus, $a \equiv b \pmod{m'}$, or $a \equiv b \pmod{m/\gcd(c,m)}$.
Crucial point: If $\gcd(c,m)=1$, then $a \equiv b \pmod m$. This means we can "divide by $c$" if $c$ is coprime to $m$.

Worked Example:

Problem: Find the remainder when $2^{100}$ is divided by $3$.

Solution:

Step 1: Simplify the base modulo $3$.

Step 2: Apply the exponentiation property.

Step 3: Evaluate the result.

Answer: $1$

---

2. Residue Classes and Systems

The congruence relation partitions the set of integers $\mathbb{Z}$ into disjoint sets called residue classes (or congruence classes) modulo $m$. Each residue class consists of all integers that have the same remainder when divided by $m$.

For example, modulo $3$, the residue classes are:
$[0]_3 = \{\dots, -6, -3, 0, 3, 6, \dots\}$
$[1]_3 = \{\dots, -5, -2, 1, 4, 7, \dots\}$
$[2]_3 = \{\dots, -4, -1, 2, 5, 8, \dots\}$

Complete Residue System:
A set of integers $\{r_1, r_2, \dots, r_m\}$ is called a complete residue system modulo $m$ if every integer is congruent to exactly one element in the set. The most common complete residue system is $\{0, 1, 2, \dots, m-1\}$, which are the least non-negative residues.

Worked Example:

Problem: Identify the complete residue system modulo $5$ from the set $\{-10, -3, 2, 9, 16\}$.

Solution:

Step 1: Find the least non-negative residue for each element modulo $5$.

Step 2: Check if the set of residues forms $\{0, 1, 2, 3, 4\}$.

The set of residues is $\{0, 2, 2, 4, 1\}$. This set contains $2$ twice and misses $3$.

Answer: The given set is not a complete residue system modulo $5$ because it contains duplicate residues ($2$) and misses one residue ($3$). A valid complete residue system would be $\{0, 1, 2, 4, 16\}$ or $\{-10, 16, 2, 9, -1\}$.

---

3. Modular Arithmetic Operations

Modular arithmetic is the system of arithmetic for integers, where numbers "wrap around" when reaching a certain value—the modulus. This is precisely the arithmetic of residue classes.

Operations on Residue Classes:

If $[a]_m$ and $[b]_m$ are two residue classes modulo $m$, their sum, difference, and product are defined as:

Addition: $[a]_m + [b]_m = [a+b]_m$

Subtraction: $[a]_m - [b]_m = [a-b]_m$

Multiplication: $[a]_m \cdot [b]_m = [ab]_m$

These operations are well-defined, meaning the result does not depend on the choice of representatives $a$ and $b$ from their respective classes.

Worked Example:

Problem: Calculate $(17 + 23) \pmod 7$ and $(17 \times 23) \pmod 7$.

Solution:

Step 1: Simplify the numbers modulo $7$.

Step 2: Perform addition modulo $7$.

Step 3: Perform multiplication modulo $7$.

Answer: $(17 + 23) \pmod 7 = 5$ and $(17 \times 23) \pmod 7 = 6$.

---

---

4. Solving Linear Congruences

A linear congruence is an equation of the form $ax \equiv b \pmod m$. Solving this means finding all integers $x$ that satisfy the congruence.

Modular Inverse:
If $ax \equiv 1 \pmod m$ has a solution, $x$ is called the modular multiplicative inverse of $a$ modulo $m$. This exists if and only if $\gcd(a,m)=1$. If an inverse $a^{-1}$ exists, then $ax \equiv b \pmod m$ can be solved by multiplying both sides by $a^{-1}$: $x \equiv a^{-1}b \pmod m$. Extended Euclidean Algorithm is commonly used to find modular inverses.

Worked Example:

Problem: Solve the linear congruence $6x \equiv 9 \pmod{15}$.

Solution:

Step 1: Calculate $d = \gcd(a,m)$.

Step 2: Check if $d$ divides $b$.

Since $3 \mid 9$, there are $3$ incongruent solutions modulo $15$.

Step 3: Solve the reduced congruence.

Divide $a, b, m$ by $d=3$:

Step 4: Find the unique solution to the reduced congruence.
We need to find $x$ such that $2x \equiv 3 \pmod 5$. By inspection or trial and error:
If $x=0$, $2(0)=0 \not\equiv 3 \pmod 5$.
If $x=1$, $2(1)=2 \not\equiv 3 \pmod 5$.
If $x=2$, $2(2)=4 \not\equiv 3 \pmod 5$.
If $x=3$, $2(3)=6 \equiv 1 \not\equiv 3 \pmod 5$.
If $x=4$, $2(4)=8 \equiv 3 \pmod 5$.
So, $x_0 = 4$ is the unique solution modulo $5$.

Step 5: Find the $d$ solutions modulo $m$.

The solutions modulo $15$ are $x_k = x_0 + k \left(\frac{m}{d}\right)$ for $k=0, 1, 2$.
For $k=0$:

For $k=1$:

For $k=2$:

Answer: The solutions are $x \equiv 4, 9, 14 \pmod{15}$.

---

5. Modular Exponentiation

Calculating $a^k \pmod m$ for large $k$ can be done efficiently using the method of binary exponentiation (also known as exponentiation by squaring).

This algorithm has a time complexity of $O(\log k)$.

Fermat's Little Theorem:

Euler's Totient Theorem:

Worked Example:

Problem: Calculate $7^{22} \pmod{11}$.

Solution:

Step 1: Identify the values and check conditions for Fermat's Little Theorem.

Since $11$ is a prime number and $7$ is not divisible by $11$, we can use Fermat's Little Theorem.

Step 2: Apply Fermat's Little Theorem.

Step 3: Rewrite the exponent using the result from Fermat's Little Theorem.

Step 4: Substitute and calculate modulo $11$.

Answer: $1$

---

6. Pigeonhole Principle (applied to number theory)

The Pigeonhole Principle (PHP) is a simple yet powerful combinatorial principle often used in number theory proofs, especially in problems involving remainders and divisibility.

In number theory, the "items" are often numbers, and the "containers" are residue classes modulo some integer $m$.

Worked Example:

Problem: Show that among any set of $6$ distinct integers, there must exist $2$ integers whose difference is divisible by $5$.

Solution:

Step 1: Define the "pigeons" and "pigeonholes".

Pigeons: The $6$ distinct integers.
Pigeonholes: The possible remainders when an integer is divided by $5$. These are $\{0, 1, 2, 3, 4\}$. There are $5$ pigeonholes.

Step 2: Apply the Pigeonhole Principle.

Since there are $6$ integers (pigeons) and $5$ possible remainders (pigeonholes), by the Pigeonhole Principle, at least two integers must have the same remainder modulo $5$.
Let these two integers be $a$ and $b$.

Step 3: Conclude based on the definition of congruence.

If $a \equiv r \pmod 5$ and $b \equiv r \pmod 5$ for some remainder $r$, then by the properties of congruence:

This means $a-b$ is divisible by $5$.

Answer: This demonstrates that among any set of $6$ distinct integers, there are always two whose difference is divisible by $5$.

---

---

7. Applications of Congruences

Congruence relations have wide-ranging applications in various fields, including:

Divisibility Tests: Many common divisibility rules (e.g., by $3$, $9$, $11$) are based on modular arithmetic.

Parity Analysis: Determining whether a number is even or odd is equivalent to working modulo $2$. Analyzing numbers modulo $4$ is useful for properties of squares.

* An even number:

* An odd number:

* An odd number:

Thus, any square is congruent to $0$ or $1 \pmod 4$. This is crucial for problems involving sums of squares (like Pythagorean triples).

Clock Arithmetic: Time calculations (hours on a clock, days of the week) naturally use modular arithmetic. A 12-hour clock works modulo $12$, and days of the week work modulo $7$.

* Modeling Clock Hands: The position of clock hands can be represented by angles or units on the clock face. Let $t$ be time in minutes from 12:00.
* Minute hand angle:

* Hour hand angle:

Problems involving identical clock hands often require finding times $t_1, t_2$ such that the set of angles $\{\theta_H(t_1), \theta_M(t_1)\}$ is the same as $\{\theta_H(t_2), \theta_M(t_2)\}$, where $t_1 \ne t_2$ and the hands are effectively swapped. This leads to solving systems of congruences.

Worked Example:

Problem: Determine if a right-angled triangle can have integer side lengths $a, b, c$ where both $a$ and $b$ are odd.

Solution:

Step 1: State the Pythagorean theorem.

Step 2: Analyze the parities of $a$ and $b$.

Given $a$ is odd,

Given $b$ is odd,

Step 3: Analyze the squares modulo $4$.

If $n$ is odd, then $n = 2k+1$ for some integer $k$.

So, for any odd integer $n$,

Step 4: Apply this to $a^2$ and $b^2$.

Since $a$ is odd,

Since $b$ is odd,

Step 5: Calculate $a^2+b^2 \pmod 4$.

Step 6: Analyze $c^2 \pmod 4$.

From the Pythagorean theorem, $c^2 = a^2+b^2$. So

However, we know that any perfect square $n^2$ must be congruent to $0 \pmod 4$ (if $n$ is even) or $1 \pmod 4$ (if $n$ is odd).
If $n$ is even:

If $n$ is odd:

Thus,

This is a contradiction.

Step 7: Conclude.

Since $c^2 \equiv 2 \pmod 4$ is impossible for any integer $c$, there are no right-angled triangles with integer side lengths where both $a$ and $b$ are odd.

Answer: \boxed{No such right-angled triangles exist.}

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $N = 7^{2023} + 3^{2023}$. What is the remainder when $N$ is divided by $10$?" options=["0","2","4","6"] answer="0" hint="Consider $N \pmod 2$ and $N \pmod 5$ separately, then use the Chinese Remainder Theorem concept, or directly calculate $N \pmod{10}$." solution="Step 1: Calculate $7^{2023} \pmod{10}$.
The powers of $7 \pmod{10}$ cycle:
$7^1 \equiv 7 \pmod{10}$
$7^2 \equiv 49 \equiv 9 \pmod{10}$
$7^3 \equiv 9 \times 7 = 63 \equiv 3 \pmod{10}$
$7^4 \equiv 3 \times 7 = 21 \equiv 1 \pmod{10}$
The cycle length is $4$.
We need $2023 \pmod 4$. $2023 = 4 \times 505 + 3$.
So, $7^{2023} \equiv 7^3 \equiv 3 \pmod{10}$.

Step 2: Calculate $3^{2023} \pmod{10}$.
The powers of $3 \pmod{10}$ cycle:
$3^1 \equiv 3 \pmod{10}$
$3^2 \equiv 9 \pmod{10}$
$3^3 \equiv 9 \times 3 = 27 \equiv 7 \pmod{10}$
$3^4 \equiv 7 \times 3 = 21 \equiv 1 \pmod{10}$
The cycle length is $4$.
Again, $2023 \pmod 4 = 3$.
So, $3^{2023} \equiv 3^3 \equiv 7 \pmod{10}$.

Step 3: Calculate $N \pmod{10}$.

Answer: \boxed{0}"
:::

:::question type="NAT" question="A digital clock displays time in 24-hour format. If the clock is currently displaying $14:35$, what time will it display exactly $100$ hours from now? (Provide the answer in HHMM format, e.g., 0530 for 05:30)." answer="1835" hint="Use modular arithmetic for hours. Minutes remain unchanged." solution="Step 1: The current time is $14$ hours and $35$ minutes. We need to find the time $100$ hours from now. The minutes part will not change.
New hour will be $(14 + 100) \pmod{24}$.

Step 2: Calculate the sum of hours.

Step 3: Calculate the result modulo $24$.

We can divide $114$ by $24$:
$114 = 4 \times 24 + 18$
So, $114 \equiv 18 \pmod{24}$.

Step 4: Combine with the minutes.
The new time will be $18:35$.

Step 5: Format the answer as HHMM.
Answer: \boxed{1835}"
:::

:::question type="MSQ" question="Which of the following statements are true for integers $a, b, c$ and modulus $m > 1$?" options=["If $a \equiv b \pmod m$, then $a+c \equiv b+c \pmod m$.","If $ac \equiv bc \pmod m$, then $a \equiv b \pmod m$.","If $a^2 \equiv b^2 \pmod m$, then $a \equiv b \pmod m$.","If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then $ac \equiv bd \pmod m$. "] answer="A,D" hint="Carefully review the properties of congruence, especially division and exponentiation." solution="Option A: If $a \equiv b \pmod m$, then $a+c \equiv b+c \pmod m$. This is a basic property of congruence (addition). It is true.

Option B: If $ac \equiv bc \pmod m$, then $a \equiv b \pmod m$. This is false. Division in modular arithmetic requires $\gcd(c,m)=1$. For example, $2 \times 3 \equiv 4 \times 3 \pmod 6$ ($6 \equiv 12 \pmod 6$), but $2 \not\equiv 4 \pmod 6$. The correct statement is $a \equiv b \pmod{m/\gcd(c,m)}$.

Option C: If $a^2 \equiv b^2 \pmod m$, then $a \equiv b \pmod m$. This is false. For example, $2^2 \equiv (-2)^2 \pmod 6$ ($4 \equiv 4 \pmod 6$), but $2 \not\equiv -2 \pmod 6$ (since $2 \not\equiv 4 \pmod 6$). Also, $2^2 \equiv 4^2 \pmod{12}$ ($4 \equiv 16 \pmod{12}$), but $2 \not\equiv 4 \pmod{12}$.

Option D: If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then $ac \equiv bd \pmod m$. This is a basic property of congruence (multiplication). It is true.
Answer: \boxed{A,D}"
:::

:::question type="SUB" question="Prove that $n^5 - n$ is divisible by $5$ for any integer $n$." answer="Proof relies on Fermat's Little Theorem or checking cases modulo 5." hint="Consider using Fermat's Little Theorem or checking all possible residues of $n$ modulo $5$." solution="We want to prove that $n^5 - n \equiv 0 \pmod 5$ for any integer $n$.

Method 1: Using Fermat's Little Theorem

Step 1: State Fermat's Little Theorem.
Fermat's Little Theorem states that if $p$ is a prime number, then for any integer $n$, $n^p \equiv n \pmod p$.
In this case, $p=5$.

Step 2: Apply the theorem.
According to Fermat's Little Theorem, for $p=5$, we have:

Step 3: Rearrange the congruence.
Subtract $n$ from both sides:

Step 4: Conclude.
Since $n^5 - n \equiv 0 \pmod 5$, it means $n^5 - n$ is divisible by $5$ for any integer $n$.

Method 2: Checking all residues modulo 5

Step 1: Consider all possible residues of $n$ modulo $5$.
The possible residues are $0, 1, 2, 3, 4$.

Step 2: Check each case.
Case 1: $n \equiv 0 \pmod 5$

Case 2: $n \equiv 1 \pmod 5$

Case 3: $n \equiv 2 \pmod 5$

Case 4: $n \equiv 3 \pmod 5$

Case 5: $n \equiv 4 \pmod 5$

Step 3: Conclude.
In all possible cases, $n^5 - n \equiv 0 \pmod 5$. Therefore, $n^5 - n$ is divisible by $5$ for any integer $n$.
Answer: \boxed{Proven}"
:::

:::question type="NAT" question="Consider an analogue clock with only an hour hand. If it currently points exactly at $3$, and moves continuously, what number will it point to $1000$ hours later? (Assume a 12-hour cycle for the clock face. Provide the answer as a plain number from 1 to 12)." answer="11" hint="Use modular arithmetic for hours, adjusting for the 1-12 range." solution="Step 1: The clock is a 12-hour clock. We are interested in the hour hand's position modulo 12.
Current position: $3$.

Step 2: Calculate the total hours passed.
Total hours = $1000$.

Step 3: Find the position modulo $12$.
The new position will be $(3 + 1000) \pmod{12}$.

Step 4: Perform the addition.

Step 5: Calculate the remainder modulo $12$.

Divide $1003$ by $12$:
$1003 = 12 \times 83 + 7$
So, $1003 \equiv 7 \pmod{12}$.

Step 6: Interpret the result for a 12-hour clock.
A remainder of $0$ usually corresponds to $12$ on a clock face. For remainders $1$ through $11$, they correspond directly to the numbers $1$ through $11$.
Since the remainder is $7$, the hour hand will point to $7$.
Answer: \boxed{11}"
:::

---

---

Part 2: Operations in Modular Arithmetic

Introduction

Modular arithmetic is a fundamental branch of number theory that deals with integers and their remainders when divided by a fixed positive integer, known as the modulus. It provides a powerful framework for analyzing properties of numbers and has widespread applications in Data Science, including cryptography (e.g., RSA algorithm relies heavily on modular exponentiation), hashing functions, error detection and correction codes, and pseudo-random number generation. For the CMI exam, understanding operations within modular arithmetic is crucial for solving problems involving number theory, discrete mathematics, and algorithmic analysis. This section will cover the core definitions, properties, and applications of modular arithmetic, including number representation in different bases and polynomial congruences.

---

---

Key Concepts

1. Basic Properties of Congruence

Modular congruence is an equivalence relation and possesses several key properties that simplify arithmetic operations.

Worked Example: Applying Basic Properties

Problem: Find the remainder when $13^{100}$ is divided by $7$.

Solution:

Step 1: Simplify the base modulo $7$.

Also, $6 \equiv -1 \pmod 7$.

Step 2: Apply the exponentiation property.

Step 3: Evaluate the power.

Step 4: State the final congruence.

Answer: The remainder is $1$.

---

2. Polynomial Congruences

An important property in modular arithmetic is how polynomials behave under congruence. This is directly tested in CMI.

Proof:

Step 1: Given the congruence $a \equiv b \pmod n$.

Step 2: Apply the exponentiation property for each term $x^k$.
Since $a \equiv b \pmod n$, we have $a^k \equiv b^k \pmod n$ for any non-negative integer $k$.

Step 3: Apply the multiplication property for each coefficient $c_k$.
Since $c_k \equiv c_k \pmod n$ and $a^k \equiv b^k \pmod n$, we can multiply these congruences:

Step 4: Apply the addition property for all terms in the polynomial.
Summing up the congruences for each term from $k=0$ to $m$:

Step 5: Conclude the result.
The left side is $p(a)$ and the right side is $p(b)$.
Therefore, $p(a) \equiv p(b) \pmod n$.

Worked Example:

Problem: Let $p(x) = 3x^3 - 2x + 5$. If $a \equiv 4 \pmod 5$, show that $p(a) \equiv p(4) \pmod 5$.

Solution:

Step 1: Use the given congruence $a \equiv 4 \pmod 5$.

Step 2: Apply the polynomial congruence property.
Since $p(x)$ is a polynomial with integer coefficients and $a \equiv 4 \pmod 5$, we directly apply the property that $p(a) \equiv p(4) \pmod 5$.

Step 3: Calculate $p(4) \pmod 5$.

Step 4: Find the remainder of $p(4)$ when divided by $5$.

So, $189 \equiv 4 \pmod 5$.

Step 5: Conclude.
Thus, $p(a) \equiv 4 \pmod 5$. This demonstrates that $p(a) \equiv p(4) \pmod 5$.

Answer: $p(a) \equiv p(4) \pmod 5$.

---

3. Number Representation in Different Bases

Numbers can be represented in various bases (radix systems), not just base 10 (decimal). A number in base $k$ is represented by a sequence of digits $(n_t n_{t-1} \dots n_1 n_0)_k$, where each digit $n_i$ satisfies $0 \le n_i < k$.

#### 3.1. Converting from Base $k$ to Base 10

To convert a number $(n_t n_{t-1} \dots n_0)_k$ to its base 10 equivalent, simply evaluate the polynomial expression:

Worked Example:

Problem: Convert $(312)_4$ to base 10.

Solution:

Step 1: Write out the positional value expression.

Step 2: Calculate each term.

Step 3: Sum the terms.

Answer: $(312)_4 = 54_{10}$.

#### 3.2. Converting from Base 10 to Base $k$

To convert a base 10 number $N_{10}$ to base $k$, use the repeated division algorithm:

Divide $N_{10}$ by $k$. The remainder is the last digit ($n_0$).

Take the quotient from step 1 and divide it by $k$. The remainder is the next digit ($n_1$).

Repeat until the quotient is $0$. The digits are read in reverse order of their calculation.

Worked Example:

Problem: Convert $75_{10}$ to base 5.

Solution:

Step 1: Divide $75$ by $5$.

Step 2: Divide the quotient $15$ by $5$.

Step 3: Divide the quotient $3$ by $5$.

Step 4: Read the remainders from bottom to top.

Answer: $75_{10} = (300)_5$.

#### 3.3. Converting Between Arbitrary Bases

To convert a number from base $k_1$ to base $k_2$:

Convert the number from base $k_1$ to base 10.

Convert the resulting base 10 number to base $k_2$.

Special Case: Bases that are Powers of Each Other
If $k_2 = k_1^m$ (e.g., base 2 to base 8, where $8 = 2^3$), you can group digits.
To convert from base $k_1$ to base $k_1^m$:

Group $m$ digits of the base $k_1$ number, starting from the right. Pad with leading zeros if necessary.

Convert each group of $m$ digits into a single digit in base $k_1^m$.

Worked Example:

Problem: Convert $(1101101)_2$ to base 8.

Solution:

Step 1: Group the binary digits into sets of three from the right (since $8 = 2^3$). Pad with leading zeros if needed.

Step 2: Convert each group of three binary digits to its decimal equivalent (which will be the base 8 digit).

Step 3: Combine the base 8 digits.

Answer: $(1101101)_2 = (155)_8$.

---

---

#
## 4. Modular Multiplicative Inverse

The concept of division in modular arithmetic is handled using the multiplicative inverse.

Finding the Inverse:

* Extended Euclidean Algorithm: For general $a$ and $n$ where $\gcd(a, n) = 1$, this algorithm can find integers $x$ and $y$ such that $ax + ny = \gcd(a, n) = 1$. Taking this equation modulo $n$, we get $ax \equiv 1 \pmod n$, so $x$ is the inverse.
* Fermat's Little Theorem: If $n$ is a prime number, then for any integer $a$ not divisible by $n$, we have $a^{n-1} \equiv 1 \pmod n$. This implies $a^{n-2}$ is the inverse of $a$ modulo $n$.

Worked Example:

Problem: Find the modular multiplicative inverse of $5$ modulo $13$.

Solution:

Step 1: Check if an inverse exists.
$\gcd(5, 13) = 1$, so an inverse exists.

Step 2: Use the Extended Euclidean Algorithm or trial and error for small numbers.
We want to find $x$ such that $5x \equiv 1 \pmod{13}$.
This means $5x = 13k + 1$ for some integer $k$.
Let's test values for $x$:
If $x=1$, $5 \times 1 = 5 \not\equiv 1 \pmod{13}$
If $x=2$, $5 \times 2 = 10 \not\equiv 1 \pmod{13}$
If $x=3$, $5 \times 3 = 15 \equiv 2 \pmod{13}$
If $x=4$, $5 \times 4 = 20 \equiv 7 \pmod{13}$
If $x=5$, $5 \times 5 = 25 \equiv 12 \pmod{13}$
If $x=6$, $5 \times 6 = 30 \equiv 4 \pmod{13}$
If $x=7$, $5 \times 7 = 35 \equiv 9 \pmod{13}$
If $x=8$, $5 \times 8 = 40 \equiv 1 \pmod{13}$

Step 3: Identify the inverse.
The inverse is $8$.

Answer: The modular multiplicative inverse of $5$ modulo $13$ is $8$.

---

#
## 5. Applications: Parity and Modulo 2 Arithmetic

Many problems, especially those involving "on/off" states, toggling, or counts of even/odd items, can be modeled using modular arithmetic modulo 2.
In modulo 2 arithmetic:
* $0$ represents "off" or "even".
* $1$ represents "on" or "odd".
* Addition is equivalent to XOR.
* $0+0 \equiv 0 \pmod 2$
* $0+1 \equiv 1 \pmod 2$
* $1+0 \equiv 1 \pmod 2$
* $1+1 \equiv 0 \pmod 2$
* Toggling a switch means changing its state $s$ to $s+1 \pmod 2$.

A common strategy is to look for invariants modulo 2. For example, if an operation always changes the state of an even number of items, then the parity of the total number of "on" items remains invariant.

Worked Example:

Problem: You have a row of 5 lights, initially (off, on, off, on, off). In one move, you can pick any two adjacent lights and toggle both of them. Is it possible to turn all 5 lights on?

Solution:

Step 1: Represent the states as numbers modulo 2.
Let $s_i \in \{0, 1\}$ be the state of light $i$ (0 for off, 1 for on).
Initial state: $(s_1, s_2, s_3, s_4, s_5) = (0, 1, 0, 1, 0)$.
Target state: $(1, 1, 1, 1, 1)$.

Step 2: Analyze the effect of the operation on the sum of states modulo 2.
Let $S = \sum_{i=1}^5 s_i \pmod 2$.
Initial sum: $0+1+0+1+0 = 2 \equiv 0 \pmod 2$.
Target sum: $1+1+1+1+1 = 5 \equiv 1 \pmod 2$.

Step 3: Consider the effect of toggling two adjacent lights.
If we pick lights $i$ and $i+1$, their states change from $(s_i, s_{i+1})$ to $(s_i+1 \pmod 2, s_{i+1}+1 \pmod 2)$.
The change in the sum of states is $(s_i+1 + s_{i+1}+1) - (s_i+s_{i+1}) = 2 \equiv 0 \pmod 2$.
This means that each move changes the sum of the states by $0 \pmod 2$. The parity of the total number of "on" lights is an invariant.

Step 4: Compare the parity of the initial and target states.
Initial state sum parity: $0 \pmod 2$ (even number of "on" lights).
Target state sum parity: $1 \pmod 2$ (odd number of "on" lights).

Since the parity of the sum of "on" lights is invariant under the allowed operation, and the initial state has an even sum while the target state has an odd sum, it is impossible to reach the target state.

Answer: No, it is not possible to turn all 5 lights on.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="NAT" question="Convert the base 7 number $(253)_7$ to base 4. Express your answer as a plain number string (e.g., 123)." answer="2020" hint="First convert to base 10, then to base 4." solution="Step 1: Convert $(253)_7$ to base 10.

Step 2: Convert $136_{10}$ to base 4 using repeated division.

Reading the remainders from bottom to top gives $(2020)_4$.

Answer: $\boxed{2020}$
"
:::

:::question type="SUB" question="Prove that for any integer $x$, $x^5 \equiv x \pmod{10}$." answer="Proof involves Fermat's Little Theorem and Chinese Remainder Theorem, or direct checking." hint="Consider modulo 2 and modulo 5 separately, then combine." solution="We need to prove $x^5 \equiv x \pmod{10}$. This is equivalent to proving:

$$x^5 \equiv x \pmod{2}$$

$$x^5 \equiv x \pmod{5}$$

Part 1: Proving $x^5 \equiv x \pmod{2}$
If $x$ is even, then $x \equiv 0 \pmod{2}$.
Then:

Since $x \equiv 0 \pmod{2}$, we have $x^5 \equiv x \pmod{2}$.
If $x$ is odd, then $x \equiv 1 \pmod{2}$.
Then:


Since $x \equiv 1 \pmod{2}$, we have $x^5 \equiv x \pmod{2}$.
In both cases, $x^5 \equiv x \pmod{2}$ holds.

Part 2: Proving $x^5 \equiv x \pmod{5}$
By Fermat's Little Theorem, for a prime $p$ and any integer $a$, $a^p \equiv a \pmod p$.
Here, $p=5$. So, $x^5 \equiv x \pmod{5}$ holds directly from Fermat's Little Theorem.

Part 3: Combining the results using the Chinese Remainder Theorem principle
We have:

Since $\gcd(2, 5) = 1$, if $A \equiv B \pmod{2}$ and $A \equiv B \pmod{5}$, then $A \equiv B \pmod{2 \times 5}$.
Therefore, $x^5 \equiv x \pmod{10}$.
"
:::

:::question type="MCQ" question="Which of the following is the modular multiplicative inverse of $7$ modulo $15$?" options=["A) 1","B) 4","C) 7","D) 13"] answer="D) 13" hint="We are looking for an integer $x$ such that $7x \equiv 1 \pmod{15}$." solution="We need to find $x$ such that $7x \equiv 1 \pmod{15}$.
Let's test the options:
A) If $x=1$,

(Incorrect)

B) If $x=4$,

(Incorrect)

C) If $x=7$,

(Incorrect)

D) If $x=13$,

(Correct)
Therefore, $13$ is the modular multiplicative inverse of $7$ modulo $15$.

Answer: $\boxed{D}$
"
:::

:::question type="MSQ" question="Let $M = (11011)_2$. Which of the following statements are true?" options=["A) $(M)_{10} = 27$","B) $M \equiv 3 \pmod 4$","C) $(M)_8 = (33)_8$","D) $M$ is a prime number."] answer="A,B,C" hint="Convert to base 10 first, then evaluate each condition." solution="Step 1: Convert $M = (11011)_2$ to base 10.

So, option A is true.

Step 2: Check $M \equiv 3 \pmod 4$ (Option B).

So $27 \equiv 3 \pmod 4$. Thus, option B is true.

Step 3: Check $(M)_8 = (33)_8$ (Option C).
To convert $(11011)_2$ to base 8, group digits in threes from the right. We can pad with a leading zero:

So, $(11011)_2 = (33)_8$. Thus, option C is true.

Step 4: Check if $M$ is a prime number (Option D).
$M = 27$. Since $27 = 3^3$, $27$ is not a prime number (it is a composite number).
Thus, option D is false.

Answer: $\boxed{A,B,C}$
"
:::

:::question type="NAT" question="A sequence of operations is defined on a set of three binary variables $(x_1, x_2, x_3)$, where each $x_i \in \{0, 1\}$. An operation consists of selecting two variables and flipping their values (i.e., $0 \to 1$ and $1 \to 0$). If the initial state is $(0, 1, 0)$ and the target state is $(1, 1, 1)$, what is the parity (0 for even, 1 for odd) of the minimum number of operations required to reach the target state?" answer="1" hint="Consider the sum of the variables modulo 2." solution="Let the state of the variables be represented by $x_i \in \{0, 1\}$.
An operation consists of picking two variables, say $x_i$ and $x_j$, and flipping them. This means $x_i \to x_i+1 \pmod{2}$ and $x_j \to x_j+1 \pmod{2}$.

Consider the sum of the variables modulo 2: $S = (x_1 + x_2 + x_3) \pmod{2}$.
Initial state: $(0, 1, 0)$. Initial sum:

Target state: $(1, 1, 1)$. Target sum:

When an operation is performed, two variables $x_i$ and $x_j$ are flipped.
The change in the sum is:

This means that each operation changes the sum of the variables by $0 \pmod{2}$.
Therefore, the sum of the variables modulo 2 is an invariant.
Since $S_{\text{initial}} = 1 \pmod{2}$ and $S_{\text{target}} = 1 \pmod{2}$, it is possible to reach the target state.

Now, we need to find the minimum number of operations.
Initial state: $(0,1,0)$. Target state: $(1,1,1)$.
Variables that need to be flipped: $x_1$ (from $0$ to $1$) and $x_3$ (from $0$ to $1$). Variable $x_2$ stays $1$.
An operation flips two variables. We need to flip $x_1$ and $x_3$.
Operation 1: Flip $x_1$ and $x_3$.

This takes exactly one operation.

The minimum number of operations is $1$.
The parity of the minimum number of operations is $1 \pmod{2} = 1$.

Answer: $\boxed{1}$
"
:::

:::question type="SUB" question="Let $n$ be a positive integer. Prove that $n^2 \equiv n \pmod 2$ for all integers $n$." answer="Proof by cases: $n$ is even or $n$ is odd." hint="Consider $n \pmod 2$." solution="We need to prove $n^2 \equiv n \pmod{2}$.

Case 1: $n$ is an even integer.
If $n$ is even, then $n \equiv 0 \pmod{2}$.
Then:

Since $n \equiv 0 \pmod{2}$, we have $n^2 \equiv n \pmod{2}$ in this case.

Case 2: $n$ is an odd integer.
If $n$ is odd, then $n \equiv 1 \pmod{2}$.
Then:

Since $n \equiv 1 \pmod{2}$, we have $n^2 \equiv n \pmod{2}$ in this case.

In both cases, $n^2 \equiv n \pmod{2}$.
Therefore, $n^2 \equiv n \pmod{2}$ for all integers $n$.
"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="What is the smallest positive integer $x$ such that $3^{2023}x \equiv 9 \pmod{11}$?" options=["A) 1","B) 2","C) 3","D) 4"] answer="D) 4" hint="First, simplify the power of 3 using Fermat's Little Theorem. Then, find the modular inverse of the simplified coefficient." solution="We need to solve $3^{2023}x \equiv 9 \pmod{11}$.
First, simplify $3^{2023} \pmod{11}$. Since $11$ is a prime number and $11 \nmid 3$, we can use Fermat's Little Theorem, which states $a^{p-1} \equiv 1 \pmod p$. Here, $a=3$ and $p=11$, so $3^{11-1} \equiv 3^{10} \equiv 1 \pmod{11}$.

Now, we simplify the exponent $2023$:

So,

Using Fermat's Little Theorem:


The congruence becomes:

To find $x$, we need to multiply by the modular inverse of $5 \pmod{11}$.
Let $5^{-1} \pmod{11}$ be $y$. We need $5y \equiv 1 \pmod{11}$.
By inspection, $5 \times 9 = 45 \equiv 1 \pmod{11}$. So $5^{-1} \equiv 9 \pmod{11}$.
Multiply both sides of $5x \equiv 9 \pmod{11}$ by $9$:



Since $81 = 7 \times 11 + 4$, we have $81 \equiv 4 \pmod{11}$.
Thus,

The smallest positive integer $x$ is $4$.

Answer: $\boxed{D}$
"
:::

:::question type="NAT" question="Find the smallest positive integer $x$ such that $17x \equiv 1 \pmod{101}$." answer="6" hint="Use the Extended Euclidean Algorithm to find integers $a$ and $b$ such that $17a + 101b = 1$. The value of $a$ (modulo 101) will be your answer." solution="We need to find the smallest positive integer $x$ such that $17x \equiv 1 \pmod{101}$. This is equivalent to finding the modular inverse of $17$ modulo $101$.
We use the Extended Euclidean Algorithm to find integers $a$ and $b$ such that $17a + 101b = 1$.

The steps of the Euclidean Algorithm are:

Now, we work backwards from the second equation to express $1$ as a linear combination of $17$ and $101$:

So, we have $6 \times 17 + (-1) \times 101 = 1$.
Taking this equation modulo $101$:



Thus, $x \equiv 6 \pmod{101}$.
The smallest positive integer $x$ is $6$.

Answer: $\boxed{6}$
"
:::

:::question type="NAT" question="Find the remainder when $7^{2022}$ is divided by $100$." answer="49" hint="Since $\gcd(7,100)=1$, use Euler's Totient Theorem. First, calculate $\phi(100)$. Then simplify the exponent." solution="We need to find $7^{2022} \pmod{100}$.
Since $\gcd(7,100)=1$, we can use Euler's Totient Theorem, which states that $a^{\phi(n)} \equiv 1 \pmod n$ for $\gcd(a,n)=1$.
First, calculate $\phi(100)$:

So, $\phi(100) = 40$.
By Euler's Theorem, $7^{40} \equiv 1 \pmod{100}$.

Now, we simplify the exponent $2022$ modulo $40$:

So,

Using Euler's Theorem:

Now we need to calculate $7^{22} \pmod{100}$:

Since $7^4 \equiv 1 \pmod{100}$, we can simplify $7^{22}$ further:


Therefore, the remainder when $7^{2022}$ is divided by $100$ is $49$.

Answer: $\boxed{49}$
"
:::

:::question type="MCQ" question="Consider the congruence $12x \equiv 18 \pmod{42}$. Which of the following statements is true?" options=["A) It has no solutions.","B) It has exactly one solution modulo 42.","C) It has exactly 6 solutions modulo 42.","D) It has exactly 12 solutions modulo 42."] answer="C) It has exactly 6 solutions modulo 42." hint="First, calculate $\gcd(12, 42)$. Then check if this $\gcd$ divides $18$. The number of solutions depends on this $\gcd$." solution="We are given the congruence $12x \equiv 18 \pmod{42}$.

According to the theory of linear congruences, $ax \equiv b \pmod n$ has solutions if and only if $\gcd(a,n)$ divides $b$. If solutions exist, there are exactly $\gcd(a,n)$ distinct solutions modulo $n$.

Calculate $\gcd(12, 42)$:

Using the Euclidean Algorithm:


So, $\gcd(12, 42) = 6$.

Check if $\gcd(12, 42)$ divides $18$:

$6$ divides $18$ (since $18 = 3 \times 6$).
Since the condition is met, solutions exist.

Determine the number of solutions:

The number of distinct solutions modulo $42$ is equal to $\gcd(12, 42)$, which is $6$.

Therefore, the congruence $12x \equiv 18 \pmod{42}$ has exactly $6$ solutions modulo $42$.

To find these solutions (optional, for verification):
Divide the entire congruence by $\gcd(12,42)=6$:

Now we need to find the inverse of $2 \pmod{7}$.

So $2^{-1} \equiv 4 \pmod{7}$.
Multiply both sides by $4$:



This gives us one solution $x_0 = 5$. The other solutions are found by adding multiples of $n/d = 42/6 = 7$ to $x_0$:

The solutions modulo $42$ are:






There are indeed 6 distinct solutions modulo 42.

Answer: $\boxed{C}$
"
:::

---

What's Next?