Lesson 1: Divisibility & Prime Numbers

What You'll Learn

This lesson introduces the foundational ideas of number theory: divisibility, the Division Algorithm, prime and composite numbers, and basic properties of primes that will be used throughout the course.

Definition

Divisibility

Let

a, b \in \mathbb{Z}

with

a \neq 0

. We say $a$ divides $b$ (written

a \mid b

) if there exists an integer

k

such that:

b = ak

We also say

a

is a divisor (or factor) of

b

, and

b

is a multiple of

a

.

If

a

does not divide

b

, we write

a \nmid b

.

Examples:

3 \mid 12

(since

12 = 3 \cdot 4

), but

5 \nmid 12

Let

a, b, c \in \mathbb{Z}

.

1. Reflexivity:

a \mid a

for all

a \neq 0

.
2. Transitivity: If

a \mid b

and

b \mid c

, then

a \mid c

.
3. Linearity: If

a \mid b

and

a \mid c

, then

a \mid (bx + cy)

for all

x, y \in \mathbb{Z}

.
4. Comparison: If

a \mid b

and

b \neq 0

, then

|a| \leq |b|

.
5. If

a \mid b

and

b \mid a

, then

a = \pm b

Divisibility is transitive and respects linear combinations — key facts used in every proof.

Example — Proving a Divisibility Statement

Prove: If

6 \mid n

, then

3 \mid n

Solution Steps

For any integers

a

and

b

with

b > 0

, there exist unique integers

q

(quotient) and

r

(remainder) such that:

a = bq + r, \quad 0 \leq r < b

We write

q = a \div b

(integer quotient) and

r = a \bmod b

(remainder).

Example:

a = 23, b = 5

23 = 5 \cdot 4 + 3

, so

q = 4, r = 3

Every integer can be uniquely expressed as bq + r with 0 ≤ r < b. This is the basis of modular arithmetic.

Example — Division Algorithm

Find the quotient and remainder when

a = -17

is divided by

b = 5

Solution Steps

Definition

Prime & Composite Numbers

An integer

p > 1

is prime if its only positive divisors are

1

and

p

itself.

An integer

n > 1

that is not prime is called composite — it can be written as

n = ab

where

1 < a, b < n

.

By convention,

1

is neither prime nor composite.

The first few primes:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots

Note:

2

is the only even prime.

Theorem (Euclid, c. 300 BCE): There are infinitely many prime numbers.

Proof (by contradiction): Suppose there are only finitely many primes:

p_1, p_2, \ldots, p_n

. Consider:

N = p_1 p_2 \cdots p_n + 1

N

is not divisible by any

p_i

(since dividing gives remainder

1

). So either

N

is prime, or

N

has a prime factor not in our list. Either way, we have a prime not in the list — contradiction. ∎

One of the most elegant proofs in mathematics: multiply all known primes and add 1 to get a contradiction.

Every integer

n > 1

has at least one prime divisor. Moreover, if

n

is composite, then

n

has a prime divisor

p \leq \sqrt{n}

.

Proof of the second part: If

n = ab

with

1 < a \leq b < n

, then

a^2 \leq ab = n

, so

a \leq \sqrt{n}

. Since

a > 1

a

has a prime divisor

p \leq a \leq \sqrt{n}

. ∎

This gives us a primality test: to check if

n

is prime, only test divisors up to

\sqrt{n}

To check primality of n, you only need to check prime divisors up to √n.

Example — Testing Primality

97

prime?

Solution Steps

The Sieve of Eratosthenes

To find all primes up to

N

:

1. List all integers from

2

N

.
2. Start with the smallest unmarked number (

2

). Circle it as prime.
3. Cross out all multiples of

2

(except

2

itself).
4. Move to the next unmarked number (

3

). Circle it.
5. Cross out all multiples of

3

.
6. Repeat until you've processed all primes up to

\sqrt{N}

.
7. All remaining unmarked numbers are prime.

This ancient algorithm (c. 240 BCE) is remarkably efficient and still used in practice.

Practice Problem

easy

Find the quotient and remainder when

47

is divided by

8

. What is the remainder?

Practice Problem

easy

143

prime or composite?

Practice Problem

medium

a \mid b

and

a \mid c

, does

a \mid (2b + 3c)

Practice Problem

medium

In Euclid's proof, if we take primes

\{2, 3, 5\}

and form

N = 2 \cdot 3 \cdot 5 + 1 = 31

, is

N

prime?

1 / 5

Lesson 1: Divisibility & Prime Numbers

What You'll Learn

Divisibility

Properties of Divisibility

Example — Proving a Divisibility Statement

The Division Algorithm

Example — Division Algorithm

Prime & Composite Numbers

Euclid's Theorem — Infinitely Many Primes

Every Integer Has a Prime Divisor

Example — Testing Primality

The Sieve of Eratosthenes