Objectives

This document will explore three topics: divisors, the division algorithm and prime numbers.

Divisors

Lets start by factoring a few integers and making some simple examples.

Examples

• $20 = 10 \times 2$

Observe: We say that 10 and 2 are factors of 20

• $30 = 6 \times 5$

Observe: We say that 6 and 5 are factors of 30

• $40 = 8 \times 5$

Observe: We say that 8 and 5 are factors of 40

• $1600 = 40 \times 40$

Observe: We say that 40 is a factor of 1600. Observe also that since 40 is a factor of 1600 and 8 is a factor of 40, then 8 is a factor of 1600.

Lets formalise our observation with a definition.

Definition: Divides

Let $a,b \in \mathbb{Z}$ we denote $a | b$ when $\exists c \in \mathbb{Z}$ s.t. $b = ac$

Written: Let a and b, be integers. We say that $a | b$ (a divides b) if there exists another integer c such that b = ac. The way I remember this is to say (a factors b) instead of (a divides b).

Let’s rewrite one of our example:

• $20 = 10 \times 2$

Observe: We now say that $10 | 20$ and $2 | 20$ .

• Since 3 is not a factor of 13 , we can write $3 \not|:13$.

Take away: The $|$(divides) definition, now gives us a way to fomally express what it means for a number to be a factor of another number.

Extra

Can you think of a definition that would work for polynomials with complex roots?

Greatest Common Divisor(Factor)

d is the greatest common divisor of a and b if:

• $d | a$ and $d | b$
• if $c | a$ and $c | b$ then $c | d$

You can think of the greatest common factor as the product of all of the common factors of a and b. It is therefore intuitive to see that if a number divides both a and b, then it must also divide the greatest common divisor.

Division algorithm

Before formally stating what this is, lets make a few observations. I claim that given two whole integers $a$ and $b$, I can always write one in terms of the other. ie $a = b * q + r$ where q and r are also integers.

Examples

10 and 20

• 20 = $10 \times 2$
• Observe: Since $10 | 20$ there is no “remainder term”
• In this example: $r=0$, $q=2$.

25 and 30

• 30 = $25 \times 1 + 5$
• Observe: Since $25 \nmid 30$ we have a “remainder term”.
• In this example: $r=5$, $q=1$.

120 and 9

• 120 = $9 \times 13 + 3$
• Observe: Since $9 \nmid 120$ we have a remainder term, which is 3.
• In this example: $r=3$, $q=13$.

Observe

If we connect, what we learned in the first section on divisors. We can observe that when $a|b$ the remainder term is 0. Agree?

Actually this is not entirely true :)

Lets take 10 and 20. We can write $20 = 10 \times 1 + 10$ , even though $10|20$ , the remainder is not zero.

What we want to say is this: when $a|b$ there exists a unique combination where $a = b \times q + r$

I want to make one last bold claim, before defining the division algorithm. For a and b, regardless of whether $a|b$ we can always find an $a = b * q + r$ where r is bounded by $b$ ie $0\leq:r<b$.

This may become intuitive if you look at $a = b * q + r$ from another point of view. This equation is analogous to saying give me q lots of b and whatever is less than b, is the remainder. Confusing?

Analogy

Alice : Give me 20 apples

Bob: Sure. we have packs of 3. So I will give you 6 packs of 3 first. If I give you 7 packs, this will be more than 21.

Bob: 6 packs of 3 will give you 18. I will then need to give you 2 apples that are not in a pack to make 20.

Alice: Sure! I see now that the remaining apples will always be less than a pack.

Charlie: But what If you gave Alice 5 packs of 3 instead of 6 packs of 3. You would then have 5 apples as the remainder!

Bob: True. However, the claim above states that there exists an $a = b * q + r$ where r is bounded. Which we found!

Theorem

We now state the division algorithm theorem.

$\forall a, b \in \mathbb{Z}$ where $b > 0$ $\exists$ unique $q,r \in \mathbb{Z}$ such that $a = bq + r$ and $0\leq r < b$

Written: For all integers a and b, there exists a unique pair of integers q and r such that $a = bq + r$ and r is bounded by b.

We call q the quotient and r the remainder.

When the remainder is 0, we can safely say that $b|a$. It all comes together!

Proof omitted.

Prime Numbers

A prime number is a natural number greater than 1 which is divisible by itself and one.

A composite number is a natural number that is divisible by any natural number other than 1 and itself.

Is 1 a prime number?