Divisibility basics

This chapter lays the groundwork for understanding divisibility in Number Theory, focusing on fundamental concepts such as prime numbers, prime factorisation, and the properties of factors and multiples. A solid grasp of these topics is crucial for tackling more complex problems in modular arithmetic and number theory applications, making them highly relevant for the CMI examination.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Prime numbers | | 2 | Prime factorisation | | 3 | Highest power of a prime | | 4 | Factors and multiples |

---

We begin with Prime numbers.

Part 1: Prime numbers

Prime numbers are fundamental building blocks in number theory, playing a crucial role in cryptography, divisibility, and the structure of integers. We explore their definitions, properties, and applications to solve complex problems.

---

Core Concepts

1. Definition and Basic Properties

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not prime is called a composite number.

📖 Prime Number

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ .

Worked Example: Determine if 1, 2, 9, 17, and 51 are prime or composite.

Step 1: Check numbers greater than 1.

> The number 1 is neither prime nor composite by definition.

Step 2: Check 2.

> The only positive divisors of 2 are 1 and 2. Thus, 2 is prime.

Step 3: Check 9.

> The positive divisors of 9 are 1, 3, 9. Since 3 is a divisor other than 1 and 9, 9 is composite.

Step 4: Check 17.

> We test for divisors from 2 up to $\lfloor\sqrt{17}\rfloor = 4$ .
> $17 \div 2$ (remainder 1)
> $17 \div 3$ (remainder 2)
> $17 \div 4$ (remainder 1)
> No divisors found. Thus, 17 is prime.

Step 5: Check 51.

> We test for divisors.
> $51 \div 3 = 17$ .
> Since 3 is a divisor other than 1 and 51, 51 is composite.

Answer: 1 (neither), 2 (prime), 9 (composite), 17 (prime), 51 (composite).

:::question type="MCQ" question="Which of the following numbers is prime?" options=["1","91","119","131"] answer="131" hint="Check for divisibility by small primes up to the square root of the number." solution="Step 1: Analyze 1.
> The number 1 is neither prime nor composite.

Step 2: Analyze 91.
> $91 = 7 \times 13$ . Thus, 91 is composite.

Step 3: Analyze 119.
> $119 = 7 \times 17$ . Thus, 119 is composite.

Step 4: Analyze 131.
> We check for prime divisors up to $\lfloor\sqrt{131}\rfloor = 11$ .
> $131 \div 2$ (remainder 1)
> $131 \div 3$ (sum of digits $1+3+1=5$ , not div by 3)
> $131 \div 5$ (does not end in 0 or 5)
> $131 \div 7 = 18$ with remainder 5
> $131 \div 11 = 11$ with remainder 10
> No prime divisors found. Thus, 131 is prime.

The correct option is 131."
:::

---

2. Fundamental Theorem of Arithmetic (Unique Prime Factorization)

Every integer greater than 1 can be uniquely expressed as a product of prime numbers, up to the order of the factors.

📐 Prime Factorization

For any integer $n > 1$ , there exist unique prime numbers $p_1, p_2, \ldots, p_k$ and unique positive integers $e_1, e_2, \ldots, e_k$ such that

n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}

Worked Example: Find the prime factorization of 360 and 1001.

Step 1: Factorize 360.

> We start dividing by the smallest prime, 2.
> $360 = 2 \times 180$
> $180 = 2 \times 90$
> $90 = 2 \times 45$
> $45 = 3 \times 15$
> $15 = 3 \times 5$
> $5 = 5 \times 1$

Step 2: Collect prime factors for 360.

1001 \div 7 = 143

1001 = 7 \times 11 \times 13

360 = 2^3 \times 3^2 \times 5

\sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor

and

n = \left\lfloor \frac{20}{2^1} \right\rfloor + \left\lfloor \frac{20}{2^2} \right\rfloor + \left\lfloor \frac{20}{2^3} \right\rfloor + \left\lfloor \frac{20}{2^4} \right\rfloor + \left\lfloor \frac{20}{2^5} \right\rfloor + \cdots

* * S t e p 3 : * * C a l c u l a t e t h e t e r m s . >

\left\lfloor \frac{20}{2} \right\rfloor = 10

>

\left\lfloor \frac{20}{4} \right\rfloor = 5

>

\left\lfloor \frac{20}{8} \right\rfloor = 2

>

\left\lfloor \frac{20}{16} \right\rfloor = 1

> All subsequent terms will be 0.

n = 10 + 5 + 2 + 1 = 18

n

p_i | ((p_1 p_2 \cdots p_k + 1) - (p_1 p_2 \cdots p_k))

>

p_i | 1

is a prime number and therefore

(7-1)! = 6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720

p

(2^{16})^3 \times 2^2 \equiv (1)^3 \times 2^2 \pmod{17}

>

1^3 \times 4 \equiv 4 \pmod{17}

2^{50} \equiv 4 \pmod{17}

(2^{16})^3 \times 2^2 \equiv (1)^3 \times 2^2 \pmod{17}

>

1 \times 4 \equiv 4 \pmod{17}

p

k = \sum_{j=1}^{\infty} \left\lfloor \frac{n}{p^j} \right\rfloor

and

k = \left\lfloor \frac{100}{7^1} \right\rfloor + \left\lfloor \frac{100}{7^2} \right\rfloor + \left\lfloor \frac{100}{7^3} \right\rfloor + \cdots

>

k = \left\lfloor \frac{100}{7} \right\rfloor + \left\lfloor \frac{100}{49} \right\rfloor + \left\lfloor \frac{100}{343} \right\rfloor + \cdots

>

k = 14 + 2 + 0

* * S t e p 3 : * * S u m t h e t e r m s . >

k = 14 + 2 = 16

k

(p-5)(p+2) = 0

p

p-5 = 0 \implies p = 5

>

p+2 = 0 \implies p = -2

p=5

(p-3)(p+2) = 0

p

p-3 = 0 \implies p = 3

>

p+2 = 0 \implies p = -2$$

Step 2: Check for prime solutions.
> A prime number must be a natural number greater than 1.
> $p=3$ is a prime number.
> $p=-2$ is not a prime number.

The value of $p$ is 3."
:::

:::question type="MCQ" question="Which of the following numbers is the smallest prime that is also a sum of two prime numbers?" options=["5","7","11","13"] answer="5" hint="Test each option. Remember that 2 is the only even prime." solution="Step 1: Analyze the definition.
> We are looking for the smallest prime number that can be expressed as the sum of two other prime numbers.

Step 2: Check $p=5$ .
> Is 5 prime? Yes.
> Can 5 be written as a sum of two primes?
> Possible sums of primes:
> $2+3=5$ . Yes.
> Since 5 is prime and $5=2+3$ (where 2 and 3 are primes), 5 fits the criteria.

Step 3: Check $p=7$ .
> Is 7 prime? Yes.
> Can 7 be written as a sum of two primes?
> $2+5=7$ . Yes.
> However, we are looking for the smallest such prime. Since 5 is smaller and fits the criteria, 7 is not the answer.

Step 4: Check $p=11$ .
> Is 11 prime? Yes.
> Can 11 be written as a sum of two primes?
> $2+9$ (9 is not prime)
> $3+8$ (8 is not prime)
> $5+6$ (6 is not prime)
> None of the sums work with 2 or 3.
> $11 = 5+6$ . $11 = 2+?$ no. $11 = 3+8$ no. $11 = 5+6$ no.
> Wait, let's systematically list sums of primes:
> $2+3=5$
> $2+5=7$
> $2+11=13$
> $3+2=5$
> $3+5=8$ (not prime)
> $3+7=10$ (not prime)
> $5+2=7$
> $5+3=8$ (not prime)
> $5+5=10$ (not prime)
> $5+7=12$ (not prime)
> So, $11$ cannot be written as a sum of two primes from the list of small primes. This is incorrect.
> $11 = 2+9$ (9 not prime)
> $11 = 3+8$ (8 not prime)
> $11 = 5+6$ (6 not prime)
> Let's try to express 11 as sum of two primes. The primes must be less than 11.
> $11 = p_1 + p_2$ .
> If $p_1=2$ , $p_2=9$ (not prime).
> If $p_1=3$ , $p_2=8$ (not prime).
> If $p_1=5$ , $p_2=6$ (not prime).
> It seems 11 is not a sum of two primes. This makes the question harder.
> Let's re-verify my earlier sums.
> $5 = 2+3$ . (Both 2 and 3 are primes).
> $7 = 2+5$ . (Both 2 and 5 are primes).
> $13 = 2+11$ . (Both 2 and 11 are primes).
> $13 = 3+10$ (no).
> $13 = 5+8$ (no).
> $13 = 7+6$ (no).
> So, 5, 7, 13 are all primes that are sums of two primes.
> The question asks for the smallest prime that is also a sum of two prime numbers.
> Among 5, 7, 13, the smallest is 5.

The smallest prime that is also a sum of two prime numbers is 5."
:::

---

Summary

❗ Key Formulas & Takeaways

| Formula/Concept | Expression |

|---|----------------|------------| | 1 | Prime Definition |

p > 1

, divisors are

1, p

| | 2 | Fundamental Theorem of Arithmetic |

n = p_1^{e_1} \cdots p_k^{e_k}

(unique) | | 3 | Euclid's Lemma | If

p | ab

, then

p | a

p | b

p>3

form |

p \equiv \pm 1 \pmod 6

| | 6 | Divisibility of

p^2-1

for

p>3

p^2-1

is divisible by 24 | | 7 | Wilson's Theorem |

(p-1)! \equiv -1 \pmod p

for prime

p

| | 8 | Fermat's Little Theorem |

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

for

p \nmid a

---

What's Next?

💡 Continue Learning

This topic connects to:

Modular Arithmetic: Many properties of prime numbers are best understood and applied using modular arithmetic.

Diophantine Equations: Prime numbers often appear as solutions or constraints in integer equations.

Cryptography: Prime numbers are the backbone of modern public-key cryptography (e.g., RSA algorithm).

Number Theoretic Functions: Functions like $\phi(n)$ (Euler's totient function) and $\tau(n)$ (number of divisors) heavily rely on prime factorization.

---

💡 Next Up

Proceeding to Prime factorisation.

---

Part 2: Prime factorisation

Prime Factorisation

Overview

Prime factorisation is the structural backbone of elementary number theory. It expresses every integer greater than

1

as a product of primes, and that factorization controls divisibility, gcd, lcm, highest powers of primes, and many proof techniques. In exam problems, the key is not only to factor numbers correctly but also to use factorization to read deeper properties immediately. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Write integers as products of prime powers.

Use uniqueness of prime factorisation correctly.

Compute gcd and lcm from prime exponents.

Decide divisibility using exponent comparison.

Apply prime factorization as a reasoning tool in proofs.

---

Core Idea

📖 Prime Factorisation

A prime factorisation of an integer $n>1$ is an expression of the form

$\qquad n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

where the $p_i$ are distinct primes and the $a_i$ are positive integers.

Example:

\qquad 360 = 2^3\cdot 3^2\cdot 5

---

Fundamental Theorem of Arithmetic

❗ Uniqueness

Every integer greater than $1$ can be written as a product of primes, and this factorisation is unique up to the order of the primes.

This means that if

\qquad 2^a3^b5^c = 2^x3^y5^z

then

\qquad a=x,\quad b=y,\quad c=z

provided both sides are written fully in prime factorized form. ---

Divisibility via Prime Exponents

📐 Exponent Comparison

Suppose

$\qquad m = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$
and
$\qquad n = p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}$

Then

$\qquad m \mid n$

if and only if

$\qquad a_i \le b_i \quad \text{for all } i$

This is one of the cleanest ways to test divisibility. ---

GCD and LCM from Prime Factorisation

📐 GCD from Exponents

If

$\qquad m = \prod p_i^{a_i}, \qquad n = \prod p_i^{b_i}$

then

$\qquad \gcd(m,n) = \prod p_i^{\min(a_i,b_i)}$

📐 LCM from Exponents

Under the same notation,

$\qquad \operatorname{lcm}(m,n) = \prod p_i^{\max(a_i,b_i)}$

---

Minimal Worked Examples

Example 1 Find the prime factorisation of

540

. We have

\qquad 540 = 54\cdot 10 = (2\cdot 3^3)(2\cdot 5)

\qquad 540 = 2^2\cdot 3^3\cdot 5

--- Example 2 Find

\gcd(72,120)

. Prime factorizations:

\qquad 72 = 2^3\cdot 3^2

\qquad 120 = 2^3\cdot 3 \cdot 5

\qquad \gcd(72,120)=2^{\min(3,3)}\cdot 3^{\min(2,1)} = 2^3\cdot 3 = 24

---

Prime Factorisation and Perfect Squares

📐 Square Criterion

An integer is a perfect square if and only if every prime exponent in its prime factorisation is even.

Example:

$36 = 2^2\cdot 3^2$ is a square

$72 = 2^3\cdot 3^2$ is not a square because the exponent of $2$ is odd

---

Common Patterns

💡 Typical Exam Patterns

Prime factorize a number completely.

Find gcd or lcm by exponent comparison.

Decide whether one number divides another.

Find smallest multiplier to make a number a square or cube.

Use uniqueness of factorization to compare expressions.

---

Common Mistakes

⚠️ Avoid These Errors

❌ stopping factorization too early at a composite number

✅ continue until every factor is prime

❌ confusing gcd with lcm exponent rules

✅ gcd uses minimum, lcm uses maximum

❌ using divisibility language without exponent comparison

✅ prime exponents make divisibility transparent

❌ forgetting uniqueness is only up to order

✅ the order of prime factors does not matter

---

CMI Strategy

💡 How to Attack Prime-Factorisation Problems

Factor numbers completely into primes first.

Align prime powers clearly.

Use exponent comparison for divisibility.

Use min-exponents for gcd and max-exponents for lcm.

In proof questions, rely on uniqueness of prime factorization.

---

Practice Questions

:::question type="MCQ" question="The prime factorisation of

84

is" options=["

2^2\cdot 3\cdot 7

","

2\cdot 3^2\cdot 7

","

2^3\cdot 3\cdot 7

","

2^2\cdot 3^2

"] answer="A" hint="Factorize step by step." solution="We have

\qquad 84 = 2\cdot 42 = 2\cdot 2\cdot 21 = 2^2\cdot 3\cdot 7

Hence the correct option is

\boxed{A}

." ::: :::question type="NAT" question="Find

\operatorname{lcm}(18,24)

." answer="72" hint="Use prime factorization." solution="We have

\qquad 18 = 2\cdot 3^2

and

\qquad 24 = 2^3\cdot 3

\qquad \operatorname{lcm}(18,24)=2^{\max(1,3)}\cdot 3^{\max(2,1)} = 2^3\cdot 3^2 = 72

Hence the answer is

\boxed{72}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["Every integer greater than

1

has a prime factorisation","Prime factorisation is unique up to order","If

m \mid n

, then each prime exponent in

m

is at most the corresponding exponent in

n

","An integer is a perfect square iff all prime exponents are odd"] answer="A,B,C" hint="Recall the fundamental theorem and exponent comparison." solution="1. True.

True.

False. For a perfect square, all prime exponents must be even.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Using prime factorization, find

\gcd(90,126)

." answer="

18

" hint="Factorize both numbers fully." solution="We have

\qquad 90 = 2\cdot 3^2\cdot 5

and

\qquad 126 = 2\cdot 3^2\cdot 7

Therefore

\qquad \gcd(90,126)=2^{\min(1,1)}\cdot 3^{\min(2,2)} = 2\cdot 3^2 = 18

Hence the answer is

\boxed{18}

." ::: ---

Summary

❗ Key Takeaways for CMI

Every integer greater than $1$ has a unique prime factorisation.

Divisibility becomes exponent comparison under prime factorization.

GCD uses minimum exponents; LCM uses maximum exponents.

Perfect-square tests come directly from parity of exponents.

Prime factorization is a structure tool, not just a computation tool.

---

💡 Next Up

Proceeding to Highest power of a prime.

---

Part 3: Highest power of a prime

Highest Power of a Prime

Overview

The highest power of a prime dividing a number is a central concept in divisibility. It tells us exactly how many times a prime can be factored out. This topic appears in factorial problems, divisibility proofs, trailing-zero questions, and exponent comparisons. In exam problems, the key skill is to count powers carefully without overcounting. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Interpret the highest power of a prime dividing an integer.

Find the exponent of a prime in a prime factorization.

Compute the highest power of a prime dividing factorials.

Use repeated division and counting methods correctly.

Solve standard trailing-zero and valuation-style questions.

---

Core Idea

📖 Highest Power of a Prime Dividing a Number

If

$\qquad p^k \mid n \quad \text{but} \quad p^{k+1}\nmid n$

then $p^k$ is the highest power of the prime $p$ dividing $n$ .

The exponent

k

is the number of times

p

appears in the prime factorization of

n

. For example:

in $72 = 2^3\cdot 3^2$ , the highest power of $2$ dividing $72$ is $2^3$

the highest power of $3$ dividing $72$ is $3^2$

---

Basic Method

📐 Prime Exponent in a Number

To find the highest power of $p$ dividing $n$ :

factorize $n$

count how many times $p$ appears

Example: For

\qquad 540 = 2^2\cdot 3^3\cdot 5

the highest power of

3

dividing

540

\qquad 3^3

---

Highest Power in a Factorial

📐 Legendre-Type Counting Formula

The exponent of a prime $p$ in $n!$ is

$\qquad \left\lfloor \dfrac{n}{p} \right\rfloor + \left\lfloor \dfrac{n}{p^2} \right\rfloor + \left\lfloor \dfrac{n}{p^3} \right\rfloor + \cdots$

The sum stops when the powers exceed

n

. :::

❗ Why It Works

$\left\lfloor \dfrac{n}{p} \right\rfloor$ counts multiples of $p$

$\left\lfloor \dfrac{n}{p^2} \right\rfloor$ counts an extra copy of $p$ from multiples of $p^2$

and so on

---

Trailing Zeros

📐 Trailing Zeros in

n!

The number of trailing zeros in $n!$ is the exponent of $10$ in $n!$ .

Since
$\qquad 10=2\cdot 5$
and powers of $2$ are more frequent than powers of $5$ in factorials, the number of trailing zeros is the exponent of $5$ in $n!$ .

This is one of the most common applications. ---

Minimal Worked Examples

Example 1 Find the highest power of

2

dividing

40

. Factorize:

\qquad 40 = 2^3\cdot 5

So the highest power is

\qquad \boxed{2^3}

. --- Example 2 Find the exponent of

5

25!

. Use the formula:

\qquad \left\lfloor \dfrac{25}{5} \right\rfloor + \left\lfloor \dfrac{25}{25} \right\rfloor = 5+1=6

So the highest power of

5

dividing

25!

\qquad \boxed{5^6}

. ---

Common Patterns

💡 Typical Exam Patterns

Find the highest power of $p$ dividing a specific integer.

Find the exponent of a prime in $n!$ .

Count trailing zeros in a factorial.

Compare powers in products or binomial coefficients.

Determine divisibility by prime powers.

---

Common Mistakes

⚠️ Avoid These Errors

❌ stopping at $\left\lfloor \dfrac{n}{p} \right\rfloor$ in factorial questions

✅ also count

\left\lfloor \dfrac{n}{p^2} \right\rfloor

\left\lfloor \dfrac{n}{p^3} \right\rfloor

, etc.

❌ forgetting that trailing zeros depend on pairs of $2$ and $5$

✅ usually powers of

5

are the limiting factor

❌ confusing the exponent with the prime power itself

✅ exponent

k

and highest power

p^k

are different objects

---

CMI Strategy

💡 How to Attack Prime-Power Questions

Factorize first if the number is small.

For factorials, switch immediately to the floor-sum formula.

In trailing-zero questions, count powers of $5$ .

Separate “exponent of $p$ ” from “highest power of $p$ ”.

Be systematic; skipped powers are a common source of error.

---

Practice Questions

:::question type="MCQ" question="The highest power of

2

dividing

48

is" options=["

2^2

","

2^3

","

2^4

","

2^5

"] answer="C" hint="Prime factorize

48

." solution="We have

\qquad 48 = 2^4 \cdot 3

So the highest power of

2

dividing

48

\qquad \boxed{2^4}

Hence the correct option is

\boxed{C}

." ::: :::question type="NAT" question="Find the exponent of

5

30!

." answer="7" hint="Use the floor-sum formula." solution="The exponent of

5

30!

\qquad \left\lfloor \dfrac{30}{5} \right\rfloor + \left\lfloor \dfrac{30}{25} \right\rfloor = 6+1=7

Hence the answer is

\boxed{7}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["The number of trailing zeros in

n!

equals the exponent of

10

n!

","In factorials, powers of

2

are usually more frequent than powers of

5

","The exponent of

p

n!

is always

\left\lfloor \dfrac{n}{p} \right\rfloor

only","If

72=2^3\cdot 3^2

, then the highest power of

3

dividing

72

3^2

"] answer="A,B,D" hint="Think carefully about extra multiples of

p^2,p^3,\dots

." solution="1. True.

True.

False, because higher powers like

p^2,p^3,\dots

also contribute.

True.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Find the highest power of

2

dividing

20!

." answer="

2^{18}

" hint="Use

\left\lfloor \dfrac{20}{2} \right\rfloor + \left\lfloor \dfrac{20}{4} \right\rfloor + \left\lfloor \dfrac{20}{8} \right\rfloor + \left\lfloor \dfrac{20}{16} \right\rfloor

." solution="The exponent of

2

20!

\qquad \left\lfloor \dfrac{20}{2} \right\rfloor + \left\lfloor \dfrac{20}{4} \right\rfloor + \left\lfloor \dfrac{20}{8} \right\rfloor + \left\lfloor \dfrac{20}{16} \right\rfloor

\qquad 10+5+2+1 = 18

Hence the highest power of

2

dividing

20!

\qquad \boxed{2^{18}}

." ::: ---

Summary

❗ Key Takeaways for CMI

The highest power of $p$ dividing $n$ is determined by the exponent of $p$ in the factorization of $n$ .

For factorials, use the floor-sum counting formula.

Trailing-zero questions reduce to counting powers of $5$ .

The exponent and the prime power must be distinguished carefully.

Systematic counting prevents errors.

---

💡 Next Up

Proceeding to Factors and multiples.

---

Part 4: Factors and multiples

Factors and Multiples

Overview

Factors and multiples are the first language of divisibility in number theory. Many harder number-theory problems reduce to this basic vocabulary: one number dividing another, common divisors, least common multiples, and structural properties of integers. In exam problems, this topic is tested not by definitions alone, but by how fluently you can use them in proofs and counting. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

State and use the definitions of factor, divisor, and multiple.

Work with divisibility notation correctly.

Use basic divisibility properties in proofs.

Distinguish common factors from common multiples.

Solve short questions involving gcd, lcm, and divisibility structure.

---

Core Definitions

📖 Factor and Multiple

If an integer $a$ divides an integer $b$ , we write

$\qquad a \mid b$

and say:

$a$ is a factor or divisor of $b$

$b$ is a multiple of $a$

This means there exists an integer

k

such that

\qquad b = ak

::: Examples:

$3 \mid 18$ because $18 = 3\cdot 6$

$5 \nmid 18$ because $18$ is not of the form $5k$ for any integer $k$

---

Basic Divisibility Facts

📐 Standard Properties

For integers $a,b,c$ :

If $a \mid b$ and $a \mid c$ , then

\qquad a \mid (b+c)

and

\qquad a \mid (b-c)

If $a \mid b$ , then

\qquad a \mid bc

for every integer

c

If $a \mid b$ and $b \mid c$ , then

\qquad a \mid c

Every integer divides $0$ :

\qquad a \mid 0

$1$ divides every integer

These are the main algebra rules for divisibility manipulation. ---

Common Factors and Common Multiples

📖 Common Factor

A common factor of two integers is an integer dividing both of them.

📖 Greatest Common Divisor

The greatest common divisor of $a$ and $b$ is denoted by

$\qquad \gcd(a,b)$

It is the largest positive integer dividing both $a$ and $b$ .

📖 Least Common Multiple

The least common multiple of $a$ and $b$ is denoted by

$\qquad \operatorname{lcm}(a,b)$

It is the smallest positive integer that is a multiple of both $a$ and $b$ .

---

Relation Between GCD and LCM

📐 Product Relation

For positive integers $a,b$ ,

$\qquad \gcd(a,b)\cdot \operatorname{lcm}(a,b)=ab$

This is one of the most frequently used relations in elementary number theory. ---

Minimal Worked Examples

Example 1 Show that if

4 \mid n

and

6 \mid n

, then

12 \mid n

need not always follow directly from the statements alone, but in this case it does because

\qquad \operatorname{lcm}(4,6)=12

So any common multiple of

4

and

6

is a multiple of

12

. --- Example 2 If

3 \mid 24

and

3 \mid 15

, then

\qquad 3 \mid (24-15)=9

This is a direct use of the subtraction property. ---

Divisibility Notation Matters

⚠️ Read This Carefully

The statement
$\qquad a \mid b$
does not mean
$\qquad b \mid a$

For example:

$2 \mid 8$ is true

$8 \mid 2$ is false

---

Common Patterns

💡 Typical Exam Patterns

Prove one number divides another.

Find all common factors or common multiples.

Use gcd and lcm together.

Use factor-multiple language in short proofs.

Simplify divisibility expressions using subtraction or linear combinations.

---

Common Mistakes

⚠️ Avoid These Errors

❌ reversing divisibility direction

✅

a \mid b

means

b=ak

❌ confusing factor with multiple

✅ factor divides, multiple is divided by the factor

❌ assuming if $a \mid bc$ then $a \mid b$ or $a \mid c$ always

✅ this is not always true without extra conditions

❌ forgetting positivity in gcd/lcm definitions

✅ gcd and lcm are usually taken positive

---

CMI Strategy

💡 How to Attack Divisibility Basics

Translate $a \mid b$ into $b=ak$ .

Use addition and subtraction properties first.

When two divisibility conditions appear, think gcd or lcm.

Keep factor and multiple language exact.

In proofs, introduce a witness integer explicitly when needed.

---

Practice Questions

:::question type="MCQ" question="Which of the following is true?" options=["

18

is a factor of

3

","

3

is a factor of

18

","

18

divides

3

","

5

divides

18

"] answer="B" hint="Use the meaning of factor and divisibility." solution="Since

\qquad 18 = 3\cdot 6

, we have

\qquad 3 \mid 18

. So

3

is a factor of

18

. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="Find

\gcd(18,24)

." answer="6" hint="List common factors or factorize." solution="Factors of

18

are

\qquad 1,2,3,6,9,18

Factors of

24

are

\qquad 1,2,3,4,6,8,12,24

The greatest common factor is

\qquad 6

Hence the answer is

\boxed{6}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["If

a \mid b

and

a \mid c

, then

a \mid (b+c)

","If

a \mid b

, then

a \mid bc

for every integer

c

","Every integer divides

0

","If

a \mid bc

, then always

a \mid b

"] answer="A,B,C" hint="Recall the standard divisibility rules." solution="1. True.

True.

False in general. For example,

6 \mid 2\cdot 3

but

6 \nmid 2

and

6 \nmid 3

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Show that if

a \mid b

and

a \mid c

, then

a \mid (b-c)

." answer="Write

b=am

and

c=an

." hint="Use the definition of divisibility." solution="Since

a \mid b

, there exists an integer

m

such that

\qquad b=am

Since

a \mid c

, there exists an integer

n

such that

\qquad c=an

Therefore

\qquad b-c = am-an = a(m-n)

Since

m-n

is an integer, it follows that

\qquad a \mid (b-c)

Hence the result is proved." ::: ---

Summary

❗ Key Takeaways for CMI

$a \mid b$ means $b=ak$ for some integer $k$ .

Factors divide; multiples are divisible by those factors.

Divisibility is preserved under addition and subtraction.

GCD is the largest common divisor; LCM is the smallest common multiple.

Exact language matters in number theory.

Chapter Summary

❗ Divisibility basics — Key Points

Prime Numbers: Integers greater than 1 with exactly two distinct positive divisors (1 and itself). They are the fundamental multiplicative building blocks of all integers.

Fundamental Theorem of Arithmetic: Every integer greater than 1 can be uniquely expressed as a product of prime numbers, up to the order of the factors. This theorem underpins all subsequent divisibility concepts.

Prime Factorisation: The decomposition of a composite number into its prime factors. This method is indispensable for calculating the number of divisors `d(n)`, sum of divisors `\sigma(n)`, greatest common divisor `\operatorname{gcd}(a,b)`, and least common multiple `\operatorname{lcm}(a,b)`.

Highest Power of a Prime: Legendre's Formula, expressed as ` $E_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$ , determines the exact exponent of a prime `p` in the prime factorisation of `n!`.

Divisors and Sums: For a number $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ , the total number of positive divisors is ` $d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$ `, and the sum of all positive divisors is ` $\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1}-1}{p_i-1}$ .

GCD and LCM Relationship: For any two positive integers `a` and `b`, their product is equal to the product of their greatest common divisor and least common multiple: ` $\operatorname{gcd}(a,b) \cdot \operatorname{lcm}(a,b) = ab$ `.

---

Chapter Review Questions

:::question type="MCQ" question="Which of the following is the smallest integer with exactly 12 positive divisors?" options=["48","60","72","96"] answer="60" hint="To find the number of divisors of an integer $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ , use the formula $d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$ . Consider factorisations of 12 (e.g., $12$ , $6 \times 2$ , $4 \times 3$ , $3 \times 2 \times 2$ ) and construct the smallest numbers for each." solution="To find the smallest integer with 12 divisors, we consider the possible forms for the exponents in its prime factorisation such that $(a_1+1)(a_2+1)\cdots=12$ .

p^{11}

2^{11} = 2048

p^5 q^1

: To minimise, use the smallest primes for larger exponents:

2^5 \cdot 3^1 = 32 \cdot 3 = 96

p^3 q^2

: To minimise, use the smallest primes for larger exponents:

2^3 \cdot 3^2 = 8 \cdot 9 = 72

p^2 q^1 r^1

: To minimise, use the smallest primes for larger exponents:

2^2 \cdot 3^1 \cdot 5^1 = 4 \cdot 3 \cdot 5 = 60

Comparing these, the smallest is 60.

Let's check the given options:
* 48 = $2^4 \cdot 3^1$ , $d(48) = (4+1)(1+1) = 10$ .
* 60 = $2^2 \cdot 3^1 \cdot 5^1$ , $d(60) = (2+1)(1+1)(1+1) = 12$ .
* 72 = $2^3 \cdot 3^2$ , $d(72) = (3+1)(2+1) = 12$ . (72 is not the smallest)
* 96 = $2^5 \cdot 3^1$ , $d(96) = (5+1)(1+1) = 12$ . (96 is not the smallest)

The smallest integer with exactly 12 positive divisors is 60."
:::

:::question type="NAT" question="Find the highest power of 5 that divides 120!." answer="28" hint="Use Legendre's Formula: $E_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$ ." solution="According to Legendre's Formula, the highest power of a prime $p$ that divides $n!$ is given by $E_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots$ .
For $p=5$ and $n=120$ :
$E_5(120!) = \left\lfloor \frac{120}{5} \right\rfloor + \left\lfloor \frac{120}{5^2} \right\rfloor + \left\lfloor \frac{120}{5^3} \right\rfloor + \dots$
$E_5(120!) = \left\lfloor \frac{120}{5} \right\rfloor + \left\lfloor \frac{120}{25} \right\rfloor + \left\lfloor \frac{120}{125} \right\rfloor + \dots$
$E_5(120!) = 24 + 4 + 0 + \dots$
$E_5(120!) = 28$ .

The highest power of 5 that divides 120! is 28."
:::

:::question type="MCQ" question="Consider the following statements about prime numbers:
I. The sum of two prime numbers is always an even number.
II. If $p$ is a prime number, then $p^2+1$ is never a prime number.
III. There are infinitely many prime numbers.

Which of the above statements are true?" options=["I and II only","II and III only","I and III only","III only"] answer="III only" hint="Test statement I with $p=2$ . Test statement II with $p=2$ . Statement III is a fundamental result in number theory." solution="Let's evaluate each statement:
I. The sum of two prime numbers is always an even number. This statement is false. The prime number 2 is even. If we take $2$ and any other odd prime, say $3$ , their sum is $2+3=5$ , which is odd. If we take two odd primes, say $3$ and $5$ , their sum is $3+5=8$ , which is even. Since it's not always even, the statement is false.
II. If $p$ is a prime number, then $p^2+1$ is never a prime number. This statement is false. Consider $p=2$ . Then $p^2+1 = 2^2+1 = 4+1=5$ , which is a prime number.
III. There are infinitely many prime numbers. This statement is true. Euclid's proof by contradiction elegantly demonstrates this fact.

Therefore, only statement III is true."
:::

:::question type="NAT" question="The product of two positive integers is 720. If their greatest common divisor is 6, what is their least common multiple?" answer="120" hint="Recall the fundamental relationship between the product of two integers, their GCD, and their LCM." solution="For any two positive integers $a$ and $b$ , the product of the numbers is equal to the product of their greatest common divisor ( $\operatorname{gcd}$ ) and least common multiple ( $\operatorname{lcm}$ ).
That is, $a \cdot b = \operatorname{gcd}(a,b) \cdot \operatorname{lcm}(a,b)$ .

Given:
Product of two integers ( $a \cdot b$ ) = 720
Greatest Common Divisor ( $\operatorname{gcd}(a,b)$ ) = 6

We need to find the Least Common Multiple ( $\operatorname{lcm}(a,b)$ ).
Substituting the given values into the formula:
$720 = 6 \cdot \operatorname{lcm}(a,b)$
$\operatorname{lcm}(a,b) = \frac{720}{6}$
$\operatorname{lcm}(a,b) = 120$ .

The least common multiple of the two integers is 120."
:::

---

What's Next?

💡 Continue Your CMI Journey

Building upon the foundational concepts of divisibility and prime factorisation, the next steps in your CMI journey will delve into advanced topics such as Modular Arithmetic, where congruences provide a powerful framework for studying remainders, and Diophantine Equations, which often leverage properties of `\operatorname{gcd}` and `\operatorname{lcm}` for integer solutions. These chapters will further develop your ability to solve complex problems in Number Theory.

Divisibility basics

Divisibility basics

Chapter Contents

| Topic |

Part 1: Prime numbers

Core Concepts

1. Definition and Basic Properties

2. Fundamental Theorem of Arithmetic (Unique Prime Factorization)

3. Euclid's Lemma

4. Infinitude of Primes (Euclid's Theorem)

5. Primes of the form 6k±16k \pm 16k±1 (for p & gt;3)

Advanced Applications

1. Divisibility of p2−1p^2-1p2−1 by 24 for p & gt;3

2. Divisibility of p(p−1)p(p-1)p(p−1) by 3 for any prime ppp

3. Divisibility by 6 for p−1p-1p−1 or p+1p+1p+1 for p & gt;3

4. Properties of Primes Modulo 8 (for p & gt;3)

5. Wilson's Theorem

6. Fermat's Little Theorem

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

| Formula/Concept | Expression |

What's Next?

Part 2: Prime factorisation

Prime Factorisation

Overview

Learning Objectives

Core Idea

Fundamental Theorem of Arithmetic

Divisibility via Prime Exponents

GCD and LCM from Prime Factorisation

Minimal Worked Examples

Prime Factorisation and Perfect Squares

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 3: Highest power of a prime

Highest Power of a Prime

Overview

Learning Objectives

Core Idea

Basic Method

Highest Power in a Factorial

Trailing Zeros

Minimal Worked Examples

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 4: Factors and multiples

Factors and Multiples

Overview

Learning Objectives

Core Definitions

Basic Divisibility Facts

Common Factors and Common Multiples

Relation Between GCD and LCM

Minimal Worked Examples

Divisibility Notation Matters

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Number Theory

Parity and structure

Congruences

GCD and LCM

Divisor-based problems

More Resources

Study Notes

Short Notes

5. Primes of the form $6k \pm 1$ (for $p & gt;3$ )

1. Divisibility of $p^2-1$ by 24 for $p & gt;3$

2. Divisibility of $p(p-1)$ by 3 for any prime $p$

3. Divisibility by 6 for $p-1$ or $p+1$ for $p & gt;3$

4. Properties of Primes Modulo 8 (for $p & gt;3$ )