file.pdf

CHAPTER Numeration 4 Systems and Number Theory 4.1 Early Numeration Systems 4.2 Place-Value Systems 4.3 Different Base Systems 4.4 Ari...

CHAPTER Numeration 4 Systems and Number Theory 4.1 Early Numeration Systems 4.2 Place-Value Systems 4.3 Different Base Systems 4.4 Arithmetic in Different Bases 4.5 Prime Numbers 4.6 Topics from Number Theory W e start this chapter with an examination of several numeration systems. A working knowledge of these numeration systems will enable you better to understand and appreciate the advantages of our current Hindu-Arabic numeration system. The last two sections of this chapter cover prime numbers and topics from the field of number theory. Many of the concepts in number theory are easy to comprehend but difficult, or impossible, to prove. The mathe- matician Karl Friedrich Gauss (1777–1855) remarked that “it is just this which gives the higher arithmetic (number theory) that magical charm which has made it the favorite NUMB science of the greatest mathematicians, not to mention its inexhaustible wealth, wherein ER TH E ORY it so greatly surpasses other parts of mathematics.“ Gauss referred to mathematics as “the queen of the sciences,” and he considered the field of number theory “the queen of mathematics.” There are many unsolved problems in the field of number theory. One unsolved problem, dating from the year 1742, is Goldbach’s Conjecture, which states that every even number greater than 2 can be written as the sum of two prime numbers. This con- jecture has yet to be proved or disproved, despite the efforts of the world’s best mathe- maticians. A British publishing company has recently offered a $1 million prize to the first THE Q UEEN OF MAT HEMAT person who proves or disproves Goldbach’s Conjecture. The company hopes that the ICS prize money will entice young, mathematically talented people to work on the problem. This scenario is similar to the story line in the movie Good Will Hunting, in which a math- ematics problem posted on a bulletin board attracts the attention of a yet-to-be- discovered math genius, played by Matt Damon. For online student resources, visit this textbook’s website at college.cengage.com/pic/ aufmannexcursions2e. 177 178 Chapter 4 Numeration Systems and Number Theory SECTION 4.1 Early Numeration Systems The Egyptian Numeration System In mathematics, symbols that are used to represent numbers are called numerals. A number can be represented by many different numerals. For instance, the concept of “eightness” is represented by each of the following. Hindu-Arabic: 8 Tally: Roman: VIII Chinese: Egyptian: Babylonian: A numeration system consists of a set of numerals and a method of arranging the numerals to represent numbers. The numeration system that most people use today is known as the Hindu-Arabic numeration system. It makes use of the 10 nu- merals 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Before we examine the Hindu-Arabic numera- tion system in detail, it will be helpful to study some of the earliest numeration systems that were developed by the Egyptians, the Romans, and the Chinese. The Egyptian numeration system uses pictorial symbols called hieroglyphics as numerals. The Egyptian hieroglyphic system is an additive system because any given number is written by using numerals whose sum equals the number. Table 4.1 gives the Egyptian hieroglyphics for powers of 10 from one to one million. Table 4.1 Egyptian Hieroglyphics for Powers of 10 Hindu-Arabic Egyptian Description of Numeral Hieroglyphic Hieroglyphic 1 stroke 10 heel bone 100 scroll 1000 lotus flower 10,000 pointing finger 100,000 fish 1,000,000 astonished person To write the number 300, the Egyptians wrote the scroll hieroglyphic three times:. In the Egyptian hieroglyphic system, the order of the hieroglyphics is of no importance. Each of the following Egyptian numerals represents 321. , , ,  4.1 Early Numeration Systems 179 EXAMPLE 1 Write a Numeral Using Egyptian Hieroglyphics Write 3452 using Egyptian hieroglyphics. Solution 3452  3000  400  50  2. Thus the Egyptian numeral for 3452 is CHECK YOUR PROGRESS 1 Write 201,473 using Egyptian hieroglyphics. Solution See page S12. QUESTION Do the Egyptian hieroglyphics and represent the same number? EXAMPLE 2 Evaluate a Numeral Written Using Egyptian Hieroglyphics Write as a Hindu-Arabic numeral. Solution historical note 共2  100,000兲  共3  10,000兲  共2  1000兲  共4  100兲  共1  10兲  共3  1兲  232,413 CHECK YOUR PROGRESS 2 Write as a Hindu-Arabic numeral. Solution See page S12. One of the earliest written documents of mathematics is the Rhind papyrus (see the figure at the left). This tablet was found in Egypt in A.D. 1858, but it is estimated that the writings date back to 1650 B.C. The Rhind papyrus contains A portion of the Rhind 85 mathematical problems. Studying these problems has enabled mathematicians papyrus and historians to understand some of the mathematical procedures used in the early Egyptian numeration system. The Rhind papyrus is named after Alexander Henry Rhind, who The operation of addition with Egyptian hieroglyphics is a simple grouping purchased the papyrus in Egypt process. In some cases the final sum can be simplified by replacing a group of in A.D. 1858. Today the Rhind hieroglyphics by a single hieroglyphic with a larger numeric value. This technique papyrus is preserved in the is illustrated in Example 3. British Museum in London. ANSWER Yes, they both represent 211. 180 Chapter 4 Numeration Systems and Number Theory EXAMPLE 3 Use Egyptian Hieroglyphics to Find a Sum Use Egyptian hieroglyphics to find 2452  1263. Solution The sum is found by combining the hieroglyphics. 2452 + 1263 + Replacing 10 heel bones with one scroll produces or 3715 The sum is 3715. CHECK YOUR PROGRESS 3 Use Egyptian hieroglyphics to find 23,341  10,562. Solution See page S12. In the Egyptian numeration system, subtraction is performed by removing some of the hieroglyphics from the larger numeral. In some cases it is necessary to “borrow,” as shown in the next example. EXAMPLE 4 Use Egyptian Hieroglyphics to Find a Difference Use Egyptian hieroglyphics to find 332,246  101,512. ✔ TAKE NOTE Solution Five scrolls cannot be removed from two scrolls, so one lotus The numerical value of one lotus flower is equivalent to the numerical value of flower is replaced by ten scrolls, 10 scrolls. Thus resulting in a total of twelve scrolls. Now five scrolls can be removed from twelve scrolls. 332,246 − 101,512 − − The difference is 230,734. CHECK YOUR PROGRESS 4 Use Egyptian hieroglyphics to find 61,432  45,121. Solution See page S12.  4.1 Early Numeration Systems 181 MathMatters Early Egyptian Fractions Evidence gained from the Rhind papyrus shows that the Egyptian method of calcu- lating with fractions was much different from the methods we use today. All Egyp- tian fractions 共 except for 3 兲 were represented in terms of unit fractions, which are 2 1 fractions of the form n , for some natural number n  1. The Egyptians wrote these unit fractions by placing an oval over the numeral that represented the denomina- tor. For example, = 1 = 1 3 15 If a fraction was not a unit fraction, then the Egyptians wrote the fraction as the sum of distinct unit fractions. For instance, 2 1 1 was written as the sum of and. 5 3 15 2 1 1 Of course, 5  5  5 , but (for some mysterious reason) the early Egyptian numera- tion system didn’t allow repetitions. The Rhind papyrus includes a table that shows 2 how to write fractions of the form k , where k is an odd number from 5 to 101, in terms of unit fractions. Some of these are listed below. 2 1 1 2 1 1 2 1 1 1        7 4 28 11 6 66 19 12 76 114 Table 4.2 Roman Numerals Hindu-Arabic Roman Numeral Numeral The Roman Numeration System 1 I The Roman numeration system was used in Europe during the reign of the Roman 5 V Empire. Today we still make limited use of Roman numerals on clock faces, on the 10 X cornerstones of buildings, and in numbering the volumes of periodicals and books. 50 L Table 4.2 shows the numerals used in the Roman numeration system. If the Roman 100 C numerals are listed so that each numeral has a larger value than the numeral to its right, then the value of the Roman numeral is found by adding the values of each 500 D numeral. For example, 1000 M CLX  100  50  10  160 If a Roman numeral is repeated two or three times in succession, we add to determine its numerical value. For instance, XX  10  10  20 and CCC  100  100  100  300. Each of the numerals I, X, C, and M may be re- peated up to three times. The numerals V, L, and D are not repeated. Although the Roman numeration system is an additive system, it also incorpo- rates a subtraction property. In the Roman numeration system, the value of a nu- meral is determined by adding the values of the numerals from left to right. However, if the value of a numeral is less than the value of the numeral to its right, the smaller value is subtracted from the next larger value. For instance, VI  5  1  6; however, IV  5  1  4. In the Roman numeration system the only numerals whose values can be subtracted from the value of the numeral to 182 Chapter 4 Numeration Systems and Number Theory historical note the right are I, X, and C. Also, the subtraction of these values is allowed only if the value of the numeral to the right is within two rows as shown in Table 4.2. That is, The Roman numeration system the value of the numeral to be subtracted must be no less than one-tenth of the value evolved over a period of several of the numeral it is to be subtracted from. For instance, XL  40 and XC  90, but years, and thus some Roman nu- XD does not represent 490 because the value of X is less than one-tenth the value of merals displayed on ancient D. To write 490 using Roman numerals, we write CDXC. structures do not adhere to the basic rules given at the right. For A Summary of the Basic Rules Employed in the Roman Numeration System instance, in the Colosseum in Rome (c. A.D. 80), the numeral I  1, V  5, X  10, L  50, C  100, D  500, M  1000 XXVIIII appears above archway 1. If the numerals are listed so that each numeral has a larger value than the 29 instead of the numeral XXIX. numeral to the right, then the value of the Roman numeral is found by adding the values of the numerals. 2. Each of the numerals, I, X, C, and M may be repeated up to three times. The numerals V, L, and D are not repeated. If a numeral is repeated two or three times in succession, we add to determine its numerical value. 3. The only numerals whose values can be subtracted from the value of the numeral to the right are I, X, and C. The value of the numeral to be subtracted must be no less than one-tenth of the value of the numeral to its right. EXAMPLE 5 Evaluate a Roman Numeral Write DCIV as a Hindu-Arabic numeral. Solution Because the value of D is larger than the value of C, we add their numerical values. The value of I is less than the value of V, so we subtract the smaller value from the larger value. Thus DCIV  共DC兲  共IV兲  共500  100兲  共5  1兲  600  4  604 CHECK YOUR PROGRESS 5 Write MCDXLV as a Hindu-Arabic numeral. Solution See page S12. ✔ TAKE NOTE EXAMPLE 6 Write a Hindu-Arabic Numeral as a Roman Numeral The spreadsheet program Excel Write 579 as a Roman numeral. has a function that converts Hindu-Arabic numerals to Roman Solution numerals. In the Edit Formula di- 579  500  50  10  10  9 alogue box, type In Roman numerals 9 is written as IX. Thus 579  DLXXIX.  ROMAN共n兲, where n is the number you wish CHECK YOUR PROGRESS 6 Write 473 as a Roman numeral. to convert to a Roman numeral. Solution See page S12. In the Roman numeration system, a bar over a numeral is used to denote a value 1000 times the value of the numeral. For instance, V  5  1000  5000 IVLXX  共4  1000兲  70  4070  4.1 Early Numeration Systems 183 ✔ TAKE NOTE EXAMPLE 7 Convert Between Roman Numerals and Hindu-Arabic Numerals The method of writing a bar over a numeral should be used only to a. Write IVDLXXII as a Hindu-Arabic numeral. write Roman numerals that b. Write 6125 as a Roman numeral. cannot be written using the Solution basic rules. For instance, the Roman numeral for 2003 is a. IVDLXXII  共IV兲  共DLXXII兲 MMIII, not IIIII.  共4  1000兲  共572兲  4572 b. The Roman numeral 6 is written VI and 125 is written as CXXV. Thus in Roman numerals 6125 is VICXXV. CHECK YOUR PROGRESS 7 a. Write VIICCLIV as a Hindu-Arabic numeral. b. Write 8070 as a Roman numeral. Solution See page S12. Excursion A Rosetta Tablet for the Traditional Chinese Numeration System Most of the knowledge we have gained about early numeration systems has been ob- tained from inscriptions found on ancient tablets or stones. The information provided by these inscriptions has often been difficult to interpret. For several centuries archeologists had little success in interpreting the Egyptian hieroglyphics they had discovered. Then, in 1799, a group of French military engineers discovered a basalt stone near Rosetta in the Nile delta. This stone, which we now call the Rosetta Stone, has an inscription in three scripts: Greek, Egyptian Demotic, and Egyptian hieroglyphic. It was soon discovered that all three scripts contained the same message. The Greek script was easy to translate, and from its translation, clues were uncovered that enabled scholars to translate many of the documents that up to that time had been unreadable. Pretend that you are an archeologist. Your team has just discovered an old tablet that displays Roman numerals and traditional Chinese numerals. It also provides hints in the form of a crossword puzzle about the traditional Chinese numeration system. Study The Rosetta Stone the inscriptions on the following tablet and then complete the Excursion Exercises that follow. (continued) 184 Chapter 4 Numeration Systems and Number Theory Traditional Roman: 1 Chinese: I 2 3 4N II III 5 IV 6 V VI VII Clues In the traditional Chinese VIII numeration system: IX Across X 2. Numerals are arranged in C a vertical _______________. 5. If a numeral is written above a M power of ____ , then their numerical values are multiplied. CCCLIX 6. There is no numeral for ______. Down 1. The total value of a numeral is the ___ of the multiples of the powers of ten and the ones numeral. 3. If there are an odd number of VIICCXLVI numerals, then the bottom numeral represents units or _____. 4. A numeral written above a power of ten has a value from 1 to _____ , inclusive. Excursion Exercises 1. Complete the crossword puzzle shown on the above tablet. 2. Write 26 as a traditional Chinese numeral. 3. Write 357 as a traditional Chinese numeral. 4. Write the Hindu-Arabic numeral given by each of the following traditional Chinese numerals. a. b. (continued)  4.1 Early Numeration Systems 185 5. a. How many Hindu-Arabic numerals are required to write four thousand five hundred twenty-eight? b. How many traditional Chinese numerals are required to write four thousand five hundred twenty-eight? 6. The traditional Chinese numeration system is no longer in use. Give a reason that may have contributed to its demise. Exercise Set 4.1 In Exercises 1 – 12, write each Hindu-Arabic numeral In Exercises 25–32, use Egyptian hieroglyphics to find using Egyptian hieroglyphics. each sum or difference. 1. 46 2. 82 25. 51  43 26. 67  58 3. 103 4. 157 27. 231  435 28. 623  124 5. 2568 6. 3152 29. 83  51 30. 94  23 7. 23,402 8. 15,303 31. 254  198 32. 640  278 9. 65,800 10. 43,217 11. 1,405,203 12. 653,271 In Exercises 33–44, write each Roman numeral as a Hindu- Arabic numeral. In Exercises 13 – 24, write each Egyptian numeral as a Hindu-Arabic numeral. 33. DCL 34. MCX 13. 14. 35. MCDIX 36. MDCCII 15. 16. 37. MCCXL 38. MMDCIV 39. DCCCXL 40. CDLV 17. 18. 41. IXXLIV 42. VIIDXVII 43. XICDLXI 44. IVCCXXI 19. 20. 21. In Exercises 45–56, write each Hindu-Arabic numeral as a Roman numeral. 22. 45. 157 46. 231 47. 542 48. 783 23. 49. 1197 50. 1039 51. 787 52. 1343 24. 53. 683 54. 959 55. 6898 56. 4357 186 Chapter 4 Numeration Systems and Number Theory Egyptian Multiplication The Rhind papyrus contains b. State a reason why you might prefer to use the problems that show a doubling procedure used by the Roman numeration system rather than the Egyp- Egyptians to find the product of two whole numbers. The tian hieroglyphic numeration system. following examples illustrate this doubling procedure. In 66. What is the largest number that can be written using the examples we have used Hindu-Arabic numerals so that Roman numerals without using the bar over a nu- you can concentrate on the doubling procedure and not be meral or the subtraction property? distracted by the Egyptian hieroglyphics. The first exam- ple determines the product 5  27 by computing two suc- cessive doublings of 27 and then forming the sum of the E X P L O R AT I O N S blue numbers in the rows marked with a check. Note that the rows marked with a check show that one 27 is 27 and 67. The Ionic Greek Numeration System The four 27’s is 108. Thus five 27’s is the sum of 27 and 108, Ionic Greek numeration system assigned or 135. numerical values to the letters of the Greek alphabet. Research the Ionic Greek numeration system and write ⻫1 27 double a report that explains this numeration system. Include 2 54 double information about some of the advantages and disad- ⻫4 108 vantages of this system compared with our present 5 135 This sum is the Hindu-Arabic numeration system. product of 5 and 27. 68. Some clock faces display the Roman numeral IV In the next example, we use the Egyptian doubling as IIII. Research this topic and write a few para- procedure to find the product of 35 and 94. Because graphs that explain at least three possible reasons for the sum of 1, 2, and 32 is 35, we add only the blue numbers this variation. in the rows marked with a check to find that 35  94  94  188  3008  3290. ⻫1 94 double ⻫2 188 double 4 376 double 8 752 double 16 1504 double ⻫ 32 3008 35 3290 This sum is the product of 35 and 94. In Exercises 57–64, use the Egyptian doubling procedure 69. The Method of False Position The Rhind to find each product. papyrus (see page 179) contained solutions to several mathematical problems. Some of these solu- 57. 8  63 58. 4  57 tions made use of a procedure called the method of 59. 7  29 60. 9  33 false position. Research the method of false position 61. 17  35 62. 26  43 and write a report that explains this method. In your 63. 23  108 64. 72  215 report, include a specific mathematical problem and its solution by the method of false position. Extensions CRITICAL THINKING 65. a. State a reason why you might prefer to use the Egyptian hieroglyphic numeration sys- tem rather than the Roman numeration system.  4.2 Place-Value Systems 187 SECTION 4.2 Place-Value Systems Expanded Form historical note The most common numeration system used by people today is the Hindu-Arabic numeration system. It is called the Hindu-Arabic system because it was first devel- Abu Ja’far Muhammad oped in India (around A.D. 800) and then refined by the Arabs. It makes use of the ibn Musa al’Khwarizmi 10 symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The reason for the 10 symbols, called digits, (ca. A.D. 790 – 850) Al’Khwarizmi is related to the fact that we have 10 fingers. The Hindu-Arabic numeration system (ălkhwăhrı̆z mee) produced two is also called the decimal system, where the word decimal is a derivation of the Latin important texts. One of these word decem, which means “ten.” texts advocated the use of the One important feature of the Hindu-Arabic numeration system is that it is a Hindu-Arabic numeration system. place-value or positional-value system. This means that the numerical value of each The twelfth century Latin transla- digit in a Hindu-Arabic numeral depends on its place or position in the numeral. tion of this book is called Liber For instance, the 3 in 31 represents 3 tens, whereas the 3 in 53 represents 3 ones. The Algoritmi de Numero Indorum, or Hindu-Arabic numeration system is a base ten numeration system because the Al-Khwarizmi on the Hindu Art of Reckoning. In Europe, the people place values are the powers of 10: who favored the adoption of the... , 105, 104, 103, 102, 101, 100 Hindu-Arabic numeration system became known as algorists The place value associated with the nth digit of a numeral (counting from right to because of Al’Khwarizmi’s Liber left) is 10n1. For instance, in the numeral 7532, the 7 is the fourth digit from the Algoritmi de Numero Indorum right and is in the 1041  103, or thousands’, place. The numeral 2 is the first digit text. The Europeans who opposed from the right and is in the 1011  100, or ones’, place. The indicated sum of each the Hindu-Arabic system were digit of a numeral multiplied by its respective place value is called the expanded called abacists. They advocated form of the numeral. the use of Roman numerals and often performed computations with the aid of an abacus. EXAMPLE 1 Write a Numeral in its Expanded Form Write 4672 in expanded form. Solution 4672  4000  600  70  2  共4  1000兲  共6  100兲  共7  10兲  共2  1兲 The above expanded form can also be written as 共4  103 兲  共6  102 兲  共7  101 兲  共2  100 兲 CHECK YOUR PROGRESS 1 Write 17,325 in expanded form. Solution See page S13. If a number is written in expanded form, it can be simplified to its ordinary decimal form by performing the indicated operations. The Order of Operations Agreement states that we should first perform the exponentiations, then perform the multiplications, and finish by performing the additions. 188 Chapter 4 Numeration Systems and Number Theory EXAMPLE 2 Simplify a Number Written in Expanded Form Simplify: 共2  103兲  共7  102兲  共6  101兲  共3  100兲 Solution 共2  103兲  共7  102兲  共6  101兲  共3  100兲  共2  1000兲  共7  100兲  共6  10兲  共3  1兲  2000  700  60  3  2763 CHECK YOUR PROGRESS 2 Simplify: 共5  104兲  共9  103兲  共2  102兲  共7  101兲  共4  100兲 Solution See page S13. In the next few examples, we make use of the expanded form of a numeral to compute sums and differences. An examination of these examples will help you bet- ter understand the computational algorithms used in the Hindu-Arabic numera- tion system. EXAMPLE 3 Use Expanded Forms to Find a Sum Use expanded forms of 26 and 31 to find their sum. Solution 26  共2  10兲  6  31  共3  10兲  1 共5  10兲  7  50  7  57 CHECK YOUR PROGRESS 3 Use expanded forms to find the sum of 152 and 234. Solution See page S13. ✔ TAKE NOTE If the expanded form of a sum contains one or more powers of 10 that have multipliers larger than 9, then we simplify by rewriting the sum with multipliers From the expanded forms in that are less than or equal to 9. This process is known as carrying. Example 4, note that 12 is 1 ten and 2 ones. The 1 ten is added to the 13 tens, resulting in a total of EXAMPLE 4 Use Expanded Forms to Find a Sum 14 tens. When we add columns Use expanded forms of 85 and 57 to find their sum. of numbers, this is shown as “carry a 1.” Because the 1 is Solution placed in the tens column, we 85  共8  10兲  5 are actually adding 10.  57  共5  10兲  7 1 85 共13  10兲  12  57 共10  3兲  10  10  2 142 100  30  10  2  100  40  2  142  4.2 Place-Value Systems 189 CHECK YOUR PROGRESS 4 Use expanded forms to find the sum of 147 and 329. Solution See page S13. In the next example, we use the expanded forms of numerals to analyze the concept of “borrowing” in a subtraction problem. EXAMPLE 5 Use Expanded Forms to Find a Difference ✔ TAKE NOTE Use the expanded forms of 457 and 283 to find 457  283. Solution From the expanded forms in Example 5, note that we 457  共4  100兲  共5  10兲  7 “borrowed” 1 hundred as 10  283  共2  100兲  共8  10兲  3 tens. This explains how we show borrowing when numbers are At this point, this example is similar to Example 4 in Section 4.1. We cannot remove subtracted using place value 8 tens from 5 tens, so 1 hundred is replaced by 10 tens. form. 457  共4  100兲  共5  10兲  7 4  100  3  100  100 3 4 57 1  共3  100兲  共10  10兲  共5  10兲  7  3  100  10  10  2 83  共3  100兲  共15  10兲  7 1 74 We can now remove 8 tens from 15 tens. 457  共3  100兲  共15  10兲  7  283  共2  100兲  共8  10兲  3  共1  100兲  共7  10兲  4  100  70  4  174 CHECK YOUR PROGRESS 5 Use expanded forms to find the difference 382  157. Solution See page S13. The Babylonian Numeration System The Babylonian numeration system uses a base of 60. The place values in the Baby- lonian system are given in the following table. Table 4.3 Place Values in the Babylonian Numeration System 603 602 601 600   216,000  3600  60 1 The Babylonians recorded their numerals on damp clay using a wedge-shaped stylus. A vertical wedge shape represented one unit and a sideways “vee” shape rep- resented 10 units. 1 10 190 Chapter 4 Numeration Systems and Number Theory To represent a number smaller than 60, the Babylonians used an additive feature similar to that used by the Egyptians. For example, the Babylonian numeral for 32 is For the number 60 and larger numbers, the Babylonians left a small space between groups of symbols to indicate a different place value. This procedure is illustrated in the following example. EXAMPLE 6 Write a Babylonian Numeral as a Hindu-Arabic Numeral Write as a Hindu-Arabic numeral. Solution 1 group of 602 31 groups of 60 25 ones  共1  602兲  共31  60兲  共25  1兲  3600  1860  25  5485 CHECK YOUR PROGRESS 6 Write as a Hindu- Arabic numeral. Solution See page S13. QUESTION In the Babylonian numeration system, does = ? In the next example we illustrate a division process that can be used to convert Hindu-Arabic numerals to Babylonian numerals. EXAMPLE 7 Write a Hindu-Arabic Numeral as a Babylonian Numeral Write 8503 as a Babylonian numeral. Solution The Babylonian numeration system uses place values of 600, 601, 602, 603,.... Evaluating the powers produces 1, 60, 3600, 216,000,... The largest of these powers that is contained in 8503 is 3600. One method of find- ing how many groups of 3600 are in 8503 is to divide 3600 into 8503. Refer to the ANSWER No.  2, whereas  共1  60兲  共1  1兲  61.  4.2 Place-Value Systems 191 first division shown below. Now divide to determine how many groups of 60 are contained in the remainder 1303. 2 21 3600兲8503 60兲1303 7200 120 1303 103 60 43 The above computations show that 8503 consists of 2 groups of 3600 and 21 groups of 60, with 43 left over. Thus 8503  共2  602 兲  共21  60兲  共43  1兲 As a Babylonian numeral, 8503 is written CHECK YOUR PROGRESS 7 Write 12,578 as a Babylonian numeral. Solution See page S13. In Example 8 we find the sum of two Babylonian numerals. If a numeral for any power of 60 is larger than 59, then simplify by decreasing that numeral by 60 and increasing the place value to its left by 1. EXAMPLE 8 Find the Sum of Babylonian Numerals Find the sum: + Solution + = Combine the symbols for each place value. = Take away 60 from the ones’ place and add 1 to the 60s’ place. = Take away 60 from the 60s’ place and add 1 to the 60 2 place. + = CHECK YOUR PROGRESS 8 Find the sum: + Solution See page S13. 192 Chapter 4 Numeration Systems and Number Theory MathMatters Zero as a Placeholder and as a Number When the Babylonian numeration system first began to develop around 1700 B.C., it did not make use of a symbol for zero. The Babylonians merely used an empty space to indicate that a place value was missing. This procedure of “leaving a space” can be confusing. How big is an empty space? Is that one empty space or two empty spaces? Around 300 B.C., the Babylonians started to use the symbol to indicate that a particular place value was missing. For instance, represented 共2  602兲  共11  1兲  7211. In this case the zero placeholder indicates that there are no 60’s. There is evidence that although the Babylonians used the zero place- holder, they did not use the number zero. The Mayan Numeration System The Mayan civilization existed in the Yucatan area of southern Mexico and in Guatemala, Belize, and parts of El Salvador and Honduras. It started as far back as 9000 B.C. and reached its zenith during the period from A.D. 200 to A.D. 900. Among their many accomplishments, the Maya are best known for their complex hiero- glyphic writing system, their sophisticated calendars, and their remarkable numer- ation system. The Maya used three calendars—the solar calendar, the ceremonial calendar, and the Venus calendar. The solar calendar consisted of about 365.24 days. Of these, 360 days were divided into 18 months, each with 20 days. The Mayan numeration system was strongly influenced by this solar calendar, as evidenced by the use of the numbers 18 and 20 in determining place values. See Table 4.4. ✔ TAKE NOTE Table 4.4 Place Values in the Mayan Numeration System Observe that the place values used in the Mayan numeration 18  203 18  202 18  201 201 200 system are not all powers of 20.   144,000  7200  360  20 1 The Mayan numeration system was one of the first systems to use a symbol for zero as a placeholder. The Mayan numeration system used only three symbols. A dot was used to represent 1, a horizontal bar represented 5, and a conch shell repre- sented 0. The following table shows how the Maya used a combination of these three symbols to write the whole numbers from 0 to 19. Note that each numeral contains at most four dots and at most three horizontal bars. Table 4.5 Mayan Numerals 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  4.2 Place-Value Systems 193 To write numbers larger than 19, the Maya used a vertical arrangement with the largest place value at the top. The following example illustrates the process of con- verting a Mayan numeral to a Hindu-Arabic numeral. ✔ TAKE NOTE EXAMPLE 9 Write a Mayan Numeral as a Hindu-Arabic Numeral In the Mayan numeration system, Write each of the following as a Hindu-Arabic numeral. a. b. does not represent 3 because the three dots are not all in the same row. The Mayan numeral Solution a. 10 × 360 = 3600 b. 5 × 7200 = 36,000 represents one group of 20 and 8 × 20 = 160 0 × 360 = 0 two ones, or 22. 11 × 1 = + 11 12 × 20 = 240 3771 3 × 1 = + 3 36,243 CHECK YOUR PROGRESS 9 Write each of the following as a Hindu-Arabic numeral. a. b. Solution See page S13. In the next example, we illustrate how the concept of place value is used to con- vert Hindu-Arabic numerals to Mayan numerals. EXAMPLE 10 Write a Hindu-Arabic Numeral as a Mayan Numeral Write 7495 as a Mayan numeral. Solution The place values used in the Mayan numeration system are 200, 201, 18  201, 18  202, 18  203,... or 1, 20, 360, 7200, 144,000,... 194 Chapter 4 Numeration Systems and Number Theory Removing 1 group of 7200 from 7495 leaves 295. No groups of 360 can be obtained from 295, so we divide 295 by the next smaller place value of 20 to find that 295 equals 14 groups of 20 with 15 left over. 1 14 7200兲7495 20兲295 7200 20 295 95 80 15 Thus 7495  共1  7200兲  共0  360兲  共14  20兲  共15  1兲 In Mayan numerals, 7495 is written as CHECK YOUR PROGRESS 10 Write 11,480 as a Mayan numeral. Solution See page S13. Excursion Subtraction via the Nines Complement and the End-Around Carry In the subtraction 5627  2564  3063, the number 5627 is called the minuend, 2564 is called the subtrahend, and 3063 is called the difference. In the Hindu-Arabic base ten system, subtraction can be performed by a process that involves addition and the nines complement of the subtrahend. The nines complement of a single digit n is the num- ber 9  n. For instance, the nines complement of 3 is 6, the nines complement of 1 is 8, and the nines complement of 0 is 9. The nines complement of a number with more than one digit is the number that is formed by taking the nines complement of each digit. The nines complement of 25 is 74 and the nines complement of 867 is 132. Subtraction by Using the Nines Complement and the End-Around Carry To subtract by using the nines complement: 1. Add the nines complement of the subtrahend to the minuend. 2. Take away 1 from the leftmost digit and add 1 to the units digit. This is referred to as the end-around carry procedure. (continued)  4.2 Place-Value Systems 195 The following example illustrates the process of subtracting 2564 from 5627 by using the nines complement. 5627 Minuend  2564 Subtrahend 5627 Minuend  7435 Replace the subtrahend with the nines complement of the subtrahend and add. 13062 13062 Take away 1 from the leftmost digit and add 1 to  1 the units digit. This is the end-around carry procedure. 3063 Thus 5627  2564 3063 If the subtrahend has fewer digits than the minuend, leading zeros should be in- serted in the subtrahend so that it has the same number of digits as the minuend. This process is illustrated below for 2547  358. 2547 Minuend  358 Subtrahend 2547  0358 Insert a leading zero. 2547 Minuend  9641 Nines complement of subtrahend 12188 12188 Take away 1 from the leftmost digit  1 and add 1 to the units digit. 2189 Verify that 2189 is the correct difference. Excursion Exercises For Exercises 1–6, use the nines complement of the subtrahend to find the indicated difference. 1. 724  351 2. 2405  1608 3. 91,572  7824 4. 214,577  48,231 5. 3,156,782  875,236 6. 54,327,105  7,678,235 7. Explain why the nines complement and the end-around carry procedure produce the correct answer to a subtraction problem. 196 Chapter 4 Numeration Systems and Number Theory Exercise Set 4.2 In Exercises 1–8, write each numeral in its expanded form. 32. 1. 48 2. 93 33. 3. 420 4. 501 5. 6803 6. 9045 34. 7. 10,208 8. 67,482 35. In Exercises 9–16, simplify each expansion. 36. 9. 共4  102兲  共5  101兲  共6  100兲 10. 共7  102兲  共6  101兲  共3  100兲 11. 共5  103 兲  共0  102 兲  共7  101 兲  共6  100 兲 In Exercises 37– 46, write each Hindu-Arabic numeral as a 12. 共3  103兲  共1  102兲  共2  101兲  共8  100兲 Babylonian numeral. 13. 共3  104 兲  共5  103 兲  共4  102 兲  共0  101 兲  37. 42 38. 57 共7  100 兲 39. 128 40. 540 14. 共2  105 兲  共3  104 兲  共0  103 兲  共6  102 兲  41. 5678 42. 7821 共7  101兲  共5  100兲 43. 10,584 44. 12,687 15. 共6  105兲  共8  104兲  共3  103兲  共0  102 兲  共4  101 兲  共0  100 兲 45. 21,345 46. 24,567 16. 共5  107 兲  共3  106 兲  共0  105 兲  共0  104 兲  共7  103 兲  共9  102 兲  共0  101 兲  共2  100 兲 In Exercises 47– 52, find the sum of the Babylonian numerals. In Exercises 17–22, use expanded forms to find each sum. 47. 17. 35  41 18. 42  56 + 19. 257  138 20. 352  461 21. 1023  1458 22. 3567  2651 48. + In Exercises 23–28, use expanded forms to find each difference. 49. 23. 62  35 24. 193  157 + 25. 4725  1362 26. 85,381  64,156 27. 23,168  12,857 28. 59,163  47,956 50. + In Exercises 29–36, write each Babylonian numeral as a Hindu-Arabic numeral. 51. 29. + 30. 52. + 31.  4.3 Different Base Systems 197 In Exercises 53 – 60, write each Mayan numeral as a Extensions Hindu-Arabic numeral. CRITICAL THINKING 53. 54. 69. a. State a reason why you might prefer to use the Babylonian numeration system instead of the Mayan numeration system. 55. 56. b. State a reason why you might prefer to use the Mayan numeration system instead of the Babylon- ian numeration system. 70. Explain why it might be easy to mistake the 57. 58. number 122 for the number 4 when 122 is writ- ten as a Babylonian numeral. E X P L O R AT I O N S 59. 60. 71. A Base Three Numeration System A student has created a base three numeration system. The student has named this numeration system ZUT because Z, U, and T are the symbols used in this sys- tem: Z represents 0, U represents 1, and T represents 2. The place values in this system are:... , 33  27, In Exercises 61– 68, write each Hindu-Arabic numeral as a 32  9, 31  3, 30  1. Mayan numeral. Write each ZUT numeral as a Hindu-Arabic 61. 137 62. 253 numeral. 63. 948 64. 1265 a. TU b. TZT c. UZTT 65. 1693 66. 2728 Write each Hindu-Arabic numeral as a ZUT numeral. 67. 7432 68. 8654 d. 37 e. 87 f. 144 SECTION 4.3 Different Base Systems Converting Non-Base-Ten Numerals to Base Ten ✔ TAKE NOTE Recall that the Hindu-Arabic numeration system is a base ten system because its place values Recall that in the expression... , 105, 104, 103, 102, 101, 100 bn all have 10 as their base. The Babylonian numeration system is a base sixty system b is the base, and n is the because its place values exponent.... , 605, 604, 603, 602, 601, 600 all have 60 as their base. In general, a base b (where b is a natural number greater than 1) numeration system has place values of... , b 5, b 4, b 3, b 2, b 1, b 0 198 Chapter 4 Numeration Systems and Number Theory Many people think that our base ten numeration system was chosen because it is the easiest to use, but this is not the case. In reality most people find it easier to use our base ten system only because they have had a great deal of experience with the base ten system and have not had much experience with non-base-ten systems. In this section, we examine some non-base-ten numeration systems. To reduce the amount of memorization that would be required to learn new symbols for each of these new systems, we will (as far as possible) make use of our familiar Hindu- Arabic symbols. For instance, if we discuss a base four numeration system that requires four basic symbols, then we will use the four Hindu-Arabic symbols 0, 1, 2, and 3 and the place values... , 45, 44, 43, 42, 41, 40 The base eight, or octal, numeration system uses the Hindu-Arabic symbols 0, 1, 2, 3, 4, 5, 6, and 7 and the place values... , 85, 84, 83, 82, 81, 80 To differentiate between bases, we will label each non-base-ten numeral with a ✔ TAKE NOTE subscript that indicates the base. For instance, 23four represents a base four numeral. Because 23four is not equal to If a numeral is written without a subscript, then it is understood that the base is ten. the base ten number 23, it is Thus 23 written without a subscript is understood to be the base ten numeral 23. important not to read 23four as To convert a non-base-ten numeral to base ten, we write the numeral in its “twenty-three.” To avoid expanded form, as shown in the following example. confusion, read 23four as “two three base four.” EXAMPLE 1 Convert to Base Ten Convert 2314five to base ten. Solution In the base five numeration system, the place values are... , 54, 53, 52, 51, 50 The expanded form of 2314five is 2314five  共2  53兲  共3  52兲  共1  51兲  共4  50兲  共2  125兲  共3  25兲  共1  5兲  共4  1兲  250  75  5  4  334 Thus 2314five  334. CHECK YOUR PROGRESS 1 Convert 3156seven to base ten. Solution See page S13. QUESTION Does the notation 26five make sense? ANSWER No. The expression 26five is a meaningless expression because there is no 6 in base five.  4.3 Different Base Systems 199 In base two, which is called the binary numeration system, the place values are the powers of two.... , 27, 26, 25, 24, 23, 22, 21, 20 The binary numeration system uses only the two digits 0 and 1. These binary digits are often called bits. To convert a base two numeral to base ten, write the numeral in its expanded form and then evaluate the expanded form. EXAMPLE 2 Convert to Base Ten Convert 10110111two to base ten. Solution 10110111two  共1  27兲  共0  26兲  共1  25兲  共1  24兲  共0  23兲  共1  22兲  共1  21兲  共1  20兲  共1  128兲  共0  64兲  共1  32兲  共1  16兲  共0  8兲  共1  4兲  共1  2兲  共1  1兲  128  0  32  16  0  4  2  1  183 CHECK YOUR PROGRESS 2 Convert 111000101two to base ten. Solution See page S13. ✔ TAKE NOTE The base twelve numeration system requires 12 distinct symbols. We will use the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, and B as our base twelve numeration system The base twelve numeration symbols. The symbols 0 through 9 have their usual meaning; however, A is used to system is called the duodecimal represent 10 and B to represent 11. system. A group called the Dozenal Society of America advocates the replacement of our EXAMPLE 3 Convert to Base Ten base ten decimal system with the Convert B37twelve to base ten. duodecimal system. If you wish to find out more about this Solution organization, you can contact In the base twelve numeration system, the place values are them at: The Dozenal Society of America, Nassau Community... , 124, 123, 122, 121, 120 College, Garden City, New York. Thus Not surprisingly, the dues are $12 per year and $144 共122  144兲 B37twelve  共11  122兲  共3  121兲  共7  120兲 for a lifetime membership.  1584  36  7  1627 CHECK YOUR PROGRESS 3 Convert A5Btwelve to base ten. Solution See page S14. Computer programmers often write programs that use the base sixteen nu- meration system, which is also called the hexadecimal system. This system uses the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. Table 4.6 shows that A repre- sents 10, B represents 11, C represents 12, D represents 13, E represents 14, and F represents 15. 200 Chapter 4 Numeration Systems and Number Theory Table 4.6 Decimal and EXAMPLE 4 Convert to Base Ten Hexadecimal Equivalents Convert 3E8sixteen to base ten. Base Ten Base Sixteen Solution Decimal Hexadecimal In the base sixteen numeration system the place values are 0 0... , 164, 163, 162, 161, 160 1 1 Thus 2 2 3E8sixteen  共3  162兲  共14  161兲  共8  160兲 3 3  768  224  8 4 4  1000 5 5 6 6 CHECK YOUR PROGRESS 4 Convert C24Fsixteen to base ten. 7 7 8 8 Solution See page S14. 9 9 10 A 11 B 12 C Converting from Base Ten to Another Base 13 D 14 E The most efficient method of converting a number written in base ten to another 15 F base makes use of a successive division process. For example, to convert 219 to base four, divide 219 by 4 and write the quotient 54 and the remainder 3, as shown below. Now divide the quotient 54 by the base to get a new quotient of 13 and a new re- mainder of 2. Continuing the process, divide the quotient 13 by 4 to get a new quo- tient of 3 and a remainder of 1. Because our last quotient, 3, is less than the base, 4, we stop the division process. The answer is given by the last quotient, 3, and the re- mainders, shown in red in the following diagram. That is, 219  3123four. 4 219 4 54 3 4 13 2 3 1 You can understand how the successive division process converts a base ten numeral to another base by analyzing the process. The first division shows there are 54 fours in 219, with 3 ones left over. The second division shows that there are 13 sixteens (two successive divisions by 4 is the same as dividing by 16) in 219, and the remainder 2 indicates that there are 2 fours left over. The last division shows that there are 3 sixty-fours (three successive divisions by 4 is the same as dividing by 64) in 219, and the remainder 1 indicates that there is 1 sixteen left over. In mathemati- cal notation these results are written as follows. 219  共3  64兲  共1  16兲  共2  4兲  共3  1兲  共3  43兲  共1  42兲  共2  41兲  共3  40兲  3123four  4.3 Different Base Systems 201 EXAMPLE 5 Convert a Base Ten Numeral to Another Base Convert 5821 to a. base three and b. base sixteen. Solution a. 3 5821 b. 16 5821 3 1940 1 16 363 13 = Dsixteen 3 646 2 16 22 11 = Bsixteen 3 215 1 1 6 3 71 2 5821 = 16BDsixteen 3 23 2 3 7 2 2 1 5821 = 21222121three CHECK YOUR PROGRESS 5 Convert 1952 to a. base five and b. base twelve. Solution See page S14. MathMatters Music by the Numbers Reflective The binary numeration system is used to encode music on a CD (compact disc). Lands The figure at the left shows the surface of a CD, which consists of flat regions called surface of CD lands and small indentations called pits. As a laser beam tracks along a spiral path, Pits the beam is reflected to a sensor when it shines on a land, but it is not reflected to Enlarged the sensor when it shines on a pit. The sensor interprets a reflection as a 1 and no re- portion of the spiral flection as a 0. As the CD is playing, the sensor receives a series of 1’s and 0’s, which track the CD player converts to music. On a typical CD, the spiral path that the laser fol- lows loops around the disc over 20,000 times and contains about 650 megabytes of Table 4.7 Octal and Binary data. A byte is eight bits, so this amounts to 5,200,000,000 bits, each of which is rep- Equivalents resented by a pit or a land. Octal Binary 0 000 1 001 Converting Directly Between Computer Bases 2 010 3 011 Although computers compute internally by using base two (binary system), humans 4 100 generally find it easier to compute with a larger base. Fortunately, there are easy con- 5 101 version techniques that can be used to convert a base two numeral directly to a base eight (octal) numeral or a base sixteen (hexadecimal) numeral. Before we explain 6 110 the techniques, it will help to become familiar with the information in Table 4.7, 7 111 which shows the eight octal symbols and their binary equivalents. To convert from octal to binary, just replace each octal symbol with its three-bit binary equivalent. 202 Chapter 4 Numeration Systems and Number Theory EXAMPLE 6 Convert Directly from Base Eight to Base Two Convert 5724eight directly to binary form. Solution 5 7 2 4eight ❘❘ ❘❘ ❘❘ ❘❘ 101 111 010 100two 5724eight  101111010100two CHECK YOUR PROGRESS 6 Convert 63210eight directly to binary form. Solution See page S14. Because every group of three binary bits is equivalent to an octal symbol, we can convert from binary directly to octal by breaking a binary numeral into groups of three (from right to left) and replacing each group with its octal equivalent. EXAMPLE 7 Convert Directly from Base Two to Base Eight Convert 11100101two directly to octal form. Solution Starting from the right, break the binary numeral into groups of three. Then replace Table 4.8 Hexadecimal and each group with its octal equivalent. Binary Equivalents This zero was inserted to make a group of three. Hexadecimal Binary 011 100 101two 0 0000 ❘❘ ❘❘ ❘❘ 1 0001 3 4 5eight 2 0010 11100101two  345eight 3 0011 4 0100 CHECK YOUR PROGRESS 7 Convert 111010011100two directly to octal form. 5 0101 Solution See page S14. 6 0110 7 0111 Table 4.8 shows the hexadecimal symbols and their binary equivalents. To con- 8 1000 vert from hexadecimal to binary, replace each hexadecimal symbol with its four-bit 9 1001 binary equivalent. A 1010 EXAMPLE 8 Convert Directly from Base Sixteen to Base Two B 1011 C 1100 Convert BADsixteen directly to binary form. D 1101 Solution E 1110 B A Dsixteen F 1111 ❘❘ ❘❘ ❘❘ 1011 1010 1101two BADsixteen  101110101101two  4.3 Different Base Systems 203 CHECK YOUR PROGRESS 8 Convert C5Asixteen directly to binary form. Solution See page S14. Because every group of four binary bits is equivalent to a hexadecimal symbol, we can convert from binary to hexadecimal by breaking the binary numeral into groups of four (from right to left) and replacing each group with its hexadecimal equivalent. EXAMPLE 9 Convert Directly from Base Two to Base Sixteen Convert 10110010100011two directly to hexadecimal form. Solution Starting from the right, break the binary numeral into groups of four. Replace each group with its hexadecimal equivalent. Insert two zeros to make a group of four. 0010 1100 1010 0011two ❘❘ ❘❘ ❘❘ ❘❘ 2 C A 3 10110010100011two  2CA3sixteen CHECK YOUR PROGRESS 9 Convert 101000111010010two directly to hexadeci- mal form. Solution See page S14. The Double-Dabble Method There is a short cut that can be used to convert a base two numeral to base ten. The advantage of this short cut, called the double-dabble method, is that you can start at the left of the numeral and work your way to the right without first determining the place value of each bit in the base two numeral. EXAMPLE 10 Apply the Double-Dabble Method Use the double-dabble method to convert 1011001two to base ten. Solution Start at the left with the first 1 and move to the right. Every time you pass by a 0, double your current number. Every time you pass by a 1, dabble. Dabbling is ac- complished by doubling your current number and adding 1. 2ⴢ1 2ⴢ2ⴙ1 2ⴢ5ⴙ1 2 ⴢ 11 2 ⴢ 22 2 ⴢ 44 ⴙ 1 double dabble dabble double double dabble 2 5 11 22 44 89 1 0 1 1 0 0 1two As we pass by the final 1 in the units place, we dabble 44 to get 89. Thus 1011001two  89. 204 Chapter 4 Numeration Systems and Number Theory CHECK YOUR PROGRESS 10 Use the double-dabble method to convert 1110010two to base ten. Solution See page S14. Excursion Information Retrieval via a Binary Search To complete this Excursion, you must first construct a set of 31 cards that we refer to as a deck of binary cards. Templates for constructing the cards are available at our website, math.hmco.com/students, under the file name Binary Cards. Use a com- puter to print the templates onto a medium-weight card stock similar to that used for playing cards. Specific directions are provided with the templates. We are living in the information age, but information is not useful if it cannot be retrieved when you need it. The binary numeration system is vital to the retrieval of in- formation. To illustrate the connection between retrieval of information and the binary system, examine the card in the following figure. The card is labeled with the base ten numeral 20, and the holes and notches at the top of the card represent 20 in binary no- tation. A hole is used to indicate a 1 and a notch is used to indicate a 0. In the figure, the card has holes in the third and fifth binary-place-value positions (counting from right to left) and notches cut out of the first, second, and fourth positions. Position Position Position 5 3 1 Position Position 4 2 20 = 1 0 1 0 0 two 20 After you have constructed your deck of binary cards, take a few seconds to shuffle the deck. To find the card labeled with the numeral 20, complete the following process. 1. Use a thin dowel (or the tip of a sharp pencil) to lift out the cards that have a hole in the fifth position. Keep these cards and set the other cards off to the side. 2. From the cards that are kept, use the dowel to lift out the cards with a hole in the fourth position. Set these cards off to the side. 3. From the cards that are kept, use the dowel to lift out the cards that have a hole in the third position. Keep these cards and place the others off to the side. (continued)  4.3 Different Base Systems 205 4. From the cards that are kept, use the dowel to lift out the cards with a hole in the second position. Set these cards off to the side. 5. From the cards that are kept, use the dowel to lift out the card that has a hole in the first position. Set this card off to the side. The card that remains is the card labeled with the numeral 20. You have just completed a binary search. Excursion Exercises The binary numeration system can also be used to implement a sorting procedure. To il- lustrate, shuffle your deck of cards. Use the dowel to lift out the cards that have a hole in the rightmost position. Place these cards, face up, in the back of the other cards. Now use the dowel to lift out the cards that have a hole in the next position to the left. Place these cards, face up, in back of the other cards. Continue this process of lifting out the cards in the next position to the left and placing them in back of the other cards until you have completed the process for all five positions. 1. Examine the numerals on the cards. What do you notice about the order of the numerals? Explain why they are in this order. 2. If you wanted to sort 1000 cards from smallest to largest value by using the binary sort procedure, how many positions (where each position is either a hole or a notch) would be required at the top of each card? How many positions are needed to sort 10,000 cards? 3. Explain why the above sorting procedure cannot be implemented with base three cards. Exercise Set 4.3 In Exercises 1–10, convert the given numeral to base ten. In Exercises 21–28, use expanded forms to convert the given base two numeral to base ten. 1. 243five 2. 145seven 3. 67nine 4. 573eight 21. 1101two 22. 10101two 5. 3154six 6. 735eight 23. 11011two 24. 101101two 7. 13211four 8. 102022three 25. 1100100two 26. 11110101000two 9. B5sixteen 10. 4Atwelve 27. 10001011two 28. 110110101two In Exercises 11–20, convert the given base ten numeral to the indicated base. 11. 267 to base five 12. 362 to base eight In Exercises 29–34, use the double-dabble method to con- vert the given base two numeral to base ten. 13. 1932 to base six 14. 2024 to base four 15. 15,306 to base nine 16. 18,640 to base seven 29. 101001two 30. 1110100two 17. 4060 to base two 18. 5673 to base three 31. 1011010two 32. 10001010two 19. 283 to base twelve 20. 394 to base sixteen 33. 10100111010two 34. 10000000100two 206 Chapter 4 Numeration Systems and Number Theory In Exercises 35 – 46, convert the given numeral to the indi- 53. BEF3sixteen to base two cated base. 54. 6A7B8sixteen to base two 35. 34six to base eight 36. 71eight to base five 55. BA5CFsixteen to base two 37. 878nine to base four 38. 546seven to base six 56. 47134eight to base two 39. 1110two to base five 40. 21200three to base six 57. An Extension There is a procedure that can be 41. 3440eight to base nine 42. 1453six to base eight used to convert a base three numeral directly 43. 56sixteen to base eight 44. 43twelve to base six to base ten without using the expanded form of the numeral. Write an explanation of this procedure, 45. A4twelve to base sixteen which we will call the triple-whipple-zipple method. 46. C9sixteen to base twelve Hint: The method is an extension of the double- dabble method. In Exercises 47–56, convert the given numeral directly (without first converting to base ten) to the indicated base. 58. Determine whether the following statements are true or false. 47. 352eight to base two a. A number written in base two is divisible by 2 if 48. A4sixteen to base two and only if the number ends with a 0. 49. 11001010two to base eight b. In base six, the next counting number after 55six is 50. 111011100101two to base sixteen 100six. 51. 101010001two to base sixteen c. In base sixteen, the next counting number after 52. 56721eight to base two 3BFsixteen is 3C0sixteen. Extensions CRITICAL THINKING The D’ni Numeration System In the computer game Riven, a D’ni numeration system is used. Although the D’ni numeration system is a base twenty-five numera- tion system with 25 distinct numerals, you really need to memorize only the first five numerals, which are shown below. 0 1 2 3 4 The basic D’ni numerals If two D’ni numerals are placed side-by-side, then the numeral on the left is in the twenty-fives’ place and the numeral on the right is in the ones’ place. Thus is the D’ni numeral for 共3  25兲  共2  1兲  77. 59. Convert the following D’ni numeral to base ten. 60. Convert the following D’ni numeral to base ten.  4.3 Different Base Systems 207 Rotating any of the D’ni numerals for 1, 2, 3, and 4 by a 90° counterclockwise rota- tion produces a numeral with a value five times its original value. For instance, rotating the numeral for 1 produces , which is the D’ni numeral for 5, and rotating the numeral for 2 produces , which is the D’ni numeral for 10. 61. Write the D’ni numeral for 15. 62. Write the D’ni numeral for 20. In the D’ni numeration system, explained above, many numerals are obtained by rotating a basic numeral and then overlaying it on one of the basic numerals. For instance, if you rotate the D’ni numeral for 1, you get the numeral for 5. If you then overlay the numeral for 5 on the numeral for 1, you get the numeral for 5  1  6. 5 overlayed on 1 produces 6. 63. Write the D’ni numeral for 8. 64. Write the D’ni numeral for 22. 65. Convert the following D’ni numeral to base ten. 66. Convert the following D’ni numeral to base ten. 67. a. State one advantage of the hexadecimal numeration system over the decimal numeration system. b. State one advantage of the decimal numeration system over the hexadecimal numeration system. 68. a. State one advantage of the D’ni numeration system over the decimal numeration system. b. State one advantage of the decimal numeration system over the D’ni nu- meration system. E X P L O R AT I O N S 69. The ASCII Code ASCII, pronounced ask-key, is an acronym for the American Standard Code for Information Interchange. In this code, each of the characters that can be typed on a computer keyboard is represented by a number. For instance, the letter A is assigned the number 65, which when writ- ten as an 8-bit binary numeral is 01000001. Research the topic of ASCII. Write a report about ASCII and its applications. 70. The Postnet Code The U.S. Postal Service uses a Postnet code to write zip codes  4 on envelopes. The Postnet code is a bar code that is Erin Q. Smith based on the binary numeration system. Postnet code is very useful because 1836 First Avenue it can be read by a machine. Write a few paragraphs that explain how to con- Escondido, CA 92027-4405 vert a zip code  4 to its Postnet code. What is the Postnet code for your zip code  4? 208 Chapter 4 Numeration Systems and Number Theory SECTION 4.4 Arithmetic in Different Bases Addition in Different Bases Most computers and calculators make use of the base two (binary) numeration sys- tem to perform arithmetic compu