A Little Bit of Number Theory

21.1 Long Division:

Let be two integers. There exits unique integers $\QTR{Large}{q}$ and $\QTR{Large}{r}$ with and

Uniqueness follows from the fact that implies

thus assuming we have

_______________________________________

21.2 Definition:

Let be two integers. The greatest common divisor of $\QTR{Large}{m}$ and $\QTR{Large}{n}$ is defined to be largest integer $\QTR{Large}{d}$ such that

$\QTR{Large}{d}$ divides both $\QTR{Large}{m}$ and $\QTR{Large}{n}$ . We write .

Since one can effectively , thought very inefficiently, compute $\QTR{Large}{d}$ by dividing by all values, starting at $\QTR{Large}{1}$ and ending at the least of and

Examples:

______________________________________

21.3 Lemma:

Suppose then .

Proof:

If $\QTR{Large}{d}$ divides both $\QTR{Large}{m}$ and $\QTR{Large}{n}$ it also divides both $\QTR{Large}{n}$ and $\QTR{Large}{r}$ thus the two pair have exactly the same set of common divisors!

______________________________________

21.4 Theorem( Extended Euclidean Algorithm):

Let Using the Algorithm described in the proof below, there exists effectively computable integers $\QTR{Large}{a}$ and $\QTR{Large}{b}$ such that

$\vspace{1pt}$

PROOF: (By induction)

If $\QTR{Large}{m=n}$ the theorem is trivial so for simplicity assume that $\QTR{Large}{m>n>0}$ . Again if $\QTR{Large}{n}$ divides $\QTR{Large}{m}$ the theorem is trivial so assume

$\$ with .

By the lemma above

If $\QTR{Large}{r}_{1}$ divides $\QTR{Large}{n}$ then and .

Otherwise

$\ \QTR{bf}{\ \ }$ with

Again if $\QTR{Large}{r}_{2}$ divides $\QTR{Large}{r}_{1}$ , $\QTR{Large}{r}_{2}$ and and by substitution we have

By induction,we have

and

One finally argues that after at most $\QTR{Large}{n-1}$ steps $\$ since if it is the greatest common divisor. $\QTR{bf}{\ }$

__________

Corollary

Let $\QTR{Large}{m}$ , $\QTR{Large}{n}$ , and $\QTR{Large}{c}$ be integers, then the equation $\QTR{Large}{xm+}$ $\QTR{Large}{yn=}$ $\QTR{Large}{c}$ has integer solutions if and only if divides $\QTR{Large}{c}$ .

PROOF:.

If $\QTR{Large}{xm+}$ $\QTR{Large}{yn=}$ $\QTR{Large}{c}$ , any common divisor of $\QTR{Large}{m}$ and $\QTR{Large}{n}$ , in particular , must divide $\QTR{Large}{c}$ .

If and $\QTR{Large}{am+}$ $\QTR{Large}{bn=}$ $\QTR{Large}{d.}$ Let $\QTR{Large}{ed=}$ $\QTR{Large}{c.}$ Then $\QTR{Large}{eam+}$ $\QTR{Large}{ebn=}$ $\QTR{Large}{ed=c}$

__________

Example:

Applying the Euclidean Algorithm,

Homework Due (Nov 3):

Estimate the number of divisions that it takes to compute using the Euclidean Algorithm .

hint: Assume that $\QTR{Large}{m>n>0}$ , and show

$\vspace{1pt}$

The Steps in the Euclidean Algorithm:

with or

Let then so can be computed in at most

steps. The first step being the computation of

Finally, in terms of $\QTR{Large}{m}$ and $\QTR{Large}{n}$ , can be computed in at most

_______________________________________________________________

21.5 Lemma:

Suppose $\QTR{Large}{p}$ is prime . Suppose $\QTR{Large}{p}$ divides $\QTR{Large}{cd}$ then $\QTR{Large}{p}$ divides $\QTR{Large}{c}$ or $\QTR{Large}{p}$ divides $\QTR{Large}{d}$ .

Proof:

If $\QTR{Large}{p}$ does not divide $\QTR{Large}{c}$ , then . Thus there exists integers $\QTR{Large}{a}$ and $\QTR{Large}{b}$ , such that

Multiplying both sides of the equation by $\QTR{Large}{d}$ we have

Since, by assumption, $\QTR{Large}{p}$ divides $\QTR{Large}{cd,}$ both terms on the left hand side are divisible by $\QTR{Large}{p}$ , hence, so is the right hand side.

_________________________________________________________________

21.6 Theorem:

1. Let $\QTR{Large}{n>0}$ be a natural number then there is a unique set of prime numbers and natural numbers such that

2. Every fraction can be uniquely written as MATH such that

Proof:

1. is a straight forward induction argument using 21.5. Given 1., 2. is immediate

_________________________________________________________________

21.7 Theorem:

There does not exist a rational number $\QTR{Large}{r}$ such that

PROOF:.

Let . Applying 21.6.2. above we may assume Multiplying, we have . Since $\QTR{Large}{2}$ divides we conclude from 21.5 above that $\QTR{Large}{c=2e}$ for some $\QTR{Large}{e.}$

Hence or . Hence as before $\QTR{Large}{d=2f}$ . Thus .