** Next:** Fibonacci Numbers (last year)
** Up:** Basic Number Theory
** Previous:** Definitions
** Contents**

By definition of mod, and for some
. So, by
substitution, , and by the distributive property,
, so
.

By definition of divides, and for some . Substituting, we find
that , so by the definition of divides.

for some integer by definition of . Since and ,
then . If , then , so . Otherwise, , so ,
so we can subtract and factor on the right to get . Since
, then by definition, so .

**Fact 4**
Let

and

be integers, with

. Then there exist
unique integers q and r such that

, where

. This is called
the division algorithm.

Let be the set of all numbers of the form , where is an integer,
such that . If , then let , so has an element.
If , then let , so S has an element. If , then let , so
. Since , then , so . If ,
then , so has an element. If , then
(since ), so has an element. So, is not empty. Now, if
, then for some , and we can let and , so
where , so we are done. So, the other case we have to
consider is if . Then
, so by WOP, S has a least
element . Since , we know that . So, we need to
show that . Assume that and try to arrive at a contradiction
(this is called proof by contradiction). for some since
. Let . So
. Since ,
(by definition of ). So , and , so
. But , so . However, this is not true,
since is the least element in . So, we have arrived at a
contradiction, so our hypothesis was incorrect - so , so
.

**Fact 5**
Let

. Then there exist integers

and

such that

.

Let be the set of all numbers that can be expressed as such that
and are integers and . is not empty, since we can choose
and , so , so is in . Since , by WOP has a least element, which we will call . If we can show
that is the GCD of and , then we will be done, because , so
for some integers and . Now we will show that is the GCD
of and by using the definition of GCD.
**Part 1:** WTS: and .

By the division algorithm, for some and in
such that . We want to show that , so we will assume that
and try to reach a contradiction. Since and ,
we know that . We know (since ). Since , we
can find an and a in such that . We can
substitute in to get
, or
, which
means that . But, , and this contradicts the fact that is the
least element in . So, we conclude that , so , so .
Similarly, .

**Part 2:** WTS: If and then .

By definition of divides, and for some and in
. Since , we can substitute to get , so
, so (by definition of divides), so by Fact 1, .

**Fact 6**
If there exist integers

,

such that

, then

.

Let , so and . So, , so
, so by definition of divides, so .

Since , there exist integers , , such that .
We can write this as , so (by Fact 6), and
since , then .

We know and for some . Since , then
for some by Fact 5. We can multiply by
to get . We can substitute to get , and factor to get
, so by definition of divides.

Since , we know for some . , so for
some . Multiply by c to get , substitute to get
, and factor to get . So, by definition of divides,
.

There exist integers , such that by Fact 5, so
, so , so
, so
(by Fact 6), so .

We will prove this by contradiction. Assume for the sake of contradiction that
there exists a such that and and . Now, assume for
the sake of contradiction that , where and . Then
and . Since , by Fact 2 we can say that
. So, since and and , this is a contradiction to
, and we conclude that . Now, since , by Fact
9, . But, since we know that , this is a contradiction to
. So, , and we conclude that .

This will be proven by weak mathematical induction on .
**Base Case:** Want To Show(WTS): .

Since and , then .

**Induction Step:** Assume .

WTS: .

Since we know that and , we can apply Fact
11 to say that , or .

**Fact 13**
If

, then there exists some

such that

.

There exists such that (by Fact 5), so
, so
. is the integer we were looking for, so
we are done.

By definition of mod, , and since , then (by Fact
9), so
, and we are done.

Since , then for some . Since , then .
Since , then for some . Since , then .
Substituting, we find that , or . Since , it
follows that and . Substituting, we find that .

Since
, then , for some . So,
, so
by definition of mod.

** Next:** Fibonacci Numbers (last year)
** Up:** Basic Number Theory
** Previous:** Definitions
** Contents**
Gregory Stoll
2000-04-08