Berkeley MATH 74 - TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 15

Unformatted text preview:

MATH 74, TRANSITION TO UPPER DIVISION MATHEMATICSLECTURE 15Spring 2005, MWF 3:00PM - 4:00PM, 6 Evans, CCN: 547891. Base Representation of IntegersWe are all familiar with base-10 representation of integers. When we write the number 10, 647,for example, the digits 1, 0, 6, 4, and 7 stand for the multiples of some power of 10. More precisely,10,647 means 7·100+4·101+6·102+0·103+1·104. Similarly, we have 746 = 4·100+6·101+7·102.In some contexts we might wish to be more precise and write [746]10to denote that the digits 7,4, and 6 are used to represent an integer using base-10 representation. In most contexts, when wedon’t specify the base, it is assumed that we are using base-10 representation.In base-10 representation of integers, the sequence of digits anan−1. . . a1a0withaj∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} stands for the numberPnj=0aj10j. For example, if a0= 6, a1= 4, anda2= 7, then we have [746]10=P2j=0aj10j= a0100+ a1101+ a2102= 4 · 100+ 6 · 101+ 7 · 102.You may also be familiar with base-2 or binary representation of integers. This representation isvery useful in the field of computer science, where numbers have to be represented by bits whichhave only one of two states, 0 or 1. The number [10110010]2means 0 · 20+ 1 · 21+ 0 · 22+ 0 · 23+1 · 24+ 1 · 25+ 0 · 26+ 1 · 27= [2]10+ [16]10+ [32]10+ [128]10= [178]10. In base-2 representation ofintegers, for bj∈ {0, 1} we have [bnbn−1. . . b1b0]2=Pnj=0bj2j.It is easy to convert numbers back and forth from base-10 to binary. The example above showshow to convert a number from binary to base-10. To find the binary representation for the number[39]10, we just express [39]10as a sum of powers of 2. We have [39]10= [32]10+ [4]10+ 210+ 110=25+ 22+ 21+ 20= 1 · 25+ 0 · 24+ 0 · 23+ 1 · 22+ 1 · 21+ 1 · 20= [100111]2.You may also have seen the he xadecimal (base-16) representation of integers. In this rep-resentation, the digits come from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }, and consecu-tive digits are interpreted in base-16. For example [A]16= [10]10, [B]16= [11]10and [4C]16=[C]16· 160+ [4]16· 161= [12]10+ [4 · 16]10= [76]10.We know that when every integer is uniquely determined by it’s base-10 representation. That’swhy we can use base-10 digits to talk about integers without ambiguity. It’s also true that eachinteger is uniquely determined by both its binary (base 2) and its hexadecimal (base 16) represen-tations. It turns out that given any integer b ≥ 2, we can uniquely express each integer as a decimalin base b.The formal expression of the preceeding statement is the content of the Base RepresentationTheorem, stated below.For any b ≥ 2 and for any a ∈ N∗, there is a unique n ∈ N and a unique n + 1-tuple of naturalnumbers d0. . . dnwith (∀j ≤ n)(0 ≤ dj< b) and dn> 0 and a =Pnj=0djbj.More formally, we can express the base representation theorem as follows:(∀b ∈ N2)(∀a ∈ N∗)(∃!n, d0, . . . dn)[(∀j ∈ N : j ≤ n)(0 ≤ dj< n) ∧ dn> 0 ∧ a =nXj=0djbj)]The proof uses strong induction on a, and requires the following lemma: (∀b ∈ N2)(∀a ∈N∗)(∃!m ∈ N)(bm≤ a < bm+1), which you will prove in the homework.Date: Wednesday, February 23, 2005.12 MATH 74, TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 15The proof of the theorem from the lemma follows:Proof. Let b ∈ N2. Let P (a) say (∃!n, d0, . . . dn)[(∀j ∈ N : j ≤ n)(0 ≤ dj< n) ∧ dn> 0 ∧a =Pnj=0djbj)]. Let a ∈ N∗. Assume (∀k ∈ N∗: k < a)(P (k)). We need to show P (a), i.e.(∃!n, d0, . . . dn)[(∀j ∈ N : j ≤ n)(0 ≤ dj< n) ∧ dn> 0 ∧ a =Pnj=0djbj)]. By the lemma, chos em ∈ N with bm≤ a < bm+1. By the division theorem, there is unique q, r ∈ N with a = qbm+ rand 0 ≤ r < bm. (Note that since a ≥ bm, we will always have q > 0). For existence, we’ll handlethe cases r = 0 and r > 0 separately.(1) If r = 0, then choose n = m, choose dn= q, and choose dj= 0 for 0 ≤ j ≤ m. then we have(∀j ∈ N : j ≤ n)(0 ≤ dj< n), and we have dn> 0, and we have a = qbm=Pnj=0djbj). Sothe existence part of P (a) is true.(2) If r > 0, then r < bm≤ a, and r ∈ N∗, so our induction hypothesis applies to r, andP (r) is true. Let t, c0. . . ctbe the unique natural numbers with (∀j ∈ N : j ≤ t)(0 ≤ cj<t) ∧ ct> 0 ∧ r =Ptj=0cjbj)]. Since ct> 0, we have bt≤ ctbt≤ r < bm, which impliest < m. Choose n = m, choose dn= q, choose dj= cjfor 0 ≤ j ≤ t, and choose dj= 0 fort < j < m = n. Then we have (∀j ∈ N : j ≤ n)(0 ≤ dj< n), and we have dn> 0, and wehave a = qbm+ r = qbm+Ptj=0cjbj=Pnj=0djbj. so the existence part of P (a) is true.For uniqueness, let s, e0. . . es∈ N, and assume that (∀j ∈ N : j ≤ s)(0 ≤ ej< s) ∧ es> 0 ∧ a =Psj=0ejbj)]. Since we also have a =Pnj=0djbj, we must havePnj=0djbj−Psj=0ejbj= a − a = 0.Let z = max{s, n}. Then we can re-write the equation above asPzj=0(dj− ej)bj= 0. We want toshow that n = s and ej= djfor every j. Assume that this is not the case. Then then there is agreatest index i ≤ z such that di6= ei. Since the two sums are equal, and dj= ejfor i < j ≤ z, wemust also havePij=0djbj=Pij=0ejbjand soPi−1j=0(dj− ej)bj+ (di− ei)bi= 0. We now havebi≤ |(di− ei)bi| =Pi−1j=0(dj− ej)bj≤Pi−1j=0|(dj− ej)|bj≤Pi−1j=0(b − 1)bj= bi− 1. So bi≤ bi− 1.This is a contradiction. So we conclude that n = s and ej= djfor every j. This completes theuniqueness part of the proof.


View Full Document

Berkeley MATH 74 - TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 15

Download TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 15
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 15 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 15 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?