chapter 1 summary

# 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

(1)
\begin{equation} a=bq + r , \end{equation}

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

(2)
\begin{equation} gcd(a,b)=ar+bs. \end{equation}

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

(3)
\begin{equation} ar+bs=1. \end{equation}

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.

(4)
\begin{align} 6798 =36 \times 186 + 102\\ 186 = 102 \times 1 + 84\\ 102 = 84 \times 1 + 18\\ 84 = 18 \times 4 + 12\\ 18 = 12 \times 1 + 6\\ 12 = 6 \times 2 + 0 \end{align}

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

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

(5)
\begin{align} \begin{align} 6&= 18 + -1(12)\\ &= 18 + -1(84 + -4(18))\\ &= 5(18) + -1(84)\\ &= 5(102 + -(84)) + -1(84)\\ &= 5(102) + -6(84)\\ &= 5(102) + -6(186 + -1(102))\\ &= 11(102) + -6(186)\\ &= 11(6798 + -36(186)) + -6(186)\\ &= 11(6798) + -402(186)\\ \end{align}

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

1. Base Case: $S(n_{0})$ is true for some $n_{0} \in \mathbb{N}$ and
2. 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

1. Base Case: $S(n_{0})$ is true for some $n_{0} \in \mathbb{N}$ and
2. 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)
\begin{align} 1^2 + 2^2+....+n^2 = \frac {n(n+1)(2n+1)}{6} \end{align}

We will prove by induction
*Base Case
Let n=1

(7)
\begin{align} \begin {align*} 1^2 & = \frac {1(1+1)(2(1)+1)}{6}\\ 1 & = \frac {6}{6}\\ 1 & = 1 \end{align}

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}$

(8)
\begin{align} \begin {align*} 1^2+2^2+...+a^2 & = \frac {a(a+1)(2a+1)}{6}\\ 1^2+2^2+...+a^2+(a+1)^2 & = \frac {a(a+1)(2a+1)}{6}+(a+1)^2\\ & = \frac {a(a+1)(2a+1)+6(a+1)^2}{6}\\ & = \frac {a(a+1)(2a+1)+6(a^2+2a+1)}{6}\\ & = \frac {a(a+1)(2a+1)+(6a^2+12a+6)}{6}\\ & = \frac {a(2a^2+a+2a+1)+(6a^2+12a+6)}{6}\\ & = \frac {2a^3+a^2+2a^2+a+6a^2+12a+6}{6}\\ & = \frac {2a^3+9a^2+13a+6}{6}\\ \end{align}

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)
\begin{align} f_j < 2^j \text{and} f_{j-1} < 2^{j-1}. \end{align}

We also know

(10)
\begin{align} f_{j+1} &= f_j +f_{j-1}\\ &< 2^{k} + 2^{k-1}\\ &< 2^k \cdot 2\\ &=2^{k+1}. \end{align}

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

page revision: 32, last edited: 09 Mar 2010 12:55