2.1 Integers

Don’t laugh even if we start out in First Grade! We begin with the counting numbers: , also known as natural numbers. Zero came a little later, sometime during the Middle Ages. The integers comprise the collection of natural numbers, their corresponding negative numbers, and zero. We can represent these compactly as the set . The mathematician Kronecker thought that: “God invented the integers, all else is the work of man.” It is nevertheless possible to define the integers using various systems of axioms, two possible approaches being associated with the names Peano’s axioms and Zermelo-Fraenkel set theory. Suffice to say, it will be quite adequate for our purposes to rely on intuitive notions of numbers, starting with counting on fingers and toes.

2.2 Primes

An integer divisible only by exactly two integers, itself and 1, is called a prime number. The number 1 is conventionally excluded since it has only one factor. Prime numbers have fascinated mathematicians and others for centuries and many of their properties remain undiscovered. As the great mathematician Euler noted “Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.”

It is a good idea to know the primes less than 100, namely 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. The fundamental theorem of arithmetic states that any positive integer can be represented as a product of primes in exactly one way—not counting different ordering. The primes can thus be considered the “atoms” of integers. Euclid proved that there is no largest prime—they go on forever. The proof runs as follows. Assume that there does exist a largest prime, say, p. Then consider the number

(2.1)

where are all the primes less than p. Clearly P is not divisible by any of . Therefore P must also be prime with . Thus the original assumption must have been false and there is no largest prime number.

There is no general formula or pattern for prime numbers. Their occurrence is seemingly random although they become less frequent as N increases. For large N, the number of primes is approximated by N/ln N. For example, , compared with 25 actual primes . The approximation gets better for larger N. An unsolved question concerns the number of “twin primes” (5 and 7, 17 and 19, 29 and 31, 41 and 43, etc.): is it finite or infinite? Another intriguing issue is the Goldbach conjecture which states that every even number greater than 2 can be written as the sum of two primes (perhaps in several ways). For example, , or . Nobody knows whether this conjecture is universally true or not. Neither a proof nor a counterexample has been found since 1742, when it was first proposed. It is possible that the Goldbach conjecture belongs to the category of propositions that are true but undecidable, in the sense of Gödel’s incompleteness theorem.

Mersenne numbers are integers of the form , where p is prime. Written as binary numbers (see Section 2.7), they appear as strings of 1’s. Mersenne numbers are prime candidates for primality, although most are not. As of 2012, 45 Mersenne primes had been identified, the largest being . This is also the largest known prime number, 12,978,189 digits long.

Why would a practical scientist or engineer be interested in mathematical playthings such as primes? Indeed several computer encryption schemes are based on the fact that finding the prime factors of a large number takes a (so far) impossibly large amount of computer time, whereas multiplying prime numbers is relatively easy. The best known algorithm is RSA (Rivest-Shamir-Adleman) public key encryption. To get a feeling for the underlying principle, factor the number 36,863. After you succeed, check your result by multiplying the two factors. Note how much faster you can do the second computation.

It has been observed that various species of cicadas reappear every 7, 13, or 17 years, periods which are prime numbers. It has been speculated that makes them statistically less vulnerable to their predators, which typically have 2-, 3-, 4-, or 6-year population cycles.

2.3 Divisibility

Positive integers other than 1 which are not prime are called composite numbers. All even integers are divisible by 2 (meaning with no remainder). A number is divisible by 3 if its digital root—the sum of its digits—is divisible by 3. Sometimes you have to do this again to the sum until you get 3, 6, or 9. For example, the digits of 3141592653589793238462643 add up to 111, whose digits, in turn, add up to 3. So the original number is divisible by 3. Divisibility by 9 works much the same way. Keep adding the digits and if you wind up with 9, then it is divisible by 9. For example, 314159265 sums to 36, thence to 9. An equivalent method is called “casting out nines.” Cross out 9, likewise 6 and 3, likewise 4, 3, and 2 and so on.

An integer is divisible by 4 if its last two digits are divisible by 4. Thus 64,752 is divisible by 4 while 64,750 is not. An integer is divisible by 8 if its last three digits are divisible by 8. An integer is divisible by 400 if its last four digits are divisible by 400. Thus 1600 and 2000 are divisible while 1700, 1800, and 1900 are not. According to the Gregorian calendar, this determines whether the cusp year of a century is a leap year: 1900 was not but Y2K was a leap year! Divisibility by 5 is easy—any integer ending in 5 or 0. Divisibility by 10 is even easier—ask any first grader. Divisibility by 6 means an even number divisible by 3.

To determine if a number is divisible by 7, double the last digit, then subtract it from the remaining digits of the number. If you get an answer divisible by 7, then the original number is divisible by 7. You may have to apply the rule repeatedly. For example, to check whether 1316 is divisible by 7, double the last digit: , then subtract the answer from the remaining digits, giving . Do it again for 119. You find . This is divisible by 7, and, therefore, so is 1316.

To test divisibility by 11, take the digits from left to right, alternately adding and subtracting. The original number is divisible by 11 if and only if the resulting number is divisible by 11. For example, for 2189, calculate . This is divisible by 11, and so is 2189. There are complicated procedures for determining divisibility by 13 and 19, which we’ll leave to number theorists to worry about.

2.4 Rational Numbers

A rational number is one that can be expressed as a ratio of two integers, say n/m with . The integers are included among the rational numbers, when n is divisible by m. Also, rational numbers have alternative forms, for example, 2/3 = 4/6 = 6/9, etc. Let us focus on rational numbers reduced to their simplest form, with n and m relatively prime. Every rational number can be represented by a terminating or a periodically repeating decimal. Thus, , and A periodic decimal can be abbreviated using an overline on the repeating sequence, for example, and . Given a repeating decimal, the corresponding rational number can be determined as in the following illustration. Suppose we are given . Multiply this number by 1,000,000 to get

(2.2)

Subtracting x, we eliminate the fractional part:

(2.3)

so that x = 142,857/999,999 = 1/7.

A number that cannot be expressed as a ratio n/m is called irrational. (Irrational here doesn’t mean “insane” but rather not expressible as a ratio.) The most famous irrational is , which did however drive the followers of Pythagoras somewhat insane. To prove the irrationality of , assume, to the contrary, that it is rational. This implies , where n and m are relatively prime. In particular, n and m cannot both be even numbers. Squaring, we obtain

(2.4)

This implies that the square of n is an even number and therefore n itself is even and can be expressed n = p/2, where p is another integer. This implies, in turn, that

(2.5)

By analogous reasoning, m must also be even. But, as we have seen, n and m cannot both be even. Therefore the assumption that is rational must be false. The decimal expansion, , is nonterminating and nonperiodic.

2.5 Exponential Notation

Let’s remind ourselves how very large and very small numbers are most conveniently written using exponential notation. The value of Avogadro’s number , the number of particles in a mole, is well approximated by 602,214,129,000,000,000,000,000. We obviously need a more compact notation. The key is to count how many places we move the decimal point. A decimal point moved n places to the left is represented by the exponent . Analogously, a decimal point moved n places to the right gives the exponent . If the decimal place doesn’t move then we understand . Thus 6 followed by 23 zeros is written . To four significant figures, Avogadro’s number is given by . At the other extreme is the mass of an electron . Counting 31 places to the right, we write this number much more reasonably as , accurate to six significant figures.

This brings us to those handy prefixes for very large and very small quantities, mainly from ancient Greek roots. One gram is a nice unit when you are considering, say, the mass of a dime, 2.268 g. For your body weight, a more convenient unit is the kilogram (kg), equal to if you live in Brunei, Myanmar, Yemen, or the USA). Going in the other direction, 1 milligram (mg) = 10⁻³ g, 1 microgram (μg) = 10⁻⁶ g, 1 nanogram (ng) = 10⁻⁹ g, 1 picogram (pg) = 10⁻¹² g, 1 femtogram (fg) = 10⁻¹⁵ g. You are unlikely to need any further prefixes (although they do go on to atto for , zepto for , and yocto for ). For some really large numbers, million is indicated by the prefix mega (M), billion by giga (G), trillion by tera (T), followed by the more exotic peta (P) for , exa (E) for , zetta (Z) for , and yotta (Y) for . We should note that our British cousins count our billions as “thousand millions,” our trillions as “billions,” and so on, but we all agree on the designations giga, tera, etc.

Most little kids know the sequence of doubled numbers These are, of course, successive powers of 2. Since the internal workings of computers are based on the binary number system, a memory capacity of is conventionally called “1 kb” and a CPU speed of 1024 Hz is “1 kHz.” Likewise multiples of describe 1 megabyte (MB) and 1 megahertz (MHz), while multiples of are used in the measures of 1 gigabyte (GB) and 1 gigahertz (GHz).

2.6 Powers of 10

This is a quick survey on the style of the beautiful book by Philip Morrison and Phylis Morrison, Powers of Ten (Scientific American Library, New York, 1994). It will give you a general feeling for the relative sizes of everything in the Universe. Almost in the middle of this logarithmic scale is the order of magnitude of human dimensions, 1 m, almost literally, “an arm’s length.” Two meters would be the height of a power forward. Moving downward, 1 cm, 1/100th of a meter is approximately the width on one of your fingernails (find out which one and you’ll have a handy little ruler that you will never misplace! While you’re at it, the first joint of one of your fingers should be almost exactly 1 in. long. That’s handy for reading maps that say something like: “scale 1 in. = 100 miles”). is called a millimeter (mm). A dime is 1.25 mm in thickness. is called a micron (μm). It is the size of a small bacterium. is a nanometer (nm), the thickness of a layer of 5–10 atoms. This is a familiar quantity now with the rapid development of nanotechnology. Visible light has wavelength in the range of 400 nm (blue) to 700 nm (red). , called an Ångstrom unit (Å), is a useful measure of atomic dimensions, chemical bond lengths, and X-ray wavelengths. is 1 picometer (pm), sometimes a convenient measure of interatomic distances, with 1 Å = 100 pm. Nucleons (protons and neutrons) are of the order of or 1 femtometer (fm), also called 1 fermi. Electrons and other elementary particles appear to be pointlike in high-energy scattering experiments which have probed down to dimensions of the order of . Smaller dimensions are, at present, out of reach experimentally. Some “theories of everything,” which seek to make quantum theory consistent with general relativity, speculate that at about (the Planck length), space and time themselves become granular. This is also the approximate scale of the fundamental objects in the currently popular superstring theory and M-theory.

Returning to the 1 m realm of everyday experience, we now go in the other direction to larger scales. , about 0.62 mile, can be covered in less than a minute at highway speed. or 1000 km is approximately the width of Texas. is three times the distance to the Moon. takes us out to between the orbits of Jupiter and Saturn. is approximately equal to 1 light year (ly), the distance light will travel in 1 year at a speed of . The closest star to our Sun, Proxima Centauri, is 4.22 ly away. Our galaxy, the Milky Way, is approximately 100,000 ly ( in diameter. The Andromeda galaxy is approximately 2.5 million ly away . Finally, the whole observable Universe is in the range of .

Our journey from the smallest to the largest dimensions of interest to scientists has thus covered over 60 powers of 10.

2.7 Binary Number System

Modern digital computers operate using binary logic. The computer manipulates data expressed as sequences of two possible voltage levels (commonly 0 V for binary 0 and either +3.3 V or +5 V for binary 1). In magnetic storage media, such as hard drives or floppy disks, unmagnetized dots can stand for 0’s and magnetized dots for 1’s.

In the familiar decimal or base-10 number system, a typical number such as 123.45 is explicitly represented by

(2.6)

The base-10 number system probably evolved from the fact that we have 10 fingers. The binary or base-2 number system uses just two digits, 0 and 1. It’s like we use our two hands rather than our fingers to count. A binary number is given by the analog of (2.6)

(2.7)

Here are first few decimal numbers and their binary equivalents:

(2.8)

Some larger binary numbers:

(2.9)

It is common practice to write binaries in groupings of four digits. The length of binary numbers might appear unwieldy compared to their decimal equivalents, but computers like them just fine.

To make binary data more compact, it is sometimes converted to octal notation, using the digits 0–7 to express numbers in base 8. For example, . Even more compact is base-16 hexadecimal notation, augmenting the digits 0–9 by A, B, C, D, E, F for 10 through 15. One hex symbol corresponds very nicely to a cluster of 4 bits. For example, . Decimal-binary-octal-hexadecimal conversions can be done on most scientific calculators.

The term bit is a contraction of binary digit. A convenient unit in computer applications is a grouping of 8 bits, like bbbb bbbb, known as a byte. Each byte can represent up to 256 binary units of information. Since computers can only understand numbers, ASCII (American Standard Code for Information Interchange) is used to represent letters and other nonnumeric characters. For example, ASCII codes 65 to 90 stand for the upper-case letters A to Z, while 97 to 122 stand for lower case a to z. ASCII code 32 stands for a space. As an illustration:

Two binary numbers can be added exactly the way you did it in first grade. It’s easier, in fact, since there are only four sums to remember:

(2.10)

Here’s the binary analog of the addition :

(2.11)

where the “carries” are shown in red. Multiplication is also done analogously. You only need to remember that and you never need to carry a 1. To multiply a binary number by 2, just write another 0 at the end.

A negative number can be represented by interpreting the leftmost bit in a byte as a , leaving 7 bits to represent a magnitude from 0 to 127. A disadvantage of this convention is that +0 (0000 0000) is distinguished from (1000 0000), which might cause difficulty when the computer is making a decision whether two values are equal. A better alternative for encoding negative quantities makes use of the 2’s complement, determined as follows. First flip all the bits, replacing all 0’s by 1’s, and 1’s by 0’s. Then add 1, discarding any overflow (or carry). This is equivalent to subtracting the number from . For example, 19 is binary 0001 0011, so would be represented by 1110 1101. Constructing the 2’s complement can be imagined as winding a binary odometer backward. For example, starting with 0000 0000, one click in reverse would give the reading 1111 1111, which represents . A second click would produce 1111 1110, which is .

Subtraction of a binary number is equivalent to addition of its 2’s complement. For example, for signed 8-bit numbers,

(2.12)

since 256 produces a 1 the 9th bit, which is discarded. 2’s complements can be used as well in multiplication of signed binary numbers.

2.8 Infinity

The mathematical term for the size of a set is cardinality. The set of counting numbers is never-ending and is thus infinite in extent, designated by the symbol . (According to a children’s story, the number 8 once thought it was the biggest possible number. When it found out that even larger numbers existed, it fainted. Since then, the prostrate figure “8” has been used as the symbol for infinity.) Infinity has some strange arithmetic properties including

(2.13)

Infinity is defined in The Hitchhiker’s Guide to the Galaxy as “bigger than the biggest thing ever, and then some, much bigger than that, in fact, really amazingly immense …”

The study of infinite sets was pioneered by Georg Cantor in the 19th century. One remarkable fact is that the cardinality of the counting numbers is equal to that of many of its subsets, for example, the even numbers. The reasoning is that these sets can be matched in a one-to-one correspondence with one another according to the following scheme:

(2.14)

Two sets are said to be in one-to-one correspondence if their members can be paired off in such a way that each member of the first set has exactly one counterpart in the second set and vice versa. Likewise, the set of odd numbers , the set of perfect squares , and the set of all integers can be put into one-to-one correspondence with the natural numbers. Such sets are classified as denumerable or denumerably infinite. The term countable is also used, but generally includes finite sets as well. The cardinality of a denumerable set is represented by the symbol (pronounced “aleph null”). A famous mathematical fable tells of the Hilbert Hotel, which contains a countably infinite number of rooms numbered Then, whatever its occupancy, an arbitrary number of new guests—even a countably infinite number—can be accommodated by appropriately relocating the original guests, say from room number n to room number 2n, thus freeing up all room numbers .

A more general category than the integers are the rational numbers, ratios of integers such as n/m. The integers themselves belong to this category, for example, those cases in which m = 1. Although it might appear that there should be more rational numbers than integers, a remarkable fact is that the cardinality of both sets is equal. This can be shown by arranging the rational numbers in the following two-dimensional array:

(2.15)

We can cross out entries which are “duplicates” of other entries, such as 2/2, 2/4, 3/3, 4/2, etc. This array can be “flattened” into a single list, which can then be matched in one-to-one correspondence with the natural numbers. The rationals therefore have the same cardinality, .

The cardinality of the real numbers involves a higher level of infinity. Real numbers are much more inclusive than rational numbers, containing as well irrational numbers such as and transcendental numbers such as and e (much more on these later). Real numbers can most intuitively be imagined as points on a line. This set of numbers or points is called the continuum, with a cardinality denoted by c. Following is an elegant proof by Cantor to show that c represents a higher order of infinity than . Let us consider just the real numbers in the interval [0, 1]. These can all be expressed as infinitely long decimal fractions of the form If the fraction terminates, as in the case of 0.125, we simply pad the decimal representation with an infinite number of zeros. Our (infinitely long and infinitely wide) list of real numbers can now be written

(2.16)

Let us again presume, encouraged by our earlier successes, that we can put this set into one-to-one correspondence with the set . But it doesn’t work this time—we can find a counterexample. Focus on the digits colored in red. Let us change in the first decimal place to any digit other than , change in the second decimal place to any digit other than , and so on with the rest of the infinite list. The result will be a new decimal fraction that is different from every single real number on the list (2.16). Moreover, there is an infinite number of such exceptions. This contradicts our assumption of a one-to-one correspondence with the natural numbers. Therefore , the cardinality of the real numbers, must represent a higher level of infinity than .

Cantor introduced higher orders of cardinality by defining power sets. These are sets comprising all the possible subsets of a given set. For a set with elements, the power set is of dimension . For example, the power set of {1, 2, 3} is made up of elements:

(2.17)

According to Cantor’s theorem, a power set always has a greater cardinality than the original set. The power set of is denoted by

(2.18)

Incidentally, would belong to the same order of infinity. You should be able to convince yourself from the diagonal argument used above that the real numbers can be represented as a power set of the counting numbers. Therefore, we can set . The continuum hypothesis, conjectured by Cantor, states that there exists no intermediate cardinality between and . Surprisingly, the truth of this proposition is undecidable. The work of Kurt Gödel and Paul Cohen showed that the hypothesis can neither be proved nor disproved using the axioms of Zermelo-Fraenkel set theory, on which the number system is based.

It suffices for most purposes for scientists and engineers to understand that the real numbers, or their geometrical equivalent, the points on a line, are nondenumerably infinite—meaning that they belong to a higher order of infinity than a denumerably infinite set. We thus distinguish between variables that have discrete and continuous ranges. A little free hint on English grammar, even though this is a math book: you can only have less of a continuous quantity (e.g. less money) but fewer of a discrete quantity (e.g. fewer dollars)—despite colloquial usage. Fortunately, however, you can have more of both!

Remarkably, the number of points on a two-dimensional, three-dimensional, or even larger continuum has the same cardinality as the number of points in one dimension. This follows from the idea that ordered pairs , triplets , and larger sets can be arranged into a single list in one-to-one correspondence with a set , analogous to what was done with the rational numbers in the array (2.15).

The next higher transfinite number, assuming the continuum hypothesis is true, would be the cardinality of the power set of , namely . This might represent the totality of possible functions or of geometrical curves.

Infinite sets must be handled with extreme caution, otherwise embarrassing paradoxes can result. Consider, for example, the following “proof” that there are no numbers greater than 2. For every number between 0 and 1 there is a corresponding number between 1 and 2—just add 1. It is also true that for every number x between 0 and 1, there is a corresponding number greater than 1, namely, its reciprocal 1/x. Thus you can argue that every number greater than 1 must lie between 1 and 2, implying that there are no numbers greater than 2! The flaw in the preceding “proof” is the reality that every infinite set can be put into one-to-one correspondence with at least one of its proper subsets.