1. There are infinitely many prime numbers.

.. ~ Mathsnotes ~ Leave a comment

In this post I will be going through the definitions, proposition and methods of proof required to arrive at the result in the title. I want this to be a motivating example for the study of number theory, before I delve deeper into the topic in future posts. Number Theory is integral to computer science and cryptography, fields that grow in importance year on year.

Mathematics is the Queen of the Sciences and Number Theory is the Queen of Mathematics.
Carl Friedrich Gauss

Just to lay out some of the notation I will be using. $\mathbb{Z}$ denotes the set of integers (whole numbers), $\mathbb{N}$ denotes the set of natural numbers (counting numbers). $a\in \mathbb{Z}$ means that a belongs to the set of integers, i.e a is an integer (whole number).

I also want to discuss what “if and only if” means as I will be using this phrase frequently. Consider the phrase “Omar eats if and only if he is hungry” this means that if “Omar eats” then “he is hungry”, and if “he is hungry” then “Omar eats”. Consider another phrase “Omar didnt get enough sleep implies that he is tired” this means that if “Omar didnt get enough sleep” then “he is tired”, but this does NOT mean that if “he is tired” then “Omar didnt get enough sleep”.

Definition 1: Divisor

Given $a,b\in \mathbb{Z}$ , we say that ‘a divides b’ or ‘a is a divisor of b’ or ‘b is a multiple of a’ or ‘a is a factor of b’ if and only if there exists $c\in \mathbb{Z}$ such that $b=ac$ . (if $a\neq 0$ this means $\frac{b}{a}\in \mathbb{Z}$ ).

Notation: ‘a divides b’ is written as a|b.

Proposition 1.1: If a|b and b|c then a|c.

Proof

If a|b then $\frac{b}{a}\in \mathbb{Z}$ which using the definition above we can write as $\frac{b}{a}=k$ where $k\in \mathbb{Z}$ from which we obtain b=ak. we have that b|c and so we can write this as ak|c. using the definition again we can say that $\frac{c}{ak}=d\in \mathbb{Z}$ which implies that $\frac{c}{a}=kd\in \mathbb{Z}$ and we get a|c as required. This is known as the Transitivity property of divisibility.

QED

Proposition 1.2: If a|b and a|c then $a|(xb \pm yc)$

Proof

Since a|b and a|c there exists $m,n\in \mathbb{Z}$ such that b=an and c=am. For any $x,y\in \mathbb{Z}$ we have $xb \pm yc = xan\pm yam = a(xn\pm ym)$ so we have found an integer $xn \pm ym$ such that $xb\pm yc=aq$ . Thus $a|(xb\pm yc)$ as required. This is known as the linearity property of divisibility.

QED

Definition 1.2: Prime and Composite Numbers

A number $p\in \mathbb{N}$ with $p>1$ is prime if and only if its only divisors are 1 and p.
A number $n\in \mathbb{N}$ with $n>1$ is composite if and only if it is not prime. (i.e n=ab for some $a,b \in \mathbb{N}$ with $a,b>1$ )

Note: n=1 is neither prime nor composite.

Before we arrive at our next result, I will breifly explain the method of proof we will employ in order to prove the validity of our result.

Proof By Induction is a method of proof used to prove statements that hold for the natural numbers ( $\mathbb{N}\in \{1,2,3,4,...\}$ ) and consists of 2 steps; The base case and the inductive step. The base case is the step in which we prove the statement is true for a value of n (usually n=1) . The inductive step is the step in which we link this base case to the rest of the natural numbers, we prove that if n=k is true then n=k+1, this forms a “ladder” constantly building and climbing infinitely up the natural numbers, proving the statement for all natural numbers.

The type of induction we will be using is called strong induction, which is closely related to the method i just described. The difference lies in the inductive step where instead of supposing that n=k is true we suppose it is true for $n\in \{1,2,3,...,k\}$ and use this to prove that it is true for n=k+1.

Proposition 1.3: If $n\in \mathbb{N}$ with $n>1$ , then n has a prime factor.

Proof:

Consider the trivial case of when n is prime, then n is a prime factor of n.

It now remains to show that the statement holds for composite numbers. We employ strong induction i.e we want to show that if for all $m\in \mathbb{N}$ with $1<m<n$ , m has a prime factor (this statement is known as the inductive hypothesis) then n has a prime factor. The base case is satisfied by showing it was true for the primes i.e we have for n=4, and 1<m<4 that m is prime and the statement holds, this forms the beginning of our ladder to extend to the rest of the natural numbers. If n is composite then n=ab where $a,b\in \mathbb{N}$ with $a,b>1$ (using our definition of composite). Clearly $1<a<n$ and by the inductive hypothesis we have that a has a prime factor i.e there exists a prime p with p|a. So we have that p|a and a|n which by the transitivity property of divison implies that p|n and we have shown that n has a prime divisor.

QED

We will use another method of proof to prove our final result. Proof by contradiction essentially works by showing that assuming the statement is false leads to a contradiciton, proving the falsehood of assuming the statement was false and therefore proving the statement is true.

Theorem 1.1: There are infinitely many prime numbers.

Proof:

Let us assume for contradiciton that there are finitely many prime numbers, i.e assuming that the set $S=\{p_{1},p_{2},...,p{n}\}$ is a complete list of primes. Consider $N=1+p_{1}\times p_{2}\times ... \times p_{n}$ clearly by construction we have that N>1. By proposition 2, N has a prime factor p, p|N. However, every prime is supposedly one of $p_{1},p_{2},...,p{n}$ , so $p=p_{i}$ for some $i\in \{1,2,...,n\}$ . Therefore $p|(p_{1}\times p_{2}\times ... \times p_{n})$ , so p|(N-1). Since we have that p|N and p|(N-1) by the linearity of divisibility (proposition 2) we have p|1 since 1=N-(N-1) which is a contradiction.

QED

2. The Greatest Common Divisor

.. ~ Mathsnotes ~ Leave a comment

We have seen what it means for an integer to divide another. In this post we will explore division further and delve into the idea of the greatest common divisor, seeing how this gives us information on the solubility of linear equations in the integers. I will begin by formally defining some terms formally.

Definition 2.1: Sets, Elements and the Empty Set

A Set is a collection of objects. The objects that make up a set are called the Elements of the set. The Empty Set denoted $\emptyset$ is the unique set with no elements.

Example 2.1:

$\mathbb{Z}$ is the set of integers, $1729\in \mathbb{Z}$ means that 1729 is an element of the set of integers.
$\mathbb{N}$ is the set of natural numbers $1999\in \mathbb{N}$ .

Definition 2.2: Subset

Let A and B be sets. A is a Subset of B if every element of A is an element of B. This is denoted by A $\subseteq$ B.

Proposition 2.1: a|b and b|a implies |a|=|b|, i.e $a=\pm b$

The proof of this proposition is omitted for now! This requires ring theory as we need the fact that $\pm 1$ are the only units of the ring of integers. I will do some posts on rings in the future and will return to this proof then.

The Well-Ordering Principle is an axiom that states that every non-empty subset of $\mathbb{N}\cup \{0\}$ contains a least element, it is a property of the integers which is pretty intuitive.

Theorem 2.1: Given $a\in \mathbb{Z}$ and $b\in \mathbb{N}$ , there exists unique integers q and r satisfying $a=bq+r$ and $0\leq r<b$ . q is known as the quotient and r is known as the remainder.

Proof:

We will begin by proving the existence of such a pair of integers, and then we will go on to establish their uniqueness. Let us begin by defining the set $S:=\{a-xb: x\in \mathbb{Z}$ and $a-xb\geq 0\}$ . S is non-empty because if $a\geq 0$ by choosing m=0 we get $a-mb=a\geq 0$ which is indeed an element of S, and if $a<0$ by choosing m=a, we get $a-mb=a-ab=(-a)(b-1)\geq 0$ since $-a>0$ and $b>0$ . We have now shown that S is a non empty set (it is easy to see that it is a non empty subset of $\mathbb{N}\cup \{0\}$ ) which means we can now apply the well-ordering principle! So we have that S contains a least element, lets call it r. we have that $r\geq 0$ because $r\in S$ also by our construction of the set S we see that $r=a-qb$ so $a=qb+r$ . All that remains for us to show (to establish existence) is that $r<b$ (we already know that $r \geq 0$ because $r\in S$ ). We assume for contradiction that $r\geq b$ and let $r_{1}=r-b\geq 0$ , then $a=qb+r=qb + (r_{1}+b) = (q+1)b + r_{1}$ and so $a-(q+1)b=r_{1}\in S$ , $r_{1}=a-(q+1)r<a-qb=r$ so we have $r_{1}<r$ which is a contradiction because r is the least element of S.

We now prove that the pair q,r such that a=qb+r with $0\leq r<b$ is unique. Assume that there is another pair of integers q’ and r’ such that a=q’b+r’ with $0\leq r'<b$ . Then we have a=qb+r=q’b+r’ from which we obtain (q-q’)b=(r-r’). If q=q’ then we must have r=r’ and hence we have shown uniqueness, so it suffices for us to show that q=q’. So suppose for a contradiction that $q \neq q'$ , Then $b\leq|q-q'||b|$ because $|q-q'|\geq 1$ . We have that $b\leq|q-q'||b|=|r'-r|$ but recall that $0\leq r<b$ and $0\leq r'<b$ so $|r'-r|<b$ which means $b\leq|r'-r|<b$ which is a contradiction because |r-r’|cannot be greater than or equal to and less than b simultaneously.

QED

The theorem above is essentially saying that every integer, a, can be expressed in terms of a quotient and a remainder. This is the essence of division among the integers.

Theorem 2.2: Let $a,b\in \mathbb{Z}$ . Then there exists a unique $d\in \mathbb{N}\cup \{0\}$ and (non-unique) $x,y\in \mathbb{Z}$ such that;

d|a and d|b
if $e\in \mathbb{Z}$ , e|a and e|b then e|d.
d=ax+by (Bezout’s Identity)

Proof:

If a=b=0, then it is easy to check that we have d=0. So suppose that a and b are not both zero i.e requiring that $a^{2}+b^{2}>0$ . Let $S:=\{am+bn:m,n\in \mathbb{Z}$ and $am+bn>0\}$ since $a^{2}+b^{2}>0$ S is a non-empty subset of $\mathbb{N}\cup \{0\}$ . So we can now use the well ordering principle to establish a least element say, d>0. $d\in S$ so we can write $d=ax+by$ for some $x,y\in \mathbb{Z}$ . Also by theorem 2.1 we can write a=qd+r for some $q,r \in \mathbb{Z}$ with $0\leq r<d$ . We want to show that d|a so assume for contradiction that $r \neq 0$ , then $0<r=a-qd=a-q(ax+by)=(1-qx)a-qby$ therefore $r\in S$ . But r<d contradicting the fact d is the least element of S, so we must have that r=0 and hence d|a. The same argument shows that d|b.

Suppose that $e\in \mathbb{Z}$ , e|a and e|b. Then by the linearity of division (proposition 1.2) e divides any linear combination of a and b, recall that $d=ax+by$ for some $x,y\in \mathbb{Z}$ (i.e d is a linear combination of a and b) and so e|d.

It remains to show that d is unique, so suppose that there exists $f\in \mathbb{N}\cup \{0\}$ that also satisfies 1. and 2.. Then f|d and d|f and so $d=\pm f$ by proposition 2.1. But $d,f\geq 0$ so we have d=0, thus d is unique.

QED

Definition 2.3: Greatest Common Divisor

Let $a,b\in \mathbb{Z}$ , then the d given in theorem 2.2 is called the greatest common divisor of a and b, written as gcd(a,b). This is sometimes referred to as the highest common factor of a and b, hcf(a,b).

Bezout’s Identity is part 3 of theorem 2.2, here it is stated in terms of definition 2.3. Given $a,b\in \mathbb{Z}$ there exist (non-unique) $x,y\in \mathbb{Z}$ such that gcd(a,b)=ax+by.

Definition 2.4: Coprime

Let $a,b\in \mathbb{Z}$ , we say that a and b are coprime or relatively prime if gcd(a,b)=1.

Theorem 2.3: (Euclid’s Lemma) Let $a,b,c\in \mathbb{Z}$ . If a|bc and gcd(a,b)=1 then a|c.

Proof:

Suppose that a|bc and gcd(a,b)=1. By Bezout’s Identity there exist $x,y\in \mathbb{Z}$ such that 1=ax+by. Hence c=acx+bcy. But a|acx and a|bcy, so by the linearity of divisibility (proposition 1.2) a|(acx+bcy) which implies a|c(ax+by) i.e a|c because ax+by=1.

QED

The following theorem will show under what conditions some linear equations in the integers are soluble (i.e have a solution).

Theorem 2.4: Let $a,b,c\in \mathbb{Z}$ . The equation $ax+by=c$ is soluble with $x,y\in \mathbb{Z}$ if and only if gcd(a,b)|c.

Proof:

Let d=gcd(a,b). Then by the definition of the greatest common divisor d|a and d|b so if there exists $x,y \in \mathbb{Z}$ such that c=ax+by (i.e there exists a solution to the equation) then d|c by the linearity of divisibility (porposition 1.2). So suppose that the equation is soluble i.e that d|c. Then c=qd for some $q\in\mathbb{Z}$ . By Bezouts Identity there exists $x',y'\in\mathbb{Z}$ such that d=ax’+by’. Therefore we can write c=qd=aqx’+bqy’ and so x=qx’ and y=qy’ gives a suitable solution.

QED

3. Extended Euclidean Algorithm

.. ~ Mathsnotes ~ Leave a comment

We have seen what the greatest common divisor is and one of its uses, namely it allows us observe under what conditions linear equations are soluble in the integers. In this post we will see one way to compute the greatest common divsior, the Extended Euclidean Algorithm. Before we get to the Extended Euclidean Algorithm we will start with the standard Euclidean Algorithm. It is named after Euclid a greek mathematician who is often called the “father of geometry” who described this algorithm as early as 300 BC. The essence of the Euclidean Algorithm is to apply Theorem 2.1 over and over until we get a remainder of zero, then we can extract the greatest common divisor.

Notation: $x \nmid y$ means x does not divide y.

Definition 3.1: Linear Combination

A linear combination of integers $x,y \in \mathbb{Z}$ is any expression of the form $ax+by$ where a and b are constants. (for our purposes a and b will always be integers).

This next theorem may look intimidating but once we go through an example and put numbers to the letters it will become clearer.

Theorem 3.1: (The Euclidean Algorithm) Let $a,b\in \mathbb{N}$ with $a\geq b>0$ and $b \nmid a$ . Let $r_{0}=0,r_{1}=b$ and apply Theorem 2.1 repeatedly to obtain a sequence of remainders $r_{2},r_{3},...,r_{n},r_{n+1}$ defined as follows:

$r_{0}=r_{1}q_{1} + r_{2}$ where $0<r_{2}<r_{1}$

$r_{1} =r_{2}q_{2}+r_{3}$ where $0<r_{3}<r_{2}$

…

$r_{n-2}=r_{n-1}q_{n-1}+r_{n}$ where $0<r_{n}<r_{n-1}$

$r_{n-1}=r_{n}q_{n}+r_{n+1}$ where $r_{n+1}=0$

Then $gcd(a,b)=r_{n}$

Proof:

Consider the sequence of remainders, the $r_{i}$ are strictly decreasing non-negative integers and so at some stage $r_{n+1}=0$ . We have that for any $x,y,z\in \mathbb{Z}$ we have gcd(x,y)=gcd(x+zy,y). So in terms of our remainders this is $gcd(r_{i},r_{i+1})=gcd(r_{i+1}q_{i+1}+r_{i+2},r_{i+1})=gcd(r_{i+2},r_{i+1})=gcd(r_{i+1}),gcd(r_{i+2})$ . Applying this over and over yields; $gcd(a,b)=gcd(r_{0},r_{1})=gcd(r_{1},r_{2})=gcd(r_{2},r_{3})=...=gcd(r_{n-1},r_{n})=r_{n}.$ where the last equality is because $r_{n}|r_{n-1}$ .

QED

Remember Bezout’s Identity from the last post? well we can find $x,y \in \mathbb{Z}$ such that $gcd(a,b)=ax+by$ (i.e. we can express the gcd of a and b as a linear combination of a and b) by ‘working backwards’. We can do this because each remainder can be expressed as a linear combination of the two previous remainders, so can the remainders before those and eventually it can be expressed in terms of a and b as we will see in the following example;

Example 3.1: Calculate the Greatest Common divisor of 720 and 333 and express it as a linear combination of 720 and 333.

$720 = 333 \times 2 + 54$

$333=54 \times 6 +9$

$54 = 9 \times 6 + 0$

therefore gcd(720,333)=9. (Try and compare this example to the previous theorem and see where the numbers fit the $r_{i}'s$ ). Now lets work backwards to express 9 as a linear combination of 720 and 333.

$9 =333 \times 1 - 54 \times 6$

$54 = 720 \times 1 - 333 \times 2$ and so $9 = 333 \times 1 - (720 \times 1 -333 \times 2) \times 6$

collecting like terms yields $9= 720 \times (-6) +333 \times 13$ .

So we have now seen how and why the Euclidean Algorithm works, now for the Extended Euclidean Algorithm. The Extended Euclidean Algorithm essentially combines the ‘working backwards’ step we did in the previous example while we compute the gcd, and so it computes the gcd as a linear combination of the two integers.

The sequences of quotients, $q_{i}$ , and remainders, $r_{i}$ , defined in the Euclidean Algorithm, we now define the sequence of integers $x_{i}, y_{i}$ , such that $r_{i} = ax_{i} + by_{i}$ . Remember that we define $r_{n}$ to be the last non zero remainder and that $r_{n}=gcd(a,b)$ . Therefore we have $gcd(a,b)=r_{n}=ax_{n}+by_{n}$ and so we set $(x,y)=(x_{n},y_{n}$ . Let us now explicitly define $x_{i}$ and $y_{i}$ . So from Theorem 3.1 $r_{0}=a$ and $r_{1}=b$ and so clearly $r_{0}=a\times 1 +b\times 0$ and $r_{1}=a\times 0 +b\times 1$ and so we set $(x_{0},y_{0}):= (1,0)$ and $(x_{1},y_{1}):=(0,1)$ . Now for $i\geq 2$ we recursively define by

$(x_{i},y_{i}):=(x_{i-2},y_{i-2})-q_{i-1}(x_{i-1},y_{i-1})$

which will become clear with an example.

Example 3.2: Let calculate gcd(720,333) again but this time using the Extended Euclidean Algorithm;

and so $gcd(720,333)=9=720\times (-6) + 333\times 13$

r_{i-2} — and so $gcd(720,333)=9=720\times (-6) + 333\times 13$

Compare this with example 3.1 to help you understand where everything is coming from. A useful exercise is to compute the gcd of any two integers and then check your answer at this website https://planetcalc.com/3298/ .

Bibliography

.. ~ Mathsnotes ~ Leave a comment

MTH3004 – Number Theory – a course given at the University of Exeter by Dr Henri Johnston 2019
Gareth A. Jones and J. Mary Jones, Elementary Number Theory, Springer-Verlag, London, 1998