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