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

## Facts

Fact 1   If and , then .

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

Fact 2   If and and , then .

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

Fact 3   If , , and , then .

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 .

Fact 7   If , then .

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

Fact 8   If and and , 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.

Fact 9   If and then .

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, .

Fact 10   If , then .

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

Fact 11   If and , then .

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 .

Fact 12   If , then for all .

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.

Fact 14   If , and , then .

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

Fact 15   If and and then .

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 .

Fact 16   If then .

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