Most of the following is going to be right from Dr. Andrews book. I decided to post the proof the basis representation theorem since it’s important for Euclid’s division lemma. I will include one or two problems at the end Euclid’s Lemma. (I can’t say I’ll have them solved, but I may skip over them for now.)
Anyway, Here we go!
First a few important things:
Corollary 1-1: If and are positive integers and
Proof: Let denote the number of representations of to the base . We must show that always equals .
It is possible that some of the coefficients in a particular representation of are equal to zero. Without affecting the representation, we may exclude terms that are zero. Thus suppose that
where now neither nor equals zero. Then
by Theorem 1-2 with . Thus we see that for each representation of to the base , we can find a representation of . If has another representation to the base , the same procedure will yield a new representation to the base , the same procedure will yield a new representation of . Consequently
It is important to note the inequality (1-2-2) holds even if has no representation because in that case. Inequality (1-2-2) implies the following inequalities:
and, in general, if ,
since by Corollary 1-1, and since clearly has at least one representation (namely, itself), we see that
The extreme entries in this set of inequalities are ones, so that all of the intermediate entries must be equal to . Thus , and Theorem 1-3 is established.
Once a base has been chosen, we can represent any positive integer uniquely as a sume of multiples of powers of :
Okay! Now for Euclid’s Division Lemma. The book will use the basis representation theorem to show proof of this lemma.
Euclid’s Division Lemma (Chapter 2)
In short Euclid’s Division Lemma is a rather basic concept. Whenever you perform division in mathematics you have a dividend, divisor, quotient, and remainder. It has a strong relationship to a certain properties about prime numbers, but that’s not of concern at the moment.
Theorem (2-1) (Euclid’s Division Lemma):
For any integers and , there exists unique integers and such that and
(Now again from the book!)
Proof: Note that we have simply rewritten a division problem in terms of multiplication and addition. In the notation used above, is the dividend; , the divisor; , the quotient; and , the remainder.
If , must be zero, so that .
If , suppose first that . (We shall consider the cases in which and later.) By the basis representation theorem (see above!), has a unique representation to the base , say
If a second pair and existed, we could find a representation for to the base , say
By the uniqueness of the representation of to the base , we see that , , and thus
Consequently, the theorem is true for positive values of .
If , it is easy to verify that is the only possible solution of (2-1-1) with .
If , then , and there exist unique integers and such that.
If , then ; thus we may take and . If , then
and we may take , and .
In either case, and satisfy equation (2-1-1). Uniqueness for negative follows from uniqueness for , which is then positive.
Whew! Okay, I will try to avoid writing so much from the book in future posts, but in this case I felt I couldn’t sum it up any better than the book did. The proofs here are rather lengthy, but I’m sure they will be even longer as I progress through the book.
Here are some problems for thought:
(1) Without assuming Theorem (2-1), prove that for each pair of integers and , there exists some integer for which is positive.
(2) The principle of mathematical induction is equivalent to the following statement called the least-integer principle: Every non-empty set of positive integers has a least element.
Using the least integer principle, define to be the least integer for which is positive. (See (1)). Prove that
If anyone cares to gives these a shot leave a comment. For right now I think I’ll move on to the next part of Chapter 2. “Divisibility” and “The Linear Diophantine Equation”. From there we will finish up with a proof of the “The Fundamental Theorem of Arithmetic”
If you would like to by Dr. Andrews book you can get it here
more on Euclid’s Lemma at Wikipedia