The Integers

What is the division theorem?

For any integers a and b with b > 0,
there exist unique integers q (the quotient) and r (the remainder) such that: a = bq + r, and 0 ≤ r < b

How do we know that the quotient and the remainder are unique?

Suppose there were two different pairs (q,r) and (q′,r′) satisfying: a = bq +r = bq′ + r′, 0 ≤ r, r′ < b

Then b(q−q′) = r′−r
Since the right-hand side is strictly smaller than b, the only way this can happen is if both sides are 0.
Hence r=r′ and q=q′ so are unique

How is the highest common factor of two numbers denoted?

Hcf(a, b)

What is the Euclidean algorithm?

Keep repeating the division theorem. E.g. to find hcf(252, 198)

252 = 198 × 1 + 54

198 = 54 × 3 + 36

54 = 36 × 1 + 18

36 = 18 × 2

Therefore hcf(252, 198) = 18

What is Bézout’s Lemma?

For any integers a, b, there exist integers x, y such that hcf(a, b) = ax + by

How does Bézout’s Lemma work?

To find integers x, y such that hcf(30, 12) = 30x + 12y

Using the Euclidean algorithm:

30 = 12 × 2 + 6

12 = 6 × 2

Then we backsubstitute:

6 = 30 - 12 × 2

so x = 1 and y = -2

What is the proof for this lemma: ‘Let a, b, c ∈ Z. Suppose that a | b and a | c. Then a | (b + c).’

Since a | b, there exists x ∈ Z such that b = ax.

Since a | c, there exists y ∈ Z such that c = ay. 

Adding b = ax and c = ay gives b + c = ax + ay = a(x + y).

Let z = x + y. Then z ∈ Z, because x, y ∈ Z and b + c = az.

Therefore, a | (b + c).

What are some other lemmas that we can get from a | (b + c)?

Let a, b, c, k, l ∈ Z.

(a) Suppose that a | b and a | c. Then a | (kb + lc).

(b) Suppose that a | b and b | c. Then a | c.

(c) Suppose that a | b and b | a. Then a = ±b.

What is the official definition for a highest common factor?

Let a, b ∈ Z.

(a) A common factor of a and b is an integer c such that c | a and c | b.

(b) The highest common factor of a and b is the largest integer h that is a common factor of a and b and is denoted h = hcf(a, b); unless a = b = 0 and by convention we define hcf(0, 0) = 0.

What is the definition for two coprime integers?

Let a, b ∈ Z. We say that a is coprime to b if hcf(a, b) = 1.

What is the lemma that is key for the Euclidean algorithm?

Let a, b, q, r ∈ Z. Suppose that a = qb + r. Then hcf(a, b) = hcf(b, r).

What is the definition of a least common multiple?

Let a, b ∈ Z.

(a) A common multiple of a and b is an integer m such that a | m and b | m.

(b) The least common multiple of a and b is the smallest l ∈ N that is a common

multiple of a and b and is denoted l = lcm(a, b); unless one of a or b is equal to 0 and by convention we define lcm(a, 0) = 0 = lcm(0, b).

What is a lemma that combines both hcf and lcm?

Let a, b ∈ N. Then lcm(a, b)hcf(a, b) = ab.

What is the proof for this theorem 2.19 ‘Let a, b ∈ Z and p ∈ N be prime. Suppose that p | ab. Then p | a or p | b’

Let h = hcf(p, b). Since p is prime, the only positive factors of p are 1 and p.

Therefore, h must be either 1 or p. We consider these two cases separately.

Case 1: h = p. Then p | b.

Case 2: h = 1. Then by Theorem 2.14 there exist x, y ∈ Z such that 1 = xp + yb. Multiplying by a we obtain

a = axp + ayb = (ax)p + y(ab).

Now p | p, and p | ab. Therefore, p | a.

In both cases we have shown that p | a or p | b, which proves the theorem.

What is the proof for this corollary ‘Let a₁, a₂, . . . , a_n ∈ Z and let p ∈ N be prime. Suppose that p | a₁a₂ . . . a_n. Then p | a_i for some i = 1, 2, . . . , n.’

We have p | (a₁a₂ . . . a_n−1)a_n so by Theorem 2.19, either p | a₁a₂ . . . a_n−1 or p | a_n. If p | a_n, then we are done. Otherwise, using Theorem 2.19 again we see that p | a₁a₂ . . . a_n−2 or p | a_n−1. Continuing in this way we will eventually see that p | a_i

for some i = 1, 2, . . . , n.

What is the proof for this proposition 2.22 ‘Let n ∈ N with n > 1. Then there exist prime numbers p₁, p₂, . . . , p_k such that n = p₁p₂ · · · p_k.’

If n is prime, then we take k = 1 and p₁ = n.

So suppose that n is not prime. Let d be a factor of n with 1 < d < n and d as small as possible. Then d must be prime, because if c is a factor of d with 1 ≤ c < d, then c is a factor of n that is smaller than d so must be equal to 1.

We set p₁ = d and let n₂ ∈ N be such that n = p₁n₂.

If n₂ is prime, then we can take k = 2 and p₂ = n₂ and we are done.

Otherwise, we can apply the argument above to n2 in place of n and find a prime number p₂ and a natural number n₃ such that n₂ = p₂n₃. Then n = p₁p₂n₃.

Continuing in this way, we get a sequence of prime numbers p₁, p₂, p₃, . . . and natural numbers n = n₁ > n₂ > n₃ > . . . . Eventually, for some k ∈ N we must have that n_k is prime. Then we take p_k = n_k and we have n = p₁p₂ · · · p_k is a factorization of n as a product of primes.

What is the fundamental theorem of arithmetic?

Let n ∈ N with n > 1. Then:

(a) there exist prime numbers p₁ ≤ p₂ ≤ · · · ≤ p_k such that n = p₁p₂ · · · p_k.

(b) if q₁ ≤ q₂ ≤ · · · ≤ q_l are prime numbers such that n = q₁q₂ · · · q_l, then k = l and q_i = p_i for all i = 1, 2, . . . , k.