Link back to Home page

HTML version

1. Introduction to Proofs and Logic

Definition A statement (or proposition) is an expression that can be assigned the value of true or false

Anything that’s a question is not a statement.
In the example below, it’s a statement as the variable is “used up”. We really need to specify what’s happening to the variable for it to be a statement.

Definition A predicate is a ‘statement’ whose truth is dependent on one or more variables

• For a predicate, the variable is not “used up”

Definition A variable is a placeholder which gives a name to some entity that we want to consider

We can turn a predicate into a statement by specifying the set of values it applies to. Consider the example below:
This is a predicate unless we specify $\mathrm{\forall }n,\in \mathbb{Z}$

Definition A set is a collection of elements which can be any type of mathematical objects

Set notation

The notation $x\in X$ means that $x$ is an element of the set $X$.
Eg: $n\in Z$ means $n$ is an element of the set of integers

Building a subset:
If $P(x)$ means $x$ is even, then this subset below is just the set of even number

Axiom If all $x\in A$ are also in $B$ and all $x\in B$ are also in $A$ then $A$ and $B$ are the same set.

• Proper subset ($\subset$) - Every element of $A$ is also in $B$ but not equal to $B$
• Subset ($\subseteq$) - Set $A$ is a subset of $B$ if every element of $A$ is also in $B$

Quantifiers - they help us turn predicates into statements

$P(n)$ Is a predicate
But $\mathrm{\forall }n\in \mathbb{Z}\mathrm{\exists }P(n)$ is a statement

Universal quantifier

The expression above in words means “for every integer $n$, $n^2$ is greater than or equal to 0”

Existential quantifier

“There exists at least integer $n$ such that $n^2$ is 289

Logical operators

Probably the best way to think about these, is to form a truth table (warning: may trigger past CS trauma…) - think of True as 1 and False as 0, binary

Definition

1. Conjunction - both statements are true - like the AND logic gate

2. Disjunction - at least one statement is true - like the OR logic gate

3. Negation - the statement is false - like the NOT logic gate

Definition. Tautology: A statement that is always true
Definition Contradiction: A statement that is always false

Logical equivalent - two statements have the same truth table

Rules - flashback to AQA CS being actually useful

• Idempotent - something that squares to itself
  • Eg: $0^2=0$ or $1^2=1$
• Notice how there’s a difference between associative and distributive
  • Associate - the symbol is the same all the way
  • Distributive - it’s like mixing the signs for $\times$ and $+$

Proving the De Morgan’s Laws - on Anki

“Break the line, change the sign”

• Well, you can do it using truth table, or Venn diagram probably

Think about this analogy, let $P$ be the statement: “A in even” and $Q$ be the statement: “Q is even”.

Then $P\wedge Q$ would be the statement: A is even and B is even
If we were to negate that statement, i.e $\mathrm{\neg }(P\wedge Q)$ would be result in the statement: “Either one of A or B is not even”

So $$ \neg (P \wedge Q) = (\neg P) \vee (\neg Q)$$
Consider the absorption rule below

But how can we prove this?
Think back to the identity rule where we had: $$ P \equiv P \wedge T $$
So we have

After substituting, we can use the distributive rule, to factorise this:

Note, $T\vee Q\equiv T$ (annihilation rule), so we’re left with $P$ given the identity rule
Another way to think about it: $T\vee Q\equiv (Q\vee \mathrm{\neg }Q)\vee Q$
Then after using communicative and associate rules by moving the brackets around, we have: $$ (Q \vee Q) \vee (\neg Q) $$
Then by the idempotent rule: $Q\vee Q\equiv Q$
And then $Q\vee \mathrm{\neg }Q\equiv T$
Look at the gold example on notes…

Negating quantifiers

Consider this statement below:

What does it mean for the statement to be false?
It means $\mathrm{\exists }n\in \mathbb{Z}s.t.n^2<0$

In general…

Implications

If $P$ is false, then the statement doesn’t tell us anything about $Q$, the latter can be true or false

If we know that $P⟹Q$ is true, then:

• $P$ and $Q$ can be both true
• $P$ is false and $Q$ is true
• $P$ and $Q$ can be both false

But.. if $P⟹Q$ is true and $P$ is also true, then:

• $Q$ is also true

This principle above is called modus ponens

Definition - A counterexample is where the first statement is true, but the second statement is false, which makes the implication false

If we were to negate the implication, we’d get:

Using De Morgan’s, we get

So a counterexample by definition is when $P$ is true and $Q$ is not true

To claim that a statement is false is the same as claiming that its negation is true

Consider this example in words:
What’s the negation of $\mathrm{\forall }p\in \mathbb{Z},p$ is prime $⟹$ $2^p-1$ is prime

So this would be $\mathrm{\exists }p\in \mathbb{Z}s.t.p$ is prime and $2^p-1$ is not prime

Converse and Contrapositive

Definition Converse of an implication $P⟹Q$ is the reversed implication $Q⟹P$

Definition Equivalence $P⟺Q$ is the same as $P⟹Q\wedge Q⟹P$. It’s an if and only if statement

Definition Contrapositive of an implication $P⟹Q$ is the implication $\mathrm{\neg }Q⟹\mathrm{\neg }P$

Proof by contrapositive can be useful in some case. Consider the proof, $n^2$ is even $⟹n$ is even. The contrapositive version of this would be $n$ is not even $⟹$ $n^2$ is not even. So if we start by taking $n$ to be odd and then proving that $n^2$ is odd, we have our proof for the original statement.

When $P$ is true, then $Q$ must also be true, but this also means that $Q$ is false could only happen when $P$ is false
We can prove this using the commutative and double negation rule

Using the commutative rule we get:

Then using the double negation rule we have:

Notice how this is the definition of implies:

Modus ponens

Proofs

Definition A Proof is a sequence of steps used to demonstrate that a statement is true

Proofs begin with a premise, aka a collection of statements/predicates that we accept as true (axioms).

The result that we want to show is the conclusion

Rules of Equality

When we say $a=b$, it means that $a$ and $b$ refer to the same indistinguishable objects

• reflexive $a=a$
• symmetric $a=b⟺b=a$
• Transitive $a=b\wedge b=c⟹a=c$

Proof by contradiction

The idea behind this is to take our premise and negation of conclusion as the assumption
The formal justification is that if we show $\mathrm{\neg }P$ implies another false statement, then we have proved that:

And by using our logical equivalences

So if we have problem that the negation is false, then we proven that the original statement is true

Example- proving $\sqrt{2}$ is irrational

First we need by take our premise and the negation of our conclusion, i.e assuming that $\sqrt{2}$ is rational

And now we need to show that $\mathrm{\exists }a,b,\in \mathbb{Z}$ is false

So suppose $\mathrm{\exists }a,b,\in \mathbb{Z},s.t.a^2=2b^2$ - this is our premise

Let $d$ be the greatest common divide of $a,b$ (definition)

Then $d$ is a divisor of $a$ and $d$ is a divisor of $b$ (by defn of g.c.d)

$\mathrm{\exists }u\in \mathbb{Z}s.t.a=du$
$\mathrm{\exists }v\in \mathbb{Z}s.t.b=dv$

So we have $(du{)}^2=2(dv{)}^2$ (substitution)
After expanding an simplifying, we have:
$(u^2)=2v^2$
We’ve kind of got to where we started, but instead of having $a$ and $b$, we have $u$ and $v$, but instead this time, $u$ and $v$ cannot be even due to our introduction of the g.c.d.

But look again at our expression, $u^2$ is even (defn of even), so $u$ is even (previous result)
Therefore, $\mathrm{\exists }k\in \mathbb{Z}s.t.u=2k$
So $(2k{)}^2=2v^2$ (substitution)

After some expanding and simplifying, we have that
$(2k{)}^2=v^2$
So this means that $v^2$ is even (by defn of even) and $v$ is even

So now $\mathrm{\exists }l\in \mathbb{Z}s.t.v=2l$

And after we substitute back into the definitions of $a$ and $b$, we get:

2. Integers

Axioms - set of properties that we accept without requiring a proof
How do we know that axioms are axioms?

There is a list of algebraic axioms and order axioms:

• [Operations (Op)] The integers are equipped with two binary operations addition and multiplication. These operations are denoted by the symbols $+,\cdot$respectively.

• [Identity (Id)] Z contains two special elements, denoted $0$ and $1$, with $0\ne 1$ such that for any integer $m,m+0=0+m=m$ and $m\cdot 1=1\cdot m=m$.

• [Negation (Neg)] For every integer $m$, there exists an integer denoted $-m$ such that $m+(-m)=(-m)+m=0.$
  We write $a-b$ as a shorthand for $a+(-b).$

• [Commutative (Comm)] Addition and multiplication are commutative, i.e. $m+n=n+mandm\cdot n=n\cdot m\mathrm{\forall }m,n\in Z$

• [Associative (As)] Addition and multiplication are associative, i.e. $(m+n)+p=m+(n+p)$ and $m\cdot (n\cdot p)=(m\cdot n)\cdot p\mathrm{\forall }m,n,p\in Z$

• [Distributive (Dist)] Multiplication distributes over addition, i.e, $m\cdot (n+p)=m\cdot n+m\cdot p\mathrm{\forall }m,n,p\in Z.$

• [Zero divisors (ZD)] If $m\cdot n=0$ then $m=0$ or $n=0$.

• [Order relation (Ord)] $\mathbb{Z}$ is equipped with a relation $\le$ called “less than or equal to”.

• [Reflexive (Ref)] Every integer $m$ satisfies $m\le m$.

• [Antisymmetric (ASy)] Given two integers $m,n$, if $m\le n$ and $n\le m$ then $m=n$.

• [Transitive (Tr)] If $m,n,p$ are integers with $m\le n$ and $n\le p$ then $m\le p$.

• [Comparability (Comp)] Given any two integers $m,n$, $m\le n$ or $n\le m$.

• [Shift (Sh)] If $m,n,p$ are integers with $m\le n$, then $m+p\le n+p$

• [Scale (Sc) ] If $m,n,p$ are integers with $m\le n$ and $0\le p$ then $m\cdot p\le n\cdot p$.

• [Well ordering (WO)] The well ordering principle – any non-empty subset of non-negative integers has a unique least element.

All of these axioms will hold true even if we work with the reals, naturals, and complex numbers, and that’s why we have the ordering axioms - which work for the set of integers.

For $m,n\in \mathbb{Z}$, exactly one of the properties below hold:

• $m<n$
• $m=n$
• $m>n$
  We can prove the other inequalities from the properties above

Proof that $0<1$ (proof by contradiction)

Our starting point to take the premise and negation of our conclusion as the assumption:

So suppose $\mathrm{\neg }(0<1)⟹1\le 0$

The scaling axiom says something about 0.

According to the shift axiom:

Then using the negation, and identity axiom:

Scaling axiom, we can rescale by $-1$

And by identity axiom:

Substitution:

By identity and negation

And by the identity axiom once again:

And hence we have contradiction

Note on the Well-ordering principle

Essentially, $n$ is the least element of a set $S$ if:

• $n\in S$
• $\mathrm{\forall }m\in S,m\le n⟹m=n$
  This is just means that $n$ is the smallest element in the set, and if there is a smaller element $m$ than $n$, then that element just equals $n$.

Proof of $1$ being the least element of the set ${\mathbb{N}}_1$ of positive integers

Let $n$ be least element of $N_1$

We can say that

Assume $1\le n$
But as $n$ is the last element of ${\mathbb{N}}_1$ and $1\in \mathbb{N}$, so $n=1$

Now let’s assume that $n\le 1$. What we’re trying to show that there are no elements between $0$ and $1$

We know that $n\in \mathbb{N}$, so we can apply the scaling axiom to say that:

So now is $n^2\in \mathbb{N}$?
We can use scaling axiom to say that:

By the zero divisor axiom we have that $n\cdot n=0⟹n=0\text{ or }n=0$
This is a contradiction as $0\le n$

So we know that $n\cdot n\in \mathbb{N}$

But we know that $n$ is the lease element of ${\mathbb{N}}_1$

So $n\cdot n\le n$

So we have
$n\cdot 1=0$ or $n=0$

So $n=1$

Proof by Induction

• The first step is called the base step where use a starting case for induction
• Second step is the inductive step
• The premise $P(n)$ in the inductive step is called the inductive hypothesis

Proof of the proof by induction

What we want to prove that is $P(1)$ is true, then $\mathrm{\forall }n\ge 1,P(n)⟹P(n+1)$, then $P(n)$ is true $\mathrm{\forall }n\ge 1$

And we'll prove it by contradiction. So we assume the conclusion is false, i.e. $\mathrm{\exists }k\in {\mathbb{N}}_{1}s.t.P(n)\equiv F$

So if there exists at lease one number $k$ where $P(k)$ is false, we can collect all of them into a set:

This set $S$ is non-empty, because we're assuming that there's at least one false case

By the W.O (well ordering) principle, every non-empty subset of $\mathbb{N}$ has a least (smallest) element, and since $S$ is non-empty, there must be a smallest number, let that number be $m$.
This means that:

• $P(m)$ is false as $m\in S$
• Every smaller number has $P(n)$ True because $m$ is the first smallest number for which $P$ fails

Now we have a few cases to consider:

• If $m=1$, we've contradicted the premise, which says that $P(1)$ is true, so this is a contradiction. So $m\ne 1$
• $P(m-1)$ is true, because $m-1<m$ and all the numbers smaller than $m$ are true
• The inductive steps means that if $P(n)$ is true, then $P(n+1)$ is true

If $m$ is the smallest number where $P$ fails, then consider $n=m-1$, for which $P(n)$ is true, by the inductive step we have:

So $P(m)$ must be true, but as we've defined $m$ to be the first case where $P(m)$ is false as $m\in S$, this leads to a contradiction.

This means there are no numbers in the $S$ which satisfy the property, so there is no point where induction fails.

Example

Suppose we want to prove that $$ \forall n \geq 1, n! \leq n^n$$
So we start with the base case, $n=1$

$1!=1$ and $1^1=1$

Now for the inductive step, we want to prove the statement below:

We assume the statement holds for some $n$, and this is the induction hypothesis, so assume $$ P(n) = n! \leq n^n$$
And now we want to prove this for $(n+1)$

By the def. of factorial, we have

Now, using our scaling axiom and the inductive hypothesis ($P(n)=n!\le n^n$), we have:

As we know that $n<n+1$, we have that $n^n<(n+1{)}^n$. Using the scaling axiom again we have:

Notice how this gives us the following:

Hence the result follows by mathematical induction

Weak vs Strong induction

In weak induction, we only look one step back, i.e. assume that $P(n)$ is true and then use that to show that $P(n+1)$.

Strong induction is slightly difference, as we assume all the past results to prove the next step in the induction step, i.e. use all $P(1),P(2),...,P(n)⟹P(n+1)$

Decimal expansions, as covered in the next section, are an application of strong induction as we need the fact that every smaller number has a representation.

Decimal Expansions

#finishexplaination

Remainder Theorem

Useful for modular arithmetic which is useful for cryptography

Definition
If $a$ and $b$ are integers with $b\ne 0$, then there is a unique pair of integers $q$ (quotient) and $r$ (remainder) such that $$a = qb +r , \quad 0 \leq r < |b|$$
It's $|b|$ because the absolute value makes it work whether $b$ is positive or negative
Consider two cases below:

The second case is wrong because we can still take away 3 from 10. So that’s the idea of the proof, just keep taking away from the remainder until we’re left with a negative number as the remainder must be positive

Proof of the remainder theorem

The proof has few parts

• Existence - showing there are such integers $q$ and $r$ that work
• Show that the remainder $r$ is less than $|b|$
• Uniqueness - showing they are the only such pair

Existence

Let's start with case 1: $a\ge 0$

The idea is that we keep subtracting $|b|$ from $a$ until what's less is less than $|b|$
Formally, we define a set:

So $S$ is essentially the set of all non-negative remainders we can get when subtracting multiples of $|b|$ from $a$

Consider case 2: $a<0$

If $a$ is negative, we just flip the sign:

So the theorem works for all $a$, positive and negative

Showing $r<|b|$

Notice that $S$ is non-empty as for $q=0,a-0|b|=a\ge 0$ , so by the well-ordering, every non-empty set of non-negative integers has a smallest element

Let that smallest element be $r$.
Suppose for contradiction that $r\ge |b|$
Then we can make a new remainder: $r^{‘}=r-|b|$

Notice that:

This means that $r^{‘}=r-|b|\le 0$, so $r^{‘}\in S$

We've just shown that $r^{‘}<r$ which leads to a contradiction as $r$ is meant to be the smallest element, so $r^{‘}\notin S$, which means that $r<|b|$

Uniqueness

Suppose that there were two pairs:

We subtract one from the other to get:

This means that the left side is a multiple of $b$, but the right side is smaller than $|b|$ as both remainders are between $0$ and $|b|$

Now, if the left side is a non-zero multiple of $b$, then its absolute value must at least be $b$, but the right side is strictly less than $b$. So the only way this equality can hold true is if the right side is $0$

So $r_1=r_2$ and therefore $q_1=q_2$

So the pair $(q,r)$ is unique

3. Divisibility and Euclid’s Theorem

Definition An integer $d$ is a divisor of the integer $a$ iff there is an integer $b$ such that $db=d$

Notation - $d|a$ means $d$ is the divisor of $a$ (i.e $\frac{a}{d}$ is a integer but we’re not allowed to write it in division/fraction form)

Fun fact - not every integer is a divisor of every other integer

Greatest Common Divisor

Definition The greatest common divisor of $a$ and $b$ is the unique integer $d$ satisfying:

• $d|a$ and $d|b$
• If $c|a$ and $c|b$ then $c\le d$ so that no common divisor exceeds $d$

Notation - the greatest common divisor of $a$ and $b$ is given by: $gcd(a,b)$

Euclidean Algorithm

Essentially, the Euclidean Algorithm finds the gcd of two integers $a$ and $b$

Consider the example below: $a=252$ and $b=105$

We do repeated division:

When the remainder becomes $0$, the last non-zero remainder is the greatest common divisor. Hence $gcd(252,105)=21$

Basically, we repeatedly apply the remainder theorem on numbers and do some shifting until the remainder is 0. The proof of the Euclidean will be covered later in the module

where $r_n=gcd(a,b)$

Each line $a=qb+r$ says the same common divisor that divide $a$ and $b$ will also divide $r$. And this is where the linear combination in the section will come in.

Divisors and Linear Combination

Cancellation Lemma - if $m,b,p\in \mathbb{Z}$ s.t. $mp⟹np$ and $p\ne 0$, then $m=n$

We can use this lemma and the linear combination to prove Eucledian's Algorithm

If $a,b$ are integers with $a=qb+r$ then $gcd(a,b)=gcd(b,r)$

Now, if we can show that any common divisor of $(a,b)$ also divides $(b,r)$ and any common divisor of $(b,r)$ also divides $(a,b)$, this is means common divisors are the same, so their greatest common divisor must be the same, i.e. $gcd(a,b)=gcd(b,r)$

Let the common divisor of $(a,b)$ and $(b,r)$ be $d$. And we want to show that $d|r$ and $d|a$. It's like showing that two subsets are equal, which means they are the same set.

So if $d|a$ and $d|b$, then $a=d{k}_1$ and $b=d{k}_2,k\in \mathbb{Z}$

Now, using the remainder theorem we have:

Hence $d|r$

Now to prove the converse - if $d|b\wedge d|r⟹b|a$

$b=d{k}_3$ and $r=d{k}_{4}k\in \mathbb{Z}$

Using the definition again we have:

Hence, by definition, we have $d|a$

And therefore, $gcd(a,b)=gcd(b,r)$

Proof of Euclid’s Algorithm

The Euclid algorithm is essentially the step above repeated

until the remainder becomes 0:

There's a nice proof by contradiction to show that this process does not go on forever. So assume this goes on forever, then the set containing all the remainders is: $S=\{r_1,r_2\dots r_n\}$ will have no least element-- which contradicts the W.O axiom, so there must be a least element, which is $r_n=0$

By the rule, we've just proved that:

So when we finally hit $r_k=0$, the gcd is the last non-zero remainder:

Euclid’s Algorithm for Polynomials

The operation on polynomials satisfy all of the algebra axioms as the integers do, so they are an example of a commutative ring. But matrices are an example of non-commutative ring as they don’t saying the commutativity axiom

Definition A commutative ring is a set $R$ equipped with two binary operations: $+,\cdot$ and satisfying the axioms Op, Id, Neg, Comm, As, Dist

Bezout’s (Bucket) Identity

Definition If $a$ and $b$ are integers, then $\mathrm{\exists }u$ and $\mathrm{\exists }v$ s.t.

And then $gcd(a,b)$ is the least positive integers of the form of $au+bv(u,v)\in \mathbb{Z}$

Consider two buckets, one 4 litre and one 7 litre, now, can we measure 1 litre using those two?
Well, fill up the 4l twice and then pour it in the 7l, whatever’s left in the 4l is 1l, and that’s what Bezout’s Identity is telling us - we can solve the bucket problem when the gcd is what we’re trying to measure.

Ideals

The proof of Bezout’s Identity involves a set called ideals

Definition Let $R$ be a ring, then the subset of $I$ in $R$ is an ideal if:

• $I$ is non-empty
• $\mathrm{\forall }a,b,\in I,a+b\in I$ - closed under addition
• $\mathrm{\forall }a\in I$ and $r\in \mathbb{Z},ra\in I$ - closed under multiplication by any non-negative integer

Notice how this is similar to vector sub spaces in linear algebra.

For example:

• The set $I=\{0\}$ is an ideal of $\mathbb{Z}$
• The set of even numbers is an ideal of $\mathbb{Z}$
• The set of odd numbers is not an ideal as it’s not closed under addition nor multiplication by all other integers

Closed means that we don’t have to move outside the set if we apply an operation, i.e. if set $S$ has an operation $\ast$, then $S$ is closed under $\ast$ if

Proof of Bezout’s Identity

Lemma 3.14 Let $a,b\in \mathbb{Z}$, then the set:

Is an ideal in $\mathbb{Z}$ as it's is non-empty because we can have $a(1)+b(0)\in I$ and it's is closed under addition and multiplication

Now, let $I$ be a non-zero ideal in $\mathbb{Z}$, then $\mathrm{\exists }d\in I$ s.t.:
Lemma 3.15

In other words, take any non-zero ideal $I\in \mathbb{Z}$, then $\mathrm{\exists }d\in \mathbb{Z}$ s.t.

• Every element of $I$ is a multiple of $d$
• Every multiple of $d$ is in $I$
• Among all the elements of $I$, $d$ is the smallest

This means $I$ has the form:

What this basically means is that every ideal in $\mathbb{Z}$ is made of all the multiples of one single number. And that one number is the smallest positive element in that ideal.
Why do we care? Because Bezout's identity is about showing that the $gcd$ of this idea is the smallest positive element in that ideal. In other words, for any ideal $I\in \mathbb{Z}$, when we input the ideal of all linear combinations $a,b$, the the output $d$ gives us exactly $gcd(a,b)$ -- which is very cool!!

So we let $d$ be the least positive element of $I$ (W.O principle)

Now we want to show for the iff that:

1. $x\in I⟹d|x$
2. $d|x⟹x\in I$

2.Suppose $d|x$
$⟹\mathrm{\exists }q\in \mathbb{Z}s.t.x=qd$
$d\in I$ by definition
$q\in \mathbb{Z}$
$I$ is an ideal
So $x=q\cdot d\in I$ because by definition an ideal is closed under multiplication by any integer, all multiples of $d\in I$

1. Let $x\in I$
   Then by the remainder theorem we have $x=qd+rq,r\in \mathbb{Z}0\le r<|d|$
   We know that $d\in I⟹(-q)d\in I$ as by definition, multiplies of $d$ are in $I$ as ideal is closed under multiplication

Now, $r=x-qd=x+(-q)d$
as $x\in I$ and $(-q)d\in I$ $⟹$ $x+(-q)d\in I⟹r\in I$
As $r<d$ by definition of the remainder theorem, and $d$ is the least a positive positive element of $I$, $r$ is not positive $⟹r\le 0$, but as we have that $r>0⟹r=0$

Hence, we have shown that $x=qd+0=qd$, so every element of $I$ is in fact a multiple of $d$

Now, all that remains is to show that $d$ is the $gcd(a,b)$

So let:

This is an ideal by Lemma 3.14, and so by Lemma 3.15, $\mathrm{\exists }d\in I$ s.t. $d|x\mathrm{\forall }x\in I$

Since $d\in I$, by definition, $\mathrm{\exists }u,v$ s.t. $d=au+bv$

Now, we want to show that $d$ divides both $a$ and $b$.
Note that both $a$ and $b$ are in $I$, so:

• $a=a\cdot 1+b\cdot 0\in I$
• $b=a\cdot 0+b\cdot 1\in I$

Therefore, $d$ is a common divisor of $(a,b)$

Let $c$ be any common divisor of $(a,b)$

• If $c|a$ and $c|b$, then $c$ divides any combination of $au+bv$
• So $c$ divides element of $I$ and in particular, $c$ divides $d$

So any common divisor of $c$ of $(a,b)$ satisfies:

This means that $d$ is at least as big as any other common divisor, but since $d$ is positive, we have:

Therefore, $d=gcd(a,b)$

Lamé’s Theorem

Definition
The number of steps in the Euclidean algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.

Eg: if we apply the Eucledian algorithm to integers with 100 digits, then we require no more than 500 steps in the algorithm.

The proof of this beautifully involves the Fibonacci and the golden ratio.

Co-prime integers

Definition Two integers $a$ and $b$ are co-prime if $gcd(a,b)=1$

Definition Integers $a_1,a_2,\dots ,a_n$ are mutually co-prime if $gcd(a_i,a_j)=1,i\ne j$

Eg: integers $6,10,15$ are co-prime but not mutually co-prime

Two integers are co-prime $⟺$ $\mathrm{\exists }x,ys.t.ax+by=1$

If $gcd(a,b)=d$, then

Where $a=ud$ and $b=vd$

Let $a$ and $b$ be co-prime, then:

Note how this only works if the numbers are co-prime. The proof of both of them are in in notes.

Least Common Multiple

Pretty much self-explanatory, the lowest common multiple of two numbers is just the product of those numbers divided by the greatest common divisors of two numbers
If $a,b\in \mathbb{Z}$ and if $d=gcd(a,b)$ and $l=lcm(a,b)$ . Then:

Linear Diophantine Equations

Let $a,b,c\in \mathbb{Z}$ and $a,b\ne 0$, let $d=gcd(a,b)$. Then the equation

Has integer solutions $⟺gcd(a,b)|c$ and if it does, then there are infinitely many solutions:

Where $a=pd,b=qd$ and $(x_0,y_0)$ is any particular solutions. It’s a bit like doing differential equations.

Proof

The if an only if part is just Bezout’s identity. Any common divisor of $a$ and $b$ divides every intger linear combination of $a$ and $b$

So now we just need to prove what the general solution looks like

So assume we have one particular solution, so let $(x_0,y_0)$ satisfy $a{x}_0+b{y}_0=c$. And now we want to find out all the other pairs ($x,y$) that also make $ax+by=c$

Let $n\in \mathbb{Z}$ s..t

Where $a=pd$ and $b=qd$

Now we put this in the $ax+by=c$ to get:

So this works for any integer $n$

Now we need to show that these two are the only solutions, so we suppose that ($x,y$) is any integer solutions

We subtract the two equations to get:

After substituting $a=pd$ and $b=qd$ we get:

After dividing through by $d$ (the cancellation lemma), we have:

What this tells us that the difference between any two solutions is related by $p$ and $q$. And since $p$ and $q$ are co-prime, because that’s what happens when we divide by the gcd, the only way this equality holds in integers is if:

Which is exactly the formula for the infinitely many solutions

4. Prime Numbers

Definition An integer $p>1$ is irreducible if the only positive divisors of $p$ are $1$ and itself

Definition An integer $p>1$ is prime if $\mathrm{\forall }a,b\in \mathbb{Z}$, whenever $p|ab$ either $p|a$ or $p|b$

For example, to prove that $2$ is a prime number, we need to show that $2|ab⟹2|a$ or $2|b$

By the remainder theorem, $\mathrm{\exists }{q}_i{r}_{i}s.t.a=2q_1+r_1,b=2q_2+r_2,0\le r<2$

So we have:

We also know that $ab$ is even, so $ab=2k+0$
As the remainder theorem only gives unique values:

Therefore, $2$ is a prime number

Primes and Irreducible

Prime and irreducible really mean the same thing, at least for the integers.

Fermat was said to be confused about this difference too. If factorisation of irreducible numbers was unique, then Fermat’s last Theorem would’ve been a lot easier (why?) In other things however, this is not always true. For instance, consider the ring:

Now, I hope we can agree that

But $2$ does not divide $\sqrt{5}+1$, so by definition of a prime, $2$ is not prime

prime $⟹$ irreducible:

Assume $p$ is prime and $p=ab,b>0$ (premise)
By definition, $p|a$ or $p|b$.
WLOG (without loss of generality), assume that $a=pk,k\in \mathbb{Z}$ Then:

By the cancellation lemma, we have $1=kb$ so $b\le 1$. But as $b>0⟹b=1⟹a=p$. Therefore, $1,p$ are the only positive divisors of $p$, so $p$ is irreducible

Irreducible $⟹$ prime

Note that this is not always true, as with our example in the ring, but in integers, this will work
So let $p$ be irreducible and suppose $p|ab$. Then we want to show that $p|a$ or $p|b$

As $p$ is irreducible and since $gcd(a,p)$ is a positive divisor of $p$, then $gcd(a,p)$ must be $1$ or $p$

If the $gcd(a,p)=p$, then as $gcd(a,p)$ also divides $a$, it follows that $p|a$

On the other hand if the $gcd(a,p)=1$, then by definition $a$ and $p$ are co-prime and by Bezout's identity, we have that:

Multiplying the entire equation by $b$ we have:

By our assumption, as $p|ab⟹p|aby$ and $p|abx$. Therefore the RHS is divisible by $p$ and therefore $p|b$

Lemma 4.4: If $p$ is prime and $p|a_1,\dots a_k⟹p|a_i$ for some $i$ - this can be proved by induction, which is in the notes

The Fundamental Theorem of Arithmetic

Each integer $n>1$ has prime-power factorisation:

Where $p_1,\dots ,p_k$ are distinct primes and $e_1,\dots e_k$ are positive integers. The factorisation is unique, apart from permutation of the factors

Say I wrote a prime factorisation of $12$, how can I know that the prime factorisation is unique? That's exactly what the fundamental theorem of arithmetic allows us to do - every integer $n>1$ is can be written as a product of primes, and this factorisation is unique up to reordering.

The proof of this has two parts:

• Existence - every integer has a prime-power factorisation
• Uniqueness - this factorisation is the only one

Existence - using strong induction

Base case: $n=2$. We proved earlier that $2$ is prime, so its factorisation is simply: $2=2^1$

Induction hypothesis: assume every integer strictly between $1$ and $n$ already has a prime-power factorisation.

Inductive step: prove it for $n$. There are two cases here:

1 - $n$ is prime, which case $n=n^1$ and we're done
2 - $n$ is composite

In case 2, let $n=ab,1<a,b<n$

Now both $a,b$ have prime power decomposition by the induction hypothesis, so by substituting these into the equation $n=ab$, and then collecting powers of each prime $p_i$, we get a prime-power factorisation for $n$

Uniqueness

This will also be done by strong induction.

Base case: Suppose $n=2$ has factorisation $2=p_1^{e_1}{p}_2^{e_2}\dots p_k^{e_k}$

Then by definition each prime $p_i\ge 2$. If there is any prime $p_1>2$ contradicts $p_1^{e_1}{p}_2^{e_2}\dots p_k^{e_k}=2$
Hence the only factorisation of $2$ is $2^1$

Induction step: assume that $n>2$ and that for every integer strictly between $1$ and $n$ has a unique prime factorisation up to ordering

Now suppose we had two different factorisation:

Where all $p_i$ and $q_i$ are primes. Then our aim to show that these two sets of distinct primes are the same, up to reordering

From the first factorisation, we have that: $p_1|n$
So in the second factorisation, by Lemma 4.4 earlier, we know that:

Since $p_1$ is prime, it must divide one of the $q_j$, but each $q_j$ is prime too. So the only possibility is that: $p_1=q_j$

This essentially allows us to match up one prime from each factorisation. WLOG, we can order the primes so that: $p_1=q_1$

Now we have that

We can cancel $p_1=q_1$ from both sides to get:

And this new number is strictly smaller than $n$.

If this new number is $1$, the $k=l=1,e_1=f_1,p_1=q_1$, so the two factorisation were the same.

Otherwise, $p_1^{e_1-1}{p}_2^{e_2}\dots p_k^{e_k}$ is strictly between $1$ and $n$ so by the induction hypothesis, it has a unique prime factorisation up to reordering. So $k=l,e_1-1=f_1-1$ and $p_2^{e_2}\dots p_k^{e_k}=q_2^{f_2}\dots q_l^{f_l}$ up to reordering.