Divisibility and Primes

Overview

This chapter lays the essential groundwork for understanding number theory, focusing on the core concepts of divisibility and prime numbers. These foundational ideas are not merely abstract mathematical constructs; they are critical building blocks for a wide array of computational and algorithmic problems encountered in data science. Mastering them provides a robust framework for approaching more complex topics.

For the CMI entrance examination, a solid grasp of divisibility and primes is indispensable. These concepts frequently underpin questions related to modular arithmetic, algorithmic efficiency, and even basic cryptographic principles. Expect to encounter problems that test your ability to apply divisibility rules, identify prime factors, and understand the unique properties of prime numbers in various contexts, often requiring logical deduction and computational thinking.

Furthermore, the methods for calculating the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental. Proficiency in algorithms like the Euclidean Algorithm is not just about finding answers, but about understanding efficient computational procedures—a skill directly transferable and highly valued in data science for optimizing code and understanding data structures. This chapter ensures you possess these vital analytical tools for success.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Prime Numbers and Divisibility | Understand fundamental properties and tests for primes. |
| 2 | GCD and LCM | Compute greatest common divisor and least common multiple. |

---

Learning Objectives

---

Now let's begin with Prime Numbers and Divisibility...
## Part 1: Prime Numbers and Divisibility

Introduction

Prime numbers and the concept of divisibility form the bedrock of number theory, a fundamental branch of mathematics with widespread applications in data science, especially in cryptography, algorithm design, and computational number theory. For the CMI examination, a solid understanding of these concepts is crucial for tackling problems involving integer properties, modular arithmetic, and combinatorial counting. This unit will equip you with the essential definitions, rules, and problem-solving techniques required to excel in questions related to prime numbers, composite numbers, factors, multiples, and their applications in various numerical scenarios. Mastering these foundational ideas will also lay the groundwork for more advanced topics in number theory.

---

---

Key Concepts

1. Divisibility Rules

Divisibility rules are shortcuts to determine if an integer is divisible by another integer without performing the full division. These are particularly useful for large numbers in competitive exams.

Combining Divisibility Rules

To check divisibility by a composite number $N$, factor $N$ into two coprime (relatively prime) integers $a$ and $b$ (i.e., $\gcd(a,b)=1$). If a number is divisible by both $a$ and $b$, then it is divisible by $N$.

Example:
* Divisibility by 36: Check divisibility by $4$ and $9$ (since $\gcd(4,9)=1$).
* Divisibility by 72: Check divisibility by $8$ and $9$ (since $\gcd(8,9)=1$).
* Divisibility by 80: Check divisibility by $8$ and $10$ (since $\gcd(8,10)=2 \neq 1$, this is not the best pair. Better to use $8$ and $5$ and $2$. Or, $8$ and $10$ works if you check for $10$ first (last digit 0) and then the number formed by the last three digits for $8$). More precisely, for divisibility by $80$, it must be divisible by $10$ (last digit $0$) AND the number formed by the remaining digits (after removing the last zero) must be divisible by $8$.
* Divisibility by 120: Check divisibility by $8$, $3$, and $5$ (since $\gcd(8,3)=1$, $\gcd(8,5)=1$, $\gcd(3,5)=1$).

Worked Example:

Problem: Determine if the number $N = 728160$ is divisible by $36$, $72$, and $120$.

Solution:

Step 1: Check divisibility by $2, 3, 4, 5, 8, 9, 10$.

* Divisibility by 2: Last digit is $0$ (even). So, $N$ is divisible by $2$.
* Divisibility by 3: Sum of digits $= 7+2+8+1+6+0 = 24$. Since $24$ is divisible by $3$, $N$ is divisible by $3$.
* Divisibility by 4: Last two digits form $60$. Since $60$ is divisible by $4$ ($60 = 4 \times 15$), $N$ is divisible by $4$.
* Divisibility by 5: Last digit is $0$. So, $N$ is divisible by $5$.
* Divisibility by 8: Last three digits form $160$. Since $160$ is divisible by $8$ ($160 = 8 \times 20$), $N$ is divisible by $8$.
* Divisibility by 9: Sum of digits $= 24$. Since $24$ is not divisible by $9$, $N$ is not divisible by $9$.
* Divisibility by 10: Last digit is $0$. So, $N$ is divisible by $10$.

Step 2: Apply combined divisibility rules.

* Divisibility by 36 (check by 4 and 9):
* $N$ is divisible by $4$ (from Step 1).
* $N$ is NOT divisible by $9$ (from Step 1).
* Therefore, $N$ is NOT divisible by $36$.

* Divisibility by 72 (check by 8 and 9):
* $N$ is divisible by $8$ (from Step 1).
* $N$ is NOT divisible by $9$ (from Step 1).
* Therefore, $N$ is NOT divisible by $72$.

* Divisibility by 120 (check by 3, 5, and 8):
* $N$ is divisible by $3$ (from Step 1).
* $N$ is divisible by $5$ (from Step 1).
* $N$ is divisible by $8$ (from Step 1).
* Therefore, $N$ IS divisible by $120$.

Answer: $N = 728160$ is divisible by $120$, but not by $36$ or $72$.

---

2. Prime Factorization

Prime factorization is the process of breaking down a composite number into its prime factors. This is a unique representation for every composite number, as stated by the Fundamental Theorem of Arithmetic.

Method for Prime Factorization:

Start by dividing the number by the smallest prime number ($2$) that divides it.

Continue dividing the quotient by $2$ until it is no longer divisible by $2$.

Move to the next prime number ($3$) and repeat the process.

Continue with subsequent prime numbers ($5, 7, 11, \ldots$) until the quotient becomes $1$.

The prime factors are all the prime numbers used in the division process.

Worked Example:

Problem: Find the prime factorization of $2520$.

Solution:

Step 1: Divide by $2$ repeatedly.

Step 2: Divide by $3$ repeatedly.

Step 3: Divide by $5$.

Step 4: Divide by $7$.

Step 5: Collect the prime factors.

The prime factors are $2, 2, 2, 3, 3, 5, 7$.

Step 6: Write in exponential form.

Answer: The prime factorization of $2520$ is $2^3 \times 3^2 \times 5^1 \times 7^1$.

---

3. Number of Divisors

Once the prime factorization of a number is known, it's straightforward to calculate the total number of its positive divisors.

Worked Example:

Problem: How many positive integers are factors of $1890$?

Solution:

Step 1: Find the prime factorization of $1890$.

So, the prime factorization is $1890 = 2^1 \times 3^3 \times 5^1 \times 7^1$.

Step 2: Identify the exponents of the prime factors.

The exponents are $a_1 = 1$ (for prime $2$), $a_2 = 3$ (for prime $3$), $a_3 = 1$ (for prime $5$), $a_4 = 1$ (for prime $7$).

Step 3: Apply the formula for the number of divisors.

Answer: There are $32$ positive integer factors of $1890$.

---

---

4. Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

GCD and LCM are fundamental concepts for understanding relationships between integers and are often used in problems involving fractions and simultaneous events.

Finding GCD and LCM using Prime Factorization:

Let $A = p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k}$ and $B = p_1^{b_1} p_2^{b_2} \ldots p_k^{b_k}$, where $p_i$ are common prime factors and exponents $a_i, b_i \ge 0$.

Application in Fractional Sums (similar to PYQ4):
When dealing with sums of fractions like $\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \ldots$, finding the LCM of the denominators is crucial to combine them into a single fraction. If the sum is an integer, this implies specific divisibility conditions on the unknown terms.

Worked Example:

Problem: Let $S = \frac{1}{2} + \frac{1}{4} + \frac{1}{n}$ be an integer, where $n$ is a positive integer. Find all possible values of $n$.

Solution:

Step 1: Combine the known fractions.

The LCM of $2$ and $4$ is $4$.

Step 2: Isolate $\frac{1}{n}$ and set the expression equal to an integer $K$.

Step 3: Solve for $n$.

Step 4: Determine possible values for $4K - 3$.
Since $n$ is a positive integer, $4K - 3$ must be a positive divisor of $4$.
The positive divisors of $4$ are $1, 2, 4$.
Also, $K$ must be an integer. $4K = (4K-3) + 3$. So $(4K-3)+3$ must be a multiple of $4$.

Let $D = 4K - 3$. We need $D$ to be a divisor of $4$ AND $D+3$ to be a multiple of $4$.

* Case 1: $D=1$
If $D=1$, then $4K-3 = 1 \implies 4K = 4 \implies K=1$. This is an integer value for $K$.
Then $n = \frac{4}{D} = \frac{4}{1} = 4$.
Let's check: $\frac{1}{2} + \frac{1}{4} + \frac{1}{4} = \frac{2}{4} + \frac{1}{4} + \frac{1}{4} = \frac{4}{4} = 1$, which is an integer. So $n=4$ is a solution.

* Case 2: $D=2$
If $D=2$, then $4K-3 = 2 \implies 4K = 5$. $K = \frac{5}{4}$, which is not an integer. So this case does not yield a solution.

* Case 3: $D=4$
If $D=4$, then $4K-3 = 4 \implies 4K = 7$. $K = \frac{7}{4}$, which is not an integer. So this case does not yield a solution.

Therefore, the only positive integer value for $n$ is $4$.

Answer: $\boxed{4}$

---

5. Number Representation and Algebraic Problems

Numbers can be represented using place value notation. For a number with digits $d_k d_{k-1} \ldots d_1 d_0$, its value is $d_k \times 10^k + d_{k-1} \times 10^{k-1} + \ldots + d_1 \times 10^1 + d_0 \times 10^0$. Problems often involve manipulating these representations.

Worked Example:

Problem: A $2$-digit number $ab$ is such that the number $ba$, obtained by reversing its digits, is $4$ times the original number $ab$ plus $3$. Find the number $ab$. ($a \neq 0$).

Solution:

Step 1: Express the numbers algebraically.

Original number $ab$:

Reversed number $ba$:

Step 2: Set up the equation based on the problem statement.

Given that $N_2 = 4N_1 + 3$:

Step 3: Expand and simplify the equation.

Rearrange terms:

Divide by $3$ to simplify:

Step 4: Use the properties of digits ($a, b$ are integers from $0$ to $9$, with $a \neq 0$).

Since $b$ is a digit ($0 \le b \le 9$), $2b$ can range from $0$ to $18$.
So, $13a + 1$ must be in the range $[0, 18]$.

Consider $a=1$:

This is a valid digit ($0 \le 7 \le 9$).
So, $a=1, b=7$ is a possible solution. The number is $17$.

Let's check for other values of $a$:
If $a=2$:

This is not a digit ($>9$). Any larger value of $a$ will also result in $b>9$.

Step 5: Verify the solution.

Original number $ab = 17$.
Reversed number $ba = 71$.
Check the condition: $71 = 4 \times 17 + 3$.
$71 = 68 + 3$.
$71 = 71$. This is true.

Answer: $\boxed{17}$

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following numbers is divisible by $72$?" options=["$1234567890$","$4567890120$","$2897645040$","$9999999999$"] answer="$2897645040$" hint="A number is divisible by $72$ if it is divisible by both $8$ and $9$." solution="For a number to be divisible by $72$, it must be divisible by both $8$ and $9$ (since $\gcd(8,9)=1$).

Check Divisibility by 8: The number formed by the last three digits must be divisible by $8$.

Check Divisibility by 9: The sum of the digits must be divisible by $9$.

Let's evaluate each option:

* A) $1234567890$:
* Last three digits: $890$. $890 \div 8 = 111.25$. Not divisible by $8$. (Fail)

* B) $4567890120$:
* Last three digits: $120$. $120 \div 8 = 15$. Divisible by $8$. (Pass)
* Sum of digits: $4+5+6+7+8+9+0+1+2+0 = 42$. $42$ is not divisible by $9$. (Fail)

* C) $2897645040$:
* Last three digits: $040$. $040 \div 8 = 5$. Divisible by $8$. (Pass)
* Sum of digits: $2+8+9+7+6+4+5+0+4+0 = 45$. $45$ is divisible by $9$. (Pass)
* Since it is divisible by both $8$ and $9$, it is divisible by $72$.

* D) $9999999999$:
* Last three digits: $999$. $999 \div 8 = 124.875$. Not divisible by $8$. (Fail)

Therefore, only $2897645040$ is divisible by $72$.
Answer: \boxed{2897645040}
"
:::

:::question type="NAT" question="Calculate the total number of positive divisors of $1470$." answer="24" hint="First, find the prime factorization of $1470$. Then use the formula for the number of divisors." solution="Step 1: Find the prime factorization of $1470$.

The prime factors are $2^1, 3^1, 5^1, 7^2$.

Step 2: Apply the formula for the number of divisors $\tau(n) = (a_1+1)(a_2+1)\ldots(a_k+1)$.
The exponents are $a_1=1, a_2=1, a_3=1, a_4=2$.

Answer: \boxed{24}
"
:::

:::question type="MSQ" question="Let $S = \frac{1}{2} + \frac{1}{5} + \frac{1}{10} + \frac{1}{P}$ be an integer, where $P$ is a positive integer. Which of the following statements about $P$ is/are true?" options=["$P$ must be a multiple of $5$.","`$P$` is a multiple of $4$.","`$P$` is a divisor of $10$.","`$P$` has exactly $3$ positive divisors."] answer="A,C" hint="Combine the fractions and find possible values for $P$. Then check the properties for each possible $P$." solution="Step 1: Combine the known fractions.
Let the given sum be $K$, where $K$ is an integer.

The LCM of $2, 5, 10$ is $10$.

Step 2: Isolate $\frac{1}{P}$ and solve for $P$.

Step 3: Determine possible values for $5K - 4$.
Since $P$ is a positive integer, $5K - 4$ must be a positive divisor of $5$.
The positive divisors of $5$ are $1$ and $5$.
Also, $K$ must be an integer. $5K = (5K-4) + 4$. So $(5K-4)+4$ must be a multiple of $5$.

* Case 1: $5K - 4 = 1$
$5K = 1+4 \implies 5K = 5 \implies K=1$. This is an integer.
Then $P = \frac{5}{1} = 5$.

* Case 2: $5K - 4 = 5$
$5K = 5+4 \implies 5K = 9 \implies K = \frac{9}{5}$, which is not an integer. So this case does not yield a solution.

Thus, the only possible positive integer value for $P$ is $5$.

Step 4: Check the given statements for $P=5$.
* A) $P$ must be a multiple of $5$.
$P=5$ is a multiple of $5$. (True)
* B) $P$ is a multiple of $4$.
$P=5$ is not a multiple of $4$. (False)
* C) $P$ is a divisor of $10$.
$P=5$ divides $10$ ($10 = 5 \times 2$). (True)
* D) $P$ has exactly $3$ positive divisors.
The divisors of $P=5$ are $1$ and $5$. It has exactly $2$ positive divisors. So, this statement is false.

Therefore, statements A and C are true.
Answer: \boxed{A,C}
"
:::

:::question type="SUB" question="Find the smallest positive integer $N$ such that $N$ has exactly $12$ positive divisors and $N$ is divisible by $60$." answer="60" hint="First, find the prime factorization of $60$. Then, determine the possible exponent combinations for $12$ divisors. Combine these to find the smallest $N$." solution="Step 1: Find the prime factorization of $60$.

Step 2: Determine the possible exponent combinations for a number with $12$ divisors.
If $N = p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k}$, then the number of divisors is $(a_1+1)(a_2+1)\ldots(a_k+1) = 12$.
Possible ways to factor $12$:
* $12$: Exponent is $11$. ($p^{11}$)
* $6 \times 2$: Exponents are $5, 1$. ($p_1^5 p_2^1$)
* $4 \times 3$: Exponents are $3, 2$. ($p_1^3 p_2^2$)
* $3 \times 2 \times 2$: Exponents are $2, 1, 1$. ($p_1^2 p_2^1 p_3^1$)

Step 3: Construct $N$ such that it is divisible by $60 = 2^2 \times 3^1 \times 5^1$.
This means $N$ must have at least $2^2, 3^1, 5^1$ in its prime factorization.
We need $N = 2^a \times 3^b \times 5^c$ where $a \ge 2, b \ge 1, c \ge 1$.
The number of divisors is $(a+1)(b+1)(c+1) = 12$.

Let's list partitions of $12$ into 3 factors $\ge 1$:
* $12 = 12 \times 1 \times 1 \implies (a,b,c) = (11,0,0)$. This fails $b \ge 1$ and $c \ge 1$.
* $12 = 6 \times 2 \times 1 \implies (a,b,c) = (5,1,0)$ (and its permutations).
* $(a,b,c) = (5,1,0) \implies N = 2^5 \times 3^1 = 96$. Fails $c \ge 1$.
* $(a,b,c) = (5,0,1) \implies N = 2^5 \times 5^1 = 160$. Fails $b \ge 1$.
* $(a,b,c) = (1,5,0) \implies N = 2^1 \times 3^5 = 486$. Fails $a \ge 2$ and $c \ge 1$.
* $(a,b,c) = (0,5,1) \implies N = 3^5 \times 5^1 = 1215$. Fails $a \ge 2$.
* $(a,b,c) = (1,0,5) \implies N = 2^1 \times 5^5$. Fails $a \ge 2$ and $b \ge 1$.
* $(a,b,c) = (0,1,5) \implies N = 3^1 \times 5^5$. Fails $a \ge 2$.
* $12 = 4 \times 3 \times 1 \implies (a,b,c) = (3,2,0)$ (and its permutations).
* $(a,b,c) = (3,2,0) \implies N = 2^3 \times 3^2 = 72$. Fails $c \ge 1$.
* $(a,b,c) = (3,0,2) \implies N = 2^3 \times 5^2 = 200$. Fails $b \ge 1$.
* $(a,b,c) = (2,3,0) \implies N = 2^2 \times 3^3 = 108$. Fails $c \ge 1$.
* $(a,b,c) = (2,0,3) \implies N = 2^2 \times 5^3 = 500$. Fails $b \ge 1$.
* $(a,b,c) = (0,3,2) \implies N = 3^3 \times 5^2 = 675$. Fails $a \ge 2$.
* $(a,b,c) = (0,2,3) \implies N = 3^2 \times 5^3 = 1125$. Fails $a \ge 2$.
* $12 = 3 \times 2 \times 2 \implies (a,b,c) = (2,1,1)$ (and its permutations).
* $(a,b,c) = (2,1,1) \implies N = 2^2 \times 3^1 \times 5^1 = 60$. This satisfies $a \ge 2, b \ge 1, c \ge 1$. This is a candidate.
* $(a,b,c) = (1,2,1) \implies N = 2^1 \times 3^2 \times 5^1 = 90$. Fails $a \ge 2$.
* $(a,b,c) = (1,1,2) \implies N = 2^1 \times 3^1 \times 5^2 = 150$. Fails $a \ge 2$.

The only configuration that satisfies all conditions using only primes $2,3,5$ is $N=60$.

Step 4: Check for numbers with more than 3 prime factors.
If $N$ had 4 distinct prime factors, say $N = 2^a \times 3^b \times 5^c \times 7^d$.
For $N$ to be divisible by $60$, we need $a \ge 2, b \ge 1, c \ge 1$.
To have $12$ divisors, $(a+1)(b+1)(c+1)(d+1) = 12$.
Since $a \ge 2 \implies a+1 \ge 3$.
Since $b \ge 1 \implies b+1 \ge 2$.
Since $c \ge 1 \implies c+1 \ge 2$.
Since $d \ge 1 \implies d+1 \ge 2$.
The smallest possible product of these four factors is $3 \times 2 \times 2 \times 2 = 24$. This is greater than $12$.
Therefore, $N$ cannot have 4 or more distinct prime factors.

Thus, $N$ must have exactly 3 prime factors: $2, 3, 5$.
The smallest such $N$ is $60$.
Answer: \boxed{60}
"
:::

---

Summary

---

What's Next?

---

---

Part 2: GCD and LCM

Introduction

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental concepts in number theory, playing a crucial role in various computational and mathematical applications. For a Masters in Data Science, understanding GCD and LCM is essential not only for theoretical foundations in areas like cryptography and modular arithmetic but also for practical algorithm design, such as optimizing resource allocation, scheduling tasks, and managing data structures. In CMI examinations, questions involving GCD and LCM frequently assess a candidate's ability to apply number theoretic properties, solve systems of equations, and construct logical proofs. This section will thoroughly cover the definitions, properties, and computational methods for GCD and LCM, preparing you for complex problem-solving scenarios.

---

---

Key Concepts

1. Finding GCD: Euclidean Algorithm

The Euclidean Algorithm is an efficient method for computing the GCD of two integers. It is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. This process is repeated until one of the numbers becomes zero, and the other number is the GCD. More formally, it uses the division algorithm: $\gcd(a, b) = \gcd(b, a \pmod b)$ for $b \neq 0$.

Algorithm Steps:

Divide $a$ by $b$ and find the remainder $r$.

If $r = 0$, then $b$ is the GCD.

If $r \neq 0$, replace $a$ with $b$ and $b$ with $r$, and repeat the process.

Worked Example:

Problem: Find the greatest common divisor of $1071$ and $462$.

Solution:

Step 1: Divide $1071$ by $462$.

Step 2: Replace $a$ with $462$ and $b$ with $147$. Divide $462$ by $147$.

Step 3: Replace $a$ with $147$ and $b$ with $21$. Divide $147$ by $21$.

Step 4: The remainder is $0$. The last non-zero remainder is $21$.

Answer: $\gcd(1071, 462) = 21$

---

2. Finding GCD and LCM using Prime Factorization

Another method for finding GCD and LCM involves expressing the numbers as products of their prime factors.

Steps for GCD:

Find the prime factorization of each number.

Identify all common prime factors.

For each common prime factor, take the lowest power that appears in any of the factorizations.

Multiply these lowest powers together to get the GCD.

Steps for LCM:

Find the prime factorization of each number.

Identify all prime factors that appear in any of the factorizations (common or unique).

For each prime factor, take the highest power that appears in any of the factorizations.

Multiply these highest powers together to get the LCM.

Worked Example:

Problem: Find $\gcd(72, 120)$ and $\lcm(72, 120)$ using prime factorization.

Solution:

Step 1: Prime factorize $72$ and $120$.

Step 2: Identify common prime factors for GCD (2 and 3). Take the lowest powers.

Step 3: Identify all prime factors for LCM (2, 3, and 5). Take the highest powers.

Answer: $\gcd(72, 120) = 24$, $\lcm(72, 120) = 360$

---

3. Relationship between GCD and LCM

For any two positive integers $a$ and $b$, there is a fundamental relationship between their product, their GCD, and their LCM.

Proof Sketch:
Let $a = p_1^{e_1} \cdots p_k^{e_k}$ and $b = p_1^{f_1} \cdots p_k^{f_k}$ be the prime factorizations of $a$ and $b$, where $p_i$ are distinct prime numbers and $e_i, f_i \ge 0$.

Step 1: Express GCD using prime factorization.

Step 2: Express LCM using prime factorization.

Step 3: Multiply $a \cdot b$.

Step 4: Multiply $\gcd(a, b) \cdot \lcm(a, b)$.
Recall that for any two non-negative integers $x, y$, we have $\min(x, y) + \max(x, y) = x+y$.

Step 5: Compare the results from Step 3 and Step 4.

This fundamental relationship is extremely useful in solving problems where sums, products, GCD, and LCM are involved.

---

---

4. Properties of GCD and LCM

Understanding these properties is crucial for solving CMI problems efficiently, especially those requiring proofs or deductions.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following numbers is the greatest common divisor of $132$ and $252$?" options=["12","6","18","24"] answer="12" hint="Use the Euclidean Algorithm to find the GCD efficiently." solution="Step 1: Apply the Euclidean Algorithm.

Step 2: Continue with $132$ and $120$.

Step 3: Continue with $120$ and $12$.

The last non-zero remainder is $12$.
Thus, $\gcd(132, 252) = 12$.
Answer: \boxed{12}"
:::

:::question type="NAT" question="The product of two positive integers is $720$, and their greatest common divisor is $6$. What is their least common multiple?" answer="120" hint="Recall the fundamental relationship between the product, GCD, and LCM of two numbers." solution="Let the two positive integers be $a$ and $b$.
Given:

We use the formula:

Substitute the given values:

Divide by $6$ to find $\lcm(a, b)$:


The least common multiple is $120$.
Answer: \boxed{120}"
:::

:::question type="SUB" question="Two positive integers $A$ and $B$ satisfy $A+B=96$ and their least common multiple is $180$. Find the values of $A$ and $B$." answer="A=36, B=60 or A=60, B=36" hint="Let $d = \gcd(A, B)$, then $A=dx$ and $B=dy$ with $\gcd(x,y)=1$. Use the relationship $AB = d \cdot \lcm(A,B)$." solution="Let $d = \gcd(A, B)$.
Then we can write $A = dx$ and $B = dy$ for some positive integers $x, y$ such that $\gcd(x, y) = 1$.

Given: $A+B = 96$
Substitute $A=dx, B=dy$:

Given: $\lcm(A, B) = 180$
We know the relationship $A \cdot B = \gcd(A, B) \cdot \lcm(A, B)$.
Substitute $A=dx, B=dy, \gcd(A,B)=d$:

Since $d$ is a GCD of positive integers, $d \neq 0$. We can divide by $d$:

From (1), $d$ must be a divisor of $96$. From (2), $d$ must be a divisor of $180$.
Thus, $d$ must be a common divisor of $96$ and $180$. The greatest common divisor of $96$ and $180$ is:

So, $d$ can be any divisor of $12$ (i.e., $1, 2, 3, 4, 6, 12$).

Let's test possible values for $d$:
If $d=12$:
From (1): $12(x+y) = 96 \implies x+y = 8$.
From (2): $12xy = 180 \implies xy = 15$.

We need to find two coprime integers $x, y$ such that $x+y=8$ and $xy=15$.
Consider pairs of factors of $15$: $(1, 15), (3, 5)$.

• For $(1, 15)$: $1+15 = 16 \neq 8$.


• For $(3, 5)$: $3+5 = 8$. Also, $\gcd(3, 5) = 1$. This is a valid pair.

So, $x=3, y=5$ (or $x=5, y=3$).

Now find $A$ and $B$:
If $x=3, y=5$:

If $x=5, y=3$:

Let's verify other possible values of $d$:
If $d=6$: $x+y=16$, $xy=30$. Pairs of factors of 30: $(1,30), (2,15), (3,10), (5,6)$. None sum to 16.
If $d=4$: $x+y=24$, $xy=45$. Pairs of factors of 45: $(1,45), (3,15), (5,9)$. None sum to 24.
If $d=3$: $x+y=32$, $xy=60$. Pairs of factors of 60: $(1,60), (2,30), (3,20), (4,15), (5,12), (6,10)$. None sum to 32.
If $d=2$: $x+y=48$, $xy=90$. Pairs of factors of 90: $(1,90), (2,45), (3,30), (5,18), (6,15), (9,10)$. None sum to 48.
If $d=1$: $x+y=96$, $xy=180$. Pairs of factors of 180... (too many to list and check, but it's clear $d=12$ is the correct choice as it's the GCD).

The values are $A=36$ and $B=60$ (or vice versa).
Answer: \boxed{A=36, B=60 \text{ or } A=60, B=36}"
:::

:::question type="MSQ" question="Which of the following statements are always true for positive integers $a, b, c$?" options=["$\gcd(a, b) \le a$","$\lcm(a, b) \ge a$","If $\gcd(a, b) = 1$, then $\lcm(a, b) = a \cdot b$","$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$"] answer="A,B,C,D" hint="Carefully consider the definitions and properties of GCD and LCM." solution="Let's analyze each option:
A. $\gcd(a, b) \le a$: The greatest common divisor of $a$ and $b$ must be a divisor of $a$. The largest divisor of $a$ is $a$ itself. Therefore, $\gcd(a, b)$ cannot be greater than $a$. This statement is always true.
B. $\lcm(a, b) \ge a$: The least common multiple of $a$ and $b$ must be a multiple of $a$. The smallest positive multiple of $a$ is $a$ itself. Therefore, $\lcm(a, b)$ cannot be less than $a$. This statement is always true.
C. If $\gcd(a, b) = 1$, then $\lcm(a, b) = a \cdot b$: We know that $a \cdot b = \gcd(a, b) \cdot \lcm(a, b)$. If $\gcd(a, b) = 1$, then substituting into the formula gives $a \cdot b = 1 \cdot \lcm(a, b)$, which simplifies to $\lcm(a, b) = a \cdot b$. This statement is always true.
D. $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$: The GCD operation is associative. This property allows us to find the GCD of multiple numbers by finding the GCD of pairs iteratively. For example, $\gcd(6, 10, 15) = \gcd(\gcd(6, 10), 15) = \gcd(2, 15) = 1$. This statement is always true.

All options are correct.
Answer: \boxed{A,B,C,D}"
:::

:::question type="SUB" question="Prove that for any positive integer $n$, the fraction $\frac{n}{n+1}$ is always in its simplest form." answer="Proof shows $\gcd(n, n+1)=1$" hint="A fraction is in its simplest form if the numerator and denominator are coprime. You need to show that $\gcd(n, n+1) = 1$." solution="To prove that the fraction $\frac{n}{n+1}$ is always in its simplest form, we need to show that the greatest common divisor of the numerator $n$ and the denominator $n+1$ is $1$. That is, we need to prove $\gcd(n, n+1) = 1$.

Step 1: Let $d$ be the greatest common divisor of $n$ and $n+1$.

Step 2: By the definition of GCD, $d$ must divide both $n$ and $n+1$.

Step 3: If $d$ divides two integers, it must also divide their difference.

Step 4: Calculate the difference.

Step 5: Therefore, $d$ must divide $1$.

Step 6: The only positive integer that divides $1$ is $1$ itself.

Since $\gcd(n, n+1) = 1$, the integers $n$ and $n+1$ are coprime.
Therefore, the fraction $\frac{n}{n+1}$ is always in its simplest form (irreducible).
Answer: \boxed{\text{Proof shows } \gcd(n, n+1)=1}"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Let $a = 2^3 \cdot 3^2 \cdot 5^1$ and $b = 2^x \cdot 3^y \cdot 5^z$. If $\gcd(a,b) = 2^2 \cdot 3^1 \cdot 5^0$ and $\lcm(a,b) = 2^3 \cdot 3^2 \cdot 5^2$, what is the value of $x+y+z$?" options=["3","4","5","6"] answer="5" hint="Recall the relationship between the exponents in the prime factorization of $a, b, \gcd(a,b)$, and $\lcm(a,b)$ for each prime." solution="Let $v_p(n)$ denote the exponent of prime $p$ in the prime factorization of $n$.
For any prime $p$, we know that $v_p(\gcd(a,b)) = \min(v_p(a), v_p(b))$ and $v_p(\lcm(a,b)) = \max(v_p(a), v_p(b))$.

Given:

Let's find $x, y, z$ for each prime factor:

For prime $2$:

For prime $3$:

For prime $5$:

So, we have $x=2, y=1, z=2$.
The sum is:

Answer: \boxed{5}"
:::

:::question type="NAT" question="Find the largest integer $k$ such that $n^3 - n$ is divisible by $k$ for all integers $n \ge 2$." answer="6" hint="Factorize the expression $n^3-n$. Consider small values of $n$ to find potential divisors." solution="The expression is $n^3 - n$.
We can factorize this as:

This is a product of three consecutive integers: $(n-1), n, (n+1)$.

We know that:

In any set of three consecutive integers, at least one must be even (divisible by $2$).

In any set of three consecutive integers, exactly one must be divisible by $3$.

Therefore, the product $(n-1)n(n+1)$ must always be divisible by $2$ and by $3$.
Since $\gcd(2,3)=1$, the product must be divisible by $2 \times 3 = 6$.

To confirm this is the largest such integer $k$, we can test for small values of $n$:
For $n=2$: $2^3 - 2 = 8 - 2 = 6$.
For $n=3$: $3^3 - 3 = 27 - 3 = 24$.
For $n=4$: $4^3 - 4 = 64 - 4 = 60$.

The largest integer $k$ must divide $6$, $24$, and $60$.

Thus, the largest integer $k$ that divides $n^3-n$ for all integers $n \ge 2$ is $6$.
Answer: \boxed{6}"
:::

:::question type="Short Answer" question="If $\gcd(a,b)=1$, prove that $\gcd(a+b, ab)=1$." hint="Assume a prime $p$ divides $\gcd(a+b, ab)$ and show it leads to a contradiction using the fact that $\gcd(a,b)=1$." solution="Let $d = \gcd(a+b, ab)$. We want to prove that $d=1$.
Assume, for the sake of contradiction, that $d > 1$.
Then there must exist a prime number $p$ such that $p$ divides $d$.
Since $p|d$, we have $p|(a+b)$ and $p|ab$.

From $p|ab$, by the property of prime numbers, it must be that $p|a$ or $p|b$.

Case 1: Assume $p|a$.
Since $p|(a+b)$ and $p|a$, it implies $p$ must divide their difference:

So, if $p|a$, then $p$ must also divide $b$.

Case 2: Assume $p|b$.
Since $p|(a+b)$ and $p|b$, it implies $p$ must divide their difference:

So, if $p|b$, then $p$ must also divide $a$.

In both cases, we conclude that $p$ divides both $a$ and $b$.
This means that $p$ is a common divisor of $a$ and $b$.
Therefore, $p$ must divide $\gcd(a,b)$.

However, we are given that $\gcd(a,b)=1$.
If $p|\gcd(a,b)$ and $\gcd(a,b)=1$, then $p|1$, which is impossible for a prime $p$.
This contradiction arises from our initial assumption that $d>1$.
Therefore, our assumption must be false, and $d$ must be $1$.

Hence, if $\gcd(a,b)=1$, then $\gcd(a+b, ab)=1$.
Answer: \boxed{\text{Proof shows } \gcd(a+b, ab)=1}"
:::

:::question type="NAT" question="Find the smallest positive integer $n$ such that $n$ has exactly 6 divisors and is a multiple of 10." answer="20" hint="If $n$ has 6 divisors, what are the possible forms of its prime factorization? Use the condition that $n$ is a multiple of 10 to restrict the prime factors." solution="Let $n$ be a positive integer. We are given two conditions:

$n$ has exactly 6 divisors, i.e., $d(n)=6$.

$n$ is a multiple of 10.

First, let's analyze the number of divisors. If the prime factorization of $n$ is $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, then the number of divisors is $d(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$.
Since $d(n)=6$, there are two possible forms for the exponents:
a) $k=1$: $e_1+1=6 \implies e_1=5$. So $n = p^5$ for some prime $p$.
b) $k=2$: $(e_1+1)(e_2+1)=6$. Since $e_1, e_2 \ge 1$, the only integer solution (up to order) is $e_1+1=3$ and $e_2+1=2$, which means $e_1=2$ and $e_2=1$. So $n = p_1^2 p_2^1$ for distinct primes $p_1, p_2$.

Next, let's use the condition that $n$ is a multiple of 10. This means $n$ must be divisible by both $2$ and $5$. So, $n$ must have $2$ and $5$ as prime factors.

Consider Case a): $n = p^5$.
For $n$ to be a multiple of 10, $p$ must be $2$ and $5$ simultaneously, which is impossible.
If $p=2$, $n=2^5=32$. Not a multiple of $5$.
If $p=5$, $n=5^5=3125$. Not a multiple of $2$.
Thus, $n$ cannot be of the form $p^5$.

Consider Case b): $n = p_1^2 p_2^1$.
Since $n$ must be a multiple of 10, $\{p_1, p_2\}$ must include $2$ and $5$. We need to consider the smallest possible values for $n$.

Subcase b1): $p_1=2$ and $p_2=5$.

Let's check the conditions: $d(20) = (2+1)(1+1) = 3 \cdot 2 = 6$. (Correct)
$20$ is a multiple of $10$. (Correct)
So $n=20$ is a candidate.

Subcase b2): $p_1=5$ and $p_2=2$.

Let's check the conditions: $d(50) = (2+1)(1+1) = 3 \cdot 2 = 6$. (Correct)
$50$ is a multiple of $10$. (Correct)
So $n=50$ is a candidate.

Subcase b3): One of $p_1, p_2$ is $2$ or $5$, and the other is a different prime.
For example, if $p_1=2$, then $n=2^2 \cdot p_2^1 = 4p_2$. For $n$ to be a multiple of $10$, $p_2$ must be $5$ (already covered in b1) or $p_2$ must contain $5$ as a factor, which means $p_2=5$.
If $p_1=5$, then $n=5^2 \cdot p_2^1 = 25p_2$. For $n$ to be a multiple of $10$, $p_2$ must be $2$ (already covered in b2).
What if $p_1$ and $p_2$ are other primes, and we need to include $2$ and $5$?
This would mean $n$ has at least $3$ distinct prime factors ($p_1, p_2$, and either $2$ or $5$).
But we established $n$ can only have $1$ or $2$ distinct prime factors for $d(n)=6$.
So, this means $p_1$ and $p_2$ must be $2$ and $5$.

Comparing the candidates $n=20$ and $n=50$, the smallest positive integer is $20$.
Answer: \boxed{20}"
:::

---

What's Next?