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 soPi−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