1.2 Workshop 2 (Reading)

1.2.1 Preparatory exercises (1 hour)

Complete the following exercises in preparation for the Reading workshop.

Divisors

Definition (Divisor).

Let $a$ and $d$ be integers, with $d\neq 0$ . We say that $d$ divides $a$ , and that $d$ is a divisor (or factor) of $a$ , if $\frac{a}{d}$ is an integer. We also say that $a$ is divisible by $d$ .

We shall write $d\mid a$ to mean $d$ divides $a$ , and $d\nmid a$ to mean that $d$ does not divide $a$ .

Exercise 1.8.

True or false?

(a)

3

divides

12

. (b)

-3\mid 12

. (c)

12\mid 3

. (d)

5\mid 12

. (e)

0\mid 5

Definition (Common divisor).

Let $a$ and $b$ be integers. If $d\mid a$ and $d\mid b$ then we say $d$ is a common divisor of $a$ and $b$ .

Definition (Greatest common divisor, $\gcd$ ).

Let $a$ and $b$ be integers, not both zero. The greatest common divisor of $a$ and $b$ , denoted by $\gcd(a,b)$ , is the largest common divisor of $a$ and $b$ .

Exercise 1.9.

Choose two integers $a$ and $b$ between $-100$ and 100.

1.

Find the common divisors of $a$ and $b$ .
2.

What is the value of $\gcd(a,b)$ ?

Definition (Coprime).

Let $a$ and $b$ be integers. We say that $a$ and $b$ are coprime if $\gcd(a,b)=1$ .

Exercise 1.10.

Think of an example of two coprime numbers.

Direct Proof

Exercise 1.11.

Read Section 4.2 of the Companion Notes. For the following statement, identify the assumptions (objects that the statement is making a claim about) and conclusion(s) (the claim(s) that the statement is making) and try and identify where they are used in the proof.

Lemma (Linear Combination Lemma).

Let $a$ and $b$ be integers with common divisor $d$ . Then, for any pair of integers $m$ and $n$ , the integer $ma+nb$ is divisible by $d$ .

Note that the expression $ma+nb$ above is called a linear combination of $a$ and $b$ , hence the name of the lemma.

Proof.

Suppose $a$ and $b$ are integers with common divisor $d$ , and let $m$ and $n$ be integers.

By the definition of a divisor, $\frac{a}{d}$ and $\frac{b}{d}$ are both integers. The product of two integers is an integer, and so $n\times\frac{a}{d}=\frac{na}{d}$ and $m\times\frac{b}{d}=\frac{bm}{d}$ are also integers. The sum of two integers is an integer, and so $\frac{na}{d}+\frac{mb}{d}=\frac{na+mb}{d}$ is also an integer. Hence, by the definition of a divisor, $d\mid(ma+nb)$ .

Negating statements

Exercise 1.12.

Read Section 3.2.1 of the Companion Notes. Try to find the negation of the following statements:

1.

All the peppers in the box are green.
2.

If you do your homework, you’ll get dessert.

Proof by Contradiction

Exercise 1.13.

Read Section 4.5 in the Companion Notes. Try to identify the key steps of a proof by contradiction in the following proof. If there are any steps in the proof that you are not entirely convinced by or find confusing, make a note of them to discuss in the Reading workshop.

Theorem.

The number $\sqrt{2}$ is not rational.

Proof.

For a contradiction, assume $\sqrt{2}$ is rational. Write $\sqrt{2}=\frac{a}{b}$ , where $a$ and $b$ are integers so that the fraction is in simplest terms (i.e. $a$ and $b$ have no common factors).

Squaring both sides of $\sqrt{2}=\frac{a}{b}$ tells us that $2b^{2}=a^{2}$ .

Hence $a^{2}$ is an even number, and so $a$ is even.

Let $a=2k$ for some integer $k$ . Then $2b^{2}=4k^{2}$ and so $b^{2}$ is even. So $b$ is even.

Now both $a$ and $b$ are even. This contradicts our assumption that $\sqrt{2}$ could be written in the form $\frac{a}{b}$ with the fraction in simplest terms. Hence this assumption must be false and so $\sqrt{2}$ cannot be rational.

1.2.2 B1 Reading Workshop Supplementary Material

Lemma (Bézout’s Lemma (Special Case)).

Let $a$ and $b$ be coprime integers. Then there exist integers $m$ and $n$ such that $ma+nb=1$ .

Definition (Prime).

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

Lemma (Euclid’s lemma).

Let $a$ and $b$ be integers, and $p$ be prime. If $p\mid ab$ then $p\mid a$ or $p\mid b$ .

PROOF: (The lines of this proof are numbered to aid your discussion.)

1.

Suppose $p\mid ab$ and $p\nmid a$ ; we shall show that $p$ must divide $b$ .
2.

Since $p$ is prime and $p\nmid a$ it follows that $\gcd(a,p)=1$ .
3.

Thus, by Bézout’s Lemma (Special Case), there are integers $m$ and $n$ such that

$ma+np=1.$
4.

Multiplying both sides by $b$ gives

$mab+npb=b.$
5.

But $p\mid ab$ and $p\mid npb$ , so $p$ divides the left-hand side of the equation.
6.

Therefore it must divide $b$ , the right-hand side.
7.

The same argument can be applied to prove that if $p\mid ab$ and $p\nmid b$ then $p\mid a$ .
8.

Therefore the proof is complete. $\square$

Theorem.

The number $\sqrt{2}$ is not rational.

PROOF: (The lines of this proof are numbered to aid your discussion.)

1.

For a contradiction, assume $\sqrt{2}$ is rational.
2.

Write $\sqrt{2}=\frac{a}{b}$ , where $a$ and $b$ are integers so that the fraction is in simplest terms (i.e. $a$ and $b$ have no common factors).
3.

Squaring both sides of $\sqrt{2}=\frac{a}{b}$ tells us that $2b^{2}=a^{2}$ .
4.

Hence $a^{2}$ is an even number, and so $a$ is even.
5.

Let $a=2k$ for some integer $k$ . Then $2b^{2}=4k^{2}$ and so $b^{2}$ is even. So $b$ is even.
6.

Now both $a$ and $b$ are even.
7.

This contradicts our assumption that $\sqrt{2}$ could be written in the form $\frac{a}{b}$ with the fraction in simplest terms.
8.

Hence this assumption must be false and so $\sqrt{2}$ cannot be rational. $\square$

Theorem (The Fundamental Theorem of Arithmetic).

Let $n>1$ be an integer. Then there is a list of positive primes $p_{1},p_{2},\ldots,p_{k}$ such that

n=p_{1}p_{2}\cdots p_{k}.

The primes $p_{1},p_{2},\ldots,p_{k}$ are unique up to reordering.

SUBPROOF A (The lines of this proof are numbered to aid your discussion.)

1.

First, we prove that $n$ can be written as a product of primes.
2.

For a contradiction, assume that $n>1$ cannot be written as a product of primes and is the smallest integer with this property.
3.

Because such an $n$ cannot be prime itself, it must have a positive non-prime divisor $d$ strictly greater than $1$ and less than $n$ .
4.

Thus $n=dk$ for some positive integers $d$ and $k$ , both strictly smaller than $n$ .
5.

Because $d$ and $k$ are smaller than $n$ , and because we assumed $n$ was the smallest integer that could not be written as a product of primes, it must be possible to write $d$ and $k$ as a product of primes.
6.

But then $n$ is the product of $d$ and $k$ , both of which are a product of primes.
7.

Hence $n$ must also be a product of primes.
8.

Contradiction; no such $n$ can exist.

1.2.3 Workshop tasks

Definition (Divisor).

Let $a$ and $d$ be integers, with $d\neq 0$ . We say that $d$ divides $a$ , and that $d$ is a divisor (or factor) of $a$ , if $\frac{a}{d}$ is an integer. We also say that $a$ is divisible by $d$ .

We shall write $d\mid a$ to mean $d$ divides $a$ , and $d\nmid a$ to mean that $d$ does not divide $a$ .

Task 1.14 (5 min).

(a)

List the divisors of $0$ .
(b)

List the divisors of $1$ .
(c)

Let $k$ be an integer that is not $0$ or $1$ . At least how many distinct divisors does $k$ have?

Direct Proof

Definition (Common divisor).

Let $a$ and $b$ be integers. If $d\mid a$ and $d\mid b$ then we say $d$ is a common divisor of $a$ and $b$ .

Definition (Greatest common divisor, $\gcd$ ).

Let $a$ and $b$ be integers, not both zero. The greatest common divisor of $a$ and $b$ , denoted by $\gcd(a,b)$ , is the largest common divisor of $a$ and $b$ .

Definition (Coprime).

Let $a$ and $b$ be integers. We say that $a$ and $b$ are coprime if $\gcd(a,b)=1$ .

Lemma (Bézout’s Lemma (Special Case)).

Let $a$ and $b$ be coprime integers. Then there exist integers $m$ and $n$ such that $ma+nb=1$ .

Definition (Prime).

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

Task 1.15 (15 min).

Read the statement and proof of Euclid’s Lemma and discuss the following:

1.

Identify the assumptions and conclusions of the statement. Where do they feature in the proof?
2.

Why can Bézout’s Lemma (Special Case) be used in this proof? Are all its assumptions satisfied?
3.

One of the results we’ve looked at in this workshop so far is hidden in this proof. What is it and where is it used?
4.

EXTENSION: Is this proof valid if $p$ is NOT prime? If not, where does the proof break down?
5.

EXTENSION: If prime $p$ divides $abc$ , can we guarantee that $p$ divides at least one of $a$ , $b$ or $c$ ?

Lemma (Euclid’s lemma).

Let $a$ and $b$ be integers, and $p$ be prime. If $p\mid ab$ then $p\mid a$ or $p\mid b$ .

Proof.

(The lines of this proof are numbered to aid your discussion.)

1.

Suppose $p\mid ab$ and $p\nmid a$ ; we shall show that $p$ must divide $b$ .
2.

Since $p$ is prime and $p\nmid a$ it follows that $\gcd(a,p)=1$ .
3.

Thus, by Bézout’s Lemma (Special Case), there are integers $m$ and $n$ such that

$ma+np=1.$
4.

Multiplying both sides by $b$ gives

$mab+npb=b.$
5.

But $p\mid ab$ and $p\mid npb$ , so $p$ divides the left-hand side of the equation.
6.

Therefore it must divide $b$ , the right-hand side.
7.

The same argument can be applied to prove that if $p\mid ab$ and $p\nmid b$ then $p\mid a$ .
8.

Therefore the proof is complete.

Proof by Contradiction

Task 1.16 (15 min).

In your group, compare your notes on the proof that $\sqrt{2}$ is not rational.

1.

Do you agree where the key steps of a proof by contradiction are present in this proof? Discuss any points of confusion with your group.
2.

Which steps in the argument would not work if we tried to adapt it to prove that $\sqrt{4}$ is not rational?
3.

EXTENSION: Adapt the proof to prove that $\sqrt{3}$ is not rational.

An extra line here

Theorem.

The number $\sqrt{2}$ is not rational.

Proof.

(The lines of this proof are numbered to aid your discussion.)

1.

For a contradiction, assume $\sqrt{2}$ is rational.
2.

Write $\sqrt{2}=\frac{a}{b}$ , where $a$ and $b$ are integers so that the fraction is in simplest terms (i.e. $a$ and $b$ have no common factors).
3.

Squaring both sides of $\sqrt{2}=\frac{a}{b}$ tells us that $2b^{2}=a^{2}$ .
4.

Hence $a^{2}$ is an even number, and so $a$ is even.
5.

Let $a=2k$ for some integer $k$ . Then $2b^{2}=4k^{2}$ and so $b^{2}$ is even. So $b$ is even.
6.

Now both $a$ and $b$ are even.
7.

This contradicts our assumption that $\sqrt{2}$ could be written in the form $\frac{a}{b}$ with the fraction in simplest terms.
8.

Hence this assumption must be false and so $\sqrt{2}$ cannot be rational.

Theorem (The Fundamental Theorem of Arithmetic).

Let $n>1$ be an integer. Then there is a list of positive primes $p_{1},p_{2},\ldots,p_{k}$ such that

n=p_{1}p_{2}\cdots p_{k}.

The primes $p_{1},p_{2},\ldots,p_{k}$ are unique up to reordering.

Task 1.17 (10 min).

Negations

1.

Share your negations from the preparatory tasks with your group. Do you all agree? Which are correct?
2.

If $n>1$ is an integer and $p_{1},p_{2},\ldots,p_{k}$ are prime numbers such that

$n=p_{1}p_{2}\cdots p_{k},$

we call this expression for $n$ a prime decomposition or prime factorisation of $n$ .

What is the negation of the statement “Every integer $n>1$ has a unique prime decomposition.”?
3.

EXTENSION: How would you set up a proof by contradiction for the Fundamental Theorem of Arithmetic?

Task 1.18 (15 min).

The Fundamental Theorem of Arithmetic is an important result about the role of primes. This proof contains two subproofs by contradiction - one for existence and one for uniqueness. Read subproof $A$ and discuss the following with your group:

1.

Identify the key components of a proof by contradiction in this subproof.
2.

In line 3, why can $n$ not be prime itself?
3.

Where is the definition of a divisor used in the proof? Why does it look different?
4.

In line 3, if $n$ is not prime, why must it have a positive non-prime divisor $d$ strictly between 1 and $n$ ?
5.

EXTENSION: Why can we assume there exists a smallest integer $n>1$ that cannot be written as a product of primes?

Theorem (The Fundamental Theorem of Arithmetic).

Let $n>1$ be an integer. Then there is a list of positive primes $p_{1},p_{2},\ldots,p_{k}$ such that

n=p_{1}p_{2}\cdots p_{k}.

The primes $p_{1},p_{2},\ldots,p_{k}$ are unique up to reordering.

SUBPROOF A

1.

First, we prove that $n$ can be written as a product of primes.
2.

For a contradiction, assume that $n>1$ cannot be written as a product of primes and is the smallest integer with this property.
3.

Because such an $n$ cannot be prime itself, it must have a positive non-prime divisor $d$ strictly greater than $1$ and less than $n$ .
4.

Thus $n=dk$ for some positive integers $d$ and $k$ , both strictly smaller than $n$ .
5.

Because $d$ and $k$ are smaller than $n$ , and because we assumed $n$ was the smallest integer that could not be written as a product of primes, it must be possible to write $d$ and $k$ as a product of primes.
6.

But then $n$ is the product of $d$ and $k$ , both of which are a product of primes.
7.

Hence $n$ must also be a product of primes.
8.

Contradiction; no such $n$ can exist. $\square$

1.2 Workshop 2 (Reading)

1.2.1 Preparatory exercises (1 hour)

Divisors

Definition (Divisor).

Exercise 1.8.

Definition (Common divisor).

Definition (Greatest common divisor, gcd\gcd).

Exercise 1.9.

Definition (Coprime).

Exercise 1.10.

Direct Proof

Exercise 1.11.

Lemma (Linear Combination Lemma).

Proof.

Negating statements

Exercise 1.12.

Proof by Contradiction

Exercise 1.13.

Theorem.

Proof.

1.2.2 B1 Reading Workshop Supplementary Material

Lemma (Bézout’s Lemma (Special Case)).

Definition (Prime).

Lemma (Euclid’s lemma).

Theorem.

Theorem (The Fundamental Theorem of Arithmetic).

1.2.3 Workshop tasks

Definition (Divisor).

Task 1.14 (5 min).

Direct Proof

Definition (Common divisor).

Definition (Greatest common divisor, gcd\gcd).

Definition (Coprime).

Lemma (Bézout’s Lemma (Special Case)).

Definition (Prime).

Task 1.15 (15 min).

Lemma (Euclid’s lemma).

Proof.

Proof by Contradiction

Task 1.16 (15 min).

Theorem.

Proof.

Theorem (The Fundamental Theorem of Arithmetic).

Task 1.17 (10 min).

Task 1.18 (15 min).

Theorem (The Fundamental Theorem of Arithmetic).

Definition (Greatest common divisor, $\gcd$ ).

Definition (Greatest common divisor, $\gcd$ ).