1. Introduction to the Limits of Functions

.. ~ Mathsnotes ~ Leave a comment

The theory of limits is central to calculus, and so we must discuss limits of functions before we delve into differential and integral calculus. In order to discuss limits of functions we must define what a function is;

Definition 1.1: Function

Suppose we have two sets D and C. A rule that assigns to each element of D a unique element in C is called a function from D to C. The set D is called the Domain and C is called the Codomain. If $x\in D$ and $y\in C$ are related by the function $f$ we write $y=f(x)$ .

We say that x is the Independent variable and y is the dependent variable because y depends on the value of x. If $R= f(D)$ we say that R is the Range or Image of $f$ .

Limits of functions are used to describe how the function behaves when the independent variable gets close to a particular value. So taking the limit of a function say $f(x)$ as $x$ tends to some value $a$ , is essentially making a prediction for what $f(a)$ will be based on how the function behaves near $a$ . Sometimes the limits of functions do not exist for certain values and we will see why in future posts. Let’s informally look at a couple of examples to help us understand what a limit is;

Note: The value of a function $f(x)$ need not be defined at a point $a$ for $f(x)$ to have a limit there! Sometimes the limit of a function at a point is not equal to the function evaluated at that point, i.e $\lim_{x\to a} f(x)$ is not always equal to $f(a)$ .

Example 1: Consider the function $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x)=x^{2}+1$ , Find $\lim_{x\to 2} f(x)$ .

By compiling a table of values for $x$ and $f(x)$ we can see how $f(x)$ behaves when $x$ is near 2.

As you can see from the table as x approaches 2 (from either side), f(x) approaches 5, and so we have $\lim_{x\to 2} f(x)$ . This is an example of when the limit at the point is equal to the value of the function at that point.

Example 2: Consider the function $g: \mathbb{R} \to \mathbb{R}$ defined by

Let’s find $\lim_{x\to 0} g(x)$ . We can do the same thing as in the last example but let’s establish the limit of this function graphically.

As you can see from the graph of $y=g(x)$ above, as indicated by the blue arrows, $g(x)$ approaches 3 as x approaches zero (from either side). Clearly $lim_{x\to 0} g(x)=3$ , this however, is NOT equal to the value of the function at x=0 which is $g(0)=0$ (indicated by the green dot on the graph).

The following definition is incredibly important.

Definition 1.2: Limit

Suppose that $f(x)$ is a real function (a function whose values are real numbers). If for any $\varepsilon >0$ there exists a $\delta >0$ such that for any $x$ with $|x-a|<\delta$ we have $|f(x)-L|<\varepsilon$ then $L$ is the limit of $f(x)$ as $x$ tends towards $a$ , denoted $\lim_{x\to a} f(x)=L$ .

This definition is essentially saying if $\lim_{x\to a} f(x)=L$ , then as x gets arbitrarily close to a, f(x) is also getting close to L. Our $\delta$ and $\epsilon$ is basically our mathematical way of saying how close x is to a and how close f(x) is to L respectively.

The following theorem is very important to computing the limits of functions, i will prove the first property and will leave the rest as an exercise to the reader. Feel free to send me your proofs via the contact page if you would like me to check them.

Theorem 1.1: Laws of Limits

Proof of 1.:

$lim_{x\to a} f(x)$ and $lim_{x\to a} g(x)$ both exist and so we let $lim_{x\to a} f(x)=L_{1}$ and $lim_{x\to a} g(x)=L_{2}$ . By definition 1.2 we have that for any $\varepsilon >0$ there exists a $\delta_{1} >0$ such that for any $x$ with $|x-a|<\delta_{1}$ we have $|f(x)-L_{1}|<\frac{\varepsilon}{2}$ and there exists a $\delta_{2} >0$ such that for any $x$ with $|x-a|<\delta_{2}$ we have $|g(x)-L_{2}|<\frac{\varepsilon}{2}$ .

We let $\delta = min\{\delta_{1},\delta_{2}\}$ and so $\delta$ is sufficiently small so that they both satisfy the conditions set by the limits of f(x) and g(x). Therefore

$|f(x)-L_{1}|+|g(x)-L_{2}|\geq |(f(x)-L_{1})+(g(x)-L_{2}|=|f(x)+g(x) - (L_{1}+L_{2})|$ by the triangle inequality. Now we have $|f(x)-L_{1}|+|g(x)-L_{2}|< \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon$

and so we have $|f(x)+g(x) - (L_{1}+L_{2})|< \varepsilon$ which is precisely by definition 1.2 $lim_{x\to a} (f(x)+g(x))=lim_{x\to a} f(x)+lim_{x\to a} g(x)$ .

QED

To rigourosly show that the limit of a function is a certain value we must use definition 1.2 and establish a relationship between $\delta$ and $\varepsilon$ .

1. Groups

.. ~ Mathsnotes ~ Leave a comment

Groups are algebraic objects, and it is the study of these objects that forms a central part of abstract algebra, Group Theory. Before we get into our definition of a group, I will first introduce a few definitions that we will use to ultimately define a group.

Before we begin, you will need to remember that the symbol; $\forall$ means “for all elements”, $\exists$ means “there exists an element”, $\in$ means “in the set” and $\mathbb{Z}$ denotes the set of integers (whole numbers).

Definition 1.1: Sets, Elements, Non-Empty 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. A set is Non-Empty if it has one or more elements. The Empty Set denoted $\emptyset$ is the unique set with no elements.

Example 1.1: $X=\{1,2,3,4,5\}$ is a set and 1, 2, 3, 4 and 5 are its elements.

Definition 1.2: Cardinality

The Cardinality or size of a finite set A is the number of elements in the set A, denoted |a|. (we will look at the cardinality of infinite sets such as the Integers in future posts).

Example 1.2: For $X=\{1,2,3,4,5\}$ we have |X|=5, i.e. the set X has 5 elements.

Definition 1.3: 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.

Example 1.3: The set $Y=\{2,4\}$ is a subset of $X=\{1,2,3,4,5\}$ .

Definition 1.4: Composition Law

A Composition law (or Binary Function) on a set A is a rule $(\star)$ assigning to each $x\in A$ and $y\in A$ an element $z\in A$ such that $z=x\star y$ . We say that the set is closed

Example 1.4: Addition, +, on the set of all Integers, $\mathbb{Z}$ , is a compositon law. 1+2=3, we have assigned z=3 to x=1 and y=2.

Definition 1.5: Associative

A composition law $(\star)$ on a set A is associative if $(a \star b) \star c = a \star (b \star c), \forall a,b,c\in A$

Example 1.5: Addition on the set of all integers is Associative. e.g. (1+2)+3=3+3=6=1+5=1+(2+3)

We can write this more generally as follows: $\forall a,b,c \in \mathbb{Z}$ we have $(a+b)+c=a+(b+c)$ .

Definition 1.6: Commutative

A composition law $(\star)$ on a set A is commutative if $x\star y=y \star x, \forall x,y\in A$ .

Example 1.6: Addition on the Integers is Commutative. e.g 1+2=3=2+1.

More generally; $\forall a,b \in \mathbb{Z}$ we have $a+b=b+a$ .

Definition 1.7: Group

A pair $(G,\star)$ , where G is a non-empty set and $(\star)$ is a composition law, is a group if:

( $\star$ ) is associative: $a\star (b\star c)=(a\star b)\star c, \forall a,b,c \in \mathbb{Z}$ .
( $\star$ ) admits a neutral element: $\exists e_{G}\in G$ such that $e_{G}\star a=a\star e_{G}=a, \forall a\in G$
Every element of G has an inverse element in G: $\forall a\in G, \exists a^{-1}$ such that $a\star a^{-1}=a^{-1}\star a=e_{G}$

Example 1.7: The Integers, $\mathbb{Z}$ , endowed with addition, +, admits a neutral element, namely 0. e.g. 1+0=0+1=1.

More generally; $\forall a\in \mathbb{Z}, a+0=0+a=a$ .

Example 1.8: Every element of the Integers has an inverse element in the Integers with respect to the composition law of addition. e.g. 4+(-4)=(-4)+4=0.

More generally; $\forall a\in \mathbb{Z}, \exists (-a)$ such that $a+(-a)=0$ .

Now if we take a step back and look at examples 1.4, 1.5, 1.6, 1.7 and 1.8 all together we can see that the Integers endowed with Addition forms a group, which we denote by $(\mathbb{Z},+)$ .

Definition 1.8: Abelian

A Group is Abelian if its composition law is commutative.

Indeed the Integers endowed with Addition forms an Abelian Group.

Properties: Group

The neutral element, $e$ , is unique.
The inverse of an element is unique.
$(a^{-1})^{-1}=a$ .
$(ab)^{-1}=b^{-1}a^{-1}$ .
Cancellation laws: $au=av \Rightarrow u=v$ and $ub=vb \Rightarrow u=v$ .
$a^{n}a^{m}=a^{n+m}$ and $(a^{n})^{m}=a^{nm}$ .

For any element a of a group we can form a subgroup $<a>=\{a^{n} : n\in \mathbb{Z} \}$ for all integer powers of a.

Definition 1.9: Order of a Group

The Order of a group G is the cardinality of the set, denoted |G|.

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/ .

2. Dihedral Groups and Subgroups

.. ~ Mathsnotes ~ Leave a comment

I will now introduce a family of groups related to the symmetries of polygons, namely Dihedral Groups. We will focus on the Dihedral group related to the symmetries of a square. Consider all the actions you can do to a square to put it back on its self. We can reflect the square along one of its axes of symmetry which we will denote by $S_{x}$ where $x\in\{e,v,d,h\}$ is the axis of symmetry as shown in the following diagram;

We can also rotate the square by multiples of 90 degrees. We let r denote a 90 degree clockwise rotation, $r^{2}$ denotes 2 of these rotations (i.e a 180 degree rotation) and $r^{3}$ denotes a 270 degree clockwise rotation (or equivalently a 90 degree anticlockwise rotation). Putting all of these elements together with the identity element (the action of nothing on the square) with the commutative binary operation of composition (applying the first one and then the second) forms the dihedral group denoted by $D_{8}=\{e, r, r^{2}, r^{3}, s_{h}, s_{v}, s_{d}, s_{e}\}$ , in the following diagram we allocate each corner a colour so that we can see how it moves with each of the elements. The dihedral groups are denoted by $D_{2n}$ where n is the number of sides of the polygon the group is related to the symmetries of.

Figure 2: Visual representation of the Dihedral Group $D_{8}$

Figure 2: Visual representation of the Dihedral Group $D_{8}$

We only go up to $r^{3}$ because $r^{4}=e$ . Take a second to convince yourself that it is closed under the composition law (composing two elements gives another element of the group), especially with respect to the reflections in the axes of symmetry.

Definition 2.1: Order of an element

Let G be a group and $a \in G$ , the order of a is $ord(a)=min\{n\geq 1;a^{n}=e_{G}\}$ if there exists $n \geq 1$ with $a^{n}=e_{G}$ . Otherwise $ord(a)=\infty$ .

Here $ord(a)=min\{n\geq 1;a^{n}=e_{G}\}$ means the smallest number that is greater than or equal to 1 such that $a^{n}=e_{G}$ .

In terms of $D_{8}$ the order of an element is more informally the number of times you can compose the element with itself to get the original square i.e. the identity element e.

In any group, the identity is the unique element of order 1.

Example 2.1: Let us examine the elements of $D_{8}=\{e, r, r^{2}, r^{3}, s_{h}, s_{v}, s_{d}, s_{e}\}$ , take a second to convince yourself of these result;

$ord(e)=1$
$ord(r)=4$
$ord(r^{2})=2$
$ord(r^{3})=4$
$ord(s_{x})=2, \forall x\in\{h,v,d,e\}$

Definition 2.3: Subgroup

A subset H of a group G is a subgroup if:

H is closed under the composition law of G, $\star$ , $x\star y\in H, \forall x,y\in H$ .
The identity element of G is in H, $e_{G}\in H$.
Every element of H has an inverse element of H, $x^{-1}\in H, \forall x\in H$ .

Definition 2.2: Cyclic

A group $(G,\star)$ is a Cyclic if there exists an element a of G such that $G=<a> =\{a^{n}: n \in \mathbb{Z}\}$ where $n \in \mathbb{Z}$ . We say that “a generates G” or that a is “a generator of G”.

If $(G,\star)$ is cyclic and $ord(a)$ is finite then $|G|=ord(a)$ , in otherwords the order of a cyclic group is the order of the element that generates it.

It is left as an exercise for the reader to check that $<r>=\{e,r,r^{2},r^{3}\}$ is a cyclic subgroup of $D_{8}$ . A great way to visualise <r> is by isolating a side of the rubiks cube.

2. Rates of Change (Differentiation from First Principles)

.. ~ Mathsnotes ~ Leave a comment

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

Bibliography

.. ~ Mathsnotes ~ Leave a comment

MTH2002 – Algebra – a course given at the University of Exeter by Prof Mohammed Saidi 2018

$x$	1.85	1.9	1.99	1.999	1.9999	2	2.0001	2.001	2.01	2.1	2.15
$f(x)$	4.4225	4.6	4.9601	4.9960	4.9996	5	5.0004	5.0040	5.0401	5.41	5.6225