# definitions

**Well-Ordered**

A nonempty subset $S\subseteq\mathbb{Z}$, if it contains a least element.

**Prime Number**

An integer $t$ , where $t > 1$ , is said to be prime if the only numbers that it can be divided by are $1$ and it's positive self $t$.

**Composite Number**

An integer, greater than $1$, which is not prime.

**Common Divisor**

An integer $n$ which divides two different integers $d$ and $q$ without remainders.

**Greatest Common Divisor**

The largest possible non-zero integer $p$ that divides two non-zero integers $w$ and $x$ without a remainder.

**Relatively Prime**

Two integers are said to be relatively prime if their Greatest Common Divisor is $1$.

**Set of relatively primes**

Let $U(n)$ be the set of elements in $\Bbb{Z}_n$ that are relatively prime to $n$ $U(n)$ is called the group of units mod n.

**Example of a set of relatively primes**

$\Bbb{Z}_8$ = {0,1,2,3,4,5,6,7} $U(8)$ = {1,3,5,7} Because gcf (8,1)=1 so 1 is in $U(8)$ gcf of (8,2)=2 so 2 is not in $U(8)$ etc. Another example would be $<i>$ =$\{{-1, 1, i, -i}\}$ in $\Bbb{C}^*$

**Euclidean Algorithm**

Is the process involving repeated division by which we can find the greatest common divisor of any two nonzero integers.

# theorems

**Theorem 1.2**

The Principle of Mathematical Induction implies that the natural numbers are well-ordered.

**Division Algorithm** (Theorem 1.3)

Let $a,b\in\mathbb{Z}$ with $b>0$. Then there exists unique integers $q$ and $r$ such that

where $0\leq r< b$.

**GCD** (Theorem 1.4)

Let $a, b \in \mathbb{Z}$. Then there exists $r,s \in \mathbb{Z}$ such that

We can also say that the gcd(a,b) is unique.

**Corollary 1.5**

Let $a, b \in \mathbb{Z}$ such that $a$ and $b$ are relative prime. Then there exists $r,s \in \mathbb{Z}$ such that

**Lemma 1.6**

Let $a,b\in \mathbb{Z}$ and let *p* be prime. If $p|ab,$, then either $p|a$ or $p|b$.

**Theorem 1.7**

There exist an infinite number of primes.

Lemma 1.6 (Euclid) Let a and b be integers and p be a prime number. If

p divides ab, then either p divides a or p divides b.

# examples & notes

**The Euclidean Algorithm**

Computing the Greatest Common Divisor of 6798 and 186.

So the GCD of $6798$ and $186$ is $6$.

Now if we work backwards by doing repeated substitution, We see that:

(5)So $6798(r) + 186(s) = 6$ where $r=11$ and $s= -402$.

**First Principle of Mathematical Induction ("Weak Induction")**

Suppose $S(n)$ is an open sentence. If

- Base Case: $S(n_{0})$ is true for some $n_{0} \in \mathbb{N}$ and
- Inductive Step: for all $k \geq n_{0}, S(k)$ implies $S(k+1)$ is true,

then $S(n)$ is true for all natural numbers $n \geq n_{0}$.

**Second Principle of Mathematical Induction ("Strong Induction")**

Suppose $S(n)$ is an open sentence. If

- Base Case: $S(n_{0})$ is true for some $n_{0} \in \mathbb{N}$ and
- Inductive Step: for all $k \geq n_{0}, S(n_{0}), S(n_{1}),...S(k)$ implies $S(k+1)$ is true,

then $S(n)$ is true for all natural numbers $n \geq n_{0}$.

Note: PMI=PCI=WOP

**Classic inductive proof**

The sum of n integers i.e. $1+2+3+\cdots +n= \frac {n(n+1)}{2}$

**Proof**

Prove:

(6)We will prove by induction

***Base Case**

Let n=1

**Now we will prove by induction**

Let $a\in\mathbb {N}$ and assume $1^2+2^2+...+a^2= \frac {a(a+1)(2a+1)}{6}$

**Prove that $f_{n} < 2^n$, for $n\in\mathbb{N}$**

Base case:

We see that when $n=1$

$f_{n}=1$.

And on the other hand:

$2^{n}=2^{1}=2}$.

Therefore the base case works for $n=1$.

We can also see that the next element is $n + 1=2$,

$f_{n+1}=1$.

And on the other hand:

$2^{n +1}=2^{2}=2}$.

Therefore the base case works for $n +1$.

Inductive step: Let $k\in\mathbb{N}$ and assume $f_j < 2^j$ for all $j \leq k$.

We know that

(9)We also know

(10)Thus the formula works for $n=1$. Therefore by induction the formula is true for all $n\in\mathbb{N}$.