ARITHMETIC FUNCTION

any mathematical function defined for integers, and dependent upon those properties of the integer itself as a number, in contrast to the algebraic functions or functions of analysis, which depend upon algebraic or limiting operations performed on numbers. Examples of arithmetic functions include the following functions, which associate with each integer n one of the following numbers: (1) the number of divisors of n; (2) the number of ways n can be represented as a sum or product of a specified number of integers; (3) the number of primes (integers not divisible by any number greater than one, except themselves) dividing n (including n itself). Arithmetic functions have applications in number theory, combinatorial analysis, counting, probability, and mathematical analysis, in which they arise as the coefficients of power series. Logarithms Basic principles Logarithms were invented in the early 17th century to speed up calculations, and they were basic in numerical work for more than 300 years. The perfection of the desk calculating machine in the late 19th century and the electronic computer in the 20th has made them obsolete for large-scale computation. The operation and nature of logarithms can be seen from a table characteristic of logarithms (see item 55 ) that identifies with the number 1/2 the logarithm -1, with the number 1 the logarithm 0, with the number 2 the logarithm 1, with the number 4 the logarithm 2, and so forth. Here, the constant 2 raised to any logarithmic power gives the corresponding number. A table of this type can be used for multiplication (and division)the logarithms of the numbers to be multiplied are selected from the table and added, and the number corresponding to the answer is the result of the multiplication. For example, two numbers are taken from the first row and multiplied together; say, 2 8 = 16. The corresponding values in the second row are 1, 3, and 4; hence, when 2 is taken to the 4th power, 16 is yielded. The reason for this is that numbers in the first row are the number 2 to the power of the corresponding number in the second. Thus 1/8 = 2-3, 1 = 20, 8 = 23. In the identity 32 = 25 the number 2 is called the base. The exponent 5 is the logarithm of 32 to the base 2 and is written 5 = log2 32. More generally, the two equations have the same meaning; the first serves to define the second. By this definition y is the logarithm of x to the base b if and only if x = by. The number x is also called the antilogarithm of y to the base b. It is evidently easy to find logarithms of numbers that are simple powers of the base, and there are quite efficient methods for calculating logarithms of all numbers to as many decimal places as desired. Multiplication of any numbers m and n can be accomplished by adding their logarithms; i.e., the logarithm of the product is the sum of the logarithms (see Box 8, item 56). Division of numbers can also be accomplished by subtracting the logarithms: the logarithm of the quotient is the difference of the logarithms (see Box 8, item 57). This is not all; powers and roots can also be found with logarithms. For example, the cube of 4 is 64 (i.e., 43 = 64), and from the table the logarithms of 4 and 64 are 2 and 6. Because 6 = 3 2, the logarithm of 43 can be found by multiplying the logarithm of 4 by 3. Study of the table will verify that the logarithm of a power can be found by multiplying the logarithm of the number by the index p of the power (see Box 8, item 58). Because logarithms transform multiplication into addition, division into subtraction, and the taking of powers into multiplication, it might be guessed that they would transform the taking of square roots into division. This is the case, for example, in computing the square root of 16, its logarithm (which is 4) is divided by 2. The result is 2, which is the logarithm of 4, as expected. In general, the logarithm of a root is the logarithm of the number divided by the index q of the root (see Box 8, item 59). Because n1/2 = 2, square roots are given in the logarithmic form as one-half the logarithm of the number for which the square root is taken to be calculated (see Box 8, item 60). Logarithms work this way because they are exponents; and exponents are added for multiplying, subtracted for dividing, multiplied to take a power, and divided to take a root. These ideas may be expressed as laws of exponents (see Box 8, item 61). The exponents in these equations can be thought of as logarithms. For example, a variable may be expressed as a power of a base (see Box 8, item 62), and another variable may be expressed as a power of the same base. Their product (see Box 8, item 63) is similarly expressible in terms of a sum. Therefore, logbmn = logbm + logbn, the relationship for the addition of logarithms (see Box 8, item 64). Common logarithms The most convenient tables for numerical calculations are those in which the logarithms are to the base 10. These are called common logarithms. They have the advantage that a table of logarithms of numbers between one and 10 can be used to find the logarithms of all other numbers. For example, from tables, log10 2.41 is 0.38202 (this means that 100.38202 is 2.41; fractional powers of 10 can be found and tabulated; see below). The logarithm of 24.1 can then be found because 24.1 is expressible as a number between two and three times 10 (see Box 9, item 65). Because log10 10 = 1, the logarithm of 24.1 is 1.38202. Thus each common logarithm has two parts, an integer and a decimal less than one. The integral part is called the characteristic and is determined by the position of the decimal point in the number. Thus the log of 241.0 is 2.38202 and its characteristic is 2; for 2.41 the characteristic is 0, for 0.241 it is -1, and for 0.00241 it is -3. The decimal part of a common logarithm is called the mantissa and is found from a table of logarithms by disregarding the position of the decimal point in the number. When the characteristic is negative it cannot be written with the minus sign in front of the mantissa without causing confusion. For example, the log of 0.00241 has a mantissa of 0.38202 and characteristic of -3. It cannot be written -3.38202 because it is, in fact, -3 + 0.38202 (not -[3 + 0.38202]). It is customary to write it in the form 3.8202. Number systems and notation The positional principle Just as in language, where infinitely many words can be composed of but a small variety of different characters, so also in arithmetic are numbers, infinitely many of them, composed of but a small variety of numerals. The devising of a scheme whereby an infinitude of things can be represented by means of but a small number of symbols must be ranked among the most important achievements of the human intellect, for without it an advanced development of either language or arithmetic is unimaginable. The key ideas are two: the positional principle (to be described below) and the symbol zero. The idea is so simple, wrote the 18th19th-century mathematician Pierre-Simon, marquis de Laplace, speaking of the positional principle, that this very simplicity is the reason for our not being sufficiently aware how much admiration it deserves. Similarly, the development by the Hindus of India of the direct ancestor of the modern zero has been described as one of the most important events in the history of mathematics. Applied to the construction of numbers, the positional principle operates thus: the sequence of digits srqp is defined to signify a number the magnitude of which is a sum of products involving powers of a number a (see Box 4, item 33), in which a is called the base or radix; that is, the position of each of the coefficients p, q, r, s, is associated, in reverse order to the representation srqp, with the zeroth, first, second, third, powers of the base a. The number of distinct numerals required in this notation is readily seen to be a. Each numeral, when part of a number, can therefore be said to have two values: an intrinsic value, which is simply that signified by the isolated symbol itself; and a local value, which is that possessed by virtue of its position, or location, within the sequence of digits used to express the given number. Positional systems in history Systems are called binary, ternary, quaternary, quinary, senary, septenary, octenary (or octal), nonary, denary (or decimal), undenary, duodecimal, hexadecimal, vigesimal, and sexagesimal, corresponding to values of a = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 16, 20, and 60, respectively. The pair system, in which the counting goes one, two, two and one, two twos, two and two and one, etc., is found among the ethnologically oldest tribes of Australia, in many Papuan languages of Torres Strait and the adjacent coast of New Guinea, among some African Pygmies, and in various South American tribes. Other tribes of Tierra del Fuego and the South American continent use number systems with bases three and four. The quinary scale, or number system with base five, is very old but in pure form seems to be used at present only by speakers of Saraveca, a South American Arawakan language; elsewhere it is combined with the decimal or the vigesimal system, where the base is 20. Similarly, the pure base six scale seems to occur only sparsely in northwest Africa and is otherwise combined with the duodecimal, or base 12, system. In the course of history, the decimal system finally overshadowed all others, and it is now found in all technologically advanced nations but not, for example, in Mexico and Central America, where the number 20 was used in astronomy and thus became firmly entrenched. Nevertheless, there are still many vestiges of other systems, chiefly in commercial and domestic units, where change always meets the resistance of tradition. Thus, 12 occurs as the number of inches in a foot, months in a year, ounces in a pound (troy or apothecaries'), and twice 12 hours in a day; and both dozen and gross measure by 12s. In English the base 20 occurs chiefly in the score (Four score and seven years ago . . . ); in French it survives in the word quatre-vingts (four twenties), for 80; other traces are found in pre-English Celtic, Gaelic, Danish, and Welsh. The number 258,458 expressed in the sexagesimal (base 60) system of the Babylonians and in The Babylonians developed (20003000 BC) a positional system with base 60a sexagesimal system. With such a large base it would be awkward to have unrelated names for the digits 0, 1, , 59, so a simple grouping system to base 10 was used for these numbers. For example, the number 258,458 is written in Figure 3 as it would have appeared in Babylon. The base 60 still occurs in measurement of time and angles. The Babylonians had long used empty spaces to separate one sexagesimal order from the next in written numbers, and special symbols were sometimes employed for this purpose. Similar symbols were eventually used to indicate the absence of certain orders, and they may even have been used by astronomers to indicate fractions. The Mayan vigesimal (base 20) number system. In the course of early Spanish expeditions into Yucatn, it was discovered that the Mayans, at an early but still undated time, had a well-developed positional system, complete with zero symbols (though inconsistencies in the system limited their computational use). Their system seems to have been used primarily for the calendar rather than for commercial or other computation; this is reflected in the fact that, although the base is 20, the third digit from the end does not signify multiples of 202 but of 18 20, thus giving their year a simple number of days. The digits 0, 1, , 19 are, as in the Babylonian, formed by a simple grouping system, in this case to base 5; the groups were written vertically, as in Figure 4. Some ancient symbols for 1 and 10. The earliest numerals of which there is definite record were simple straight marks for the small numbers, with some special form for 10. These symbols appear in Egypt as early as c. 3400 BC and in Mesopotamia as early as c. 3000 BC. These dates long precede the first known inscriptions containing numerals in India (c. 300 BC), China (3rd century BC), and Crete (c. 1200 BC). Some ancient symbols for 1 and 10 are given in Figure 5. This special position occupied by 10 stems from the number of human fingers, of course, and is still evident in modern usage not only in the logical structure of the decimal system but in the English names for the numbers. Thus, eleven comes from Old English endleofan, literally meaning one left , and twelve from twelf, meaning two left; the endings -teen and -ty both refer to 10, of course, and hundred comes originally from a pre-Greek term meaning ten times . Theory of divisors At this point, an interesting development occurs, for, so long as only additions and multiplications are performed with integers, the resulting numbers are invariably themselves integersthat is, numbers of the same kind as their antecedents. This characteristic changes drastically, however, as soon as division is introduced. Performing division leads to results, called quotients or fractions, which surprisingly include numbers of a new kind, namely, rationals that are not integers. These, though arising from the combination of integers, patently constitute a distinct extension of the natural-number and integer concepts as defined above. By means of the application of the division operation, the domain of the natural numbers becomes extended and enriched immeasurably beyond the integers (see below Rational numbers). The preceding illustrates, simply but clearly, one of the proclivities that are often associated with mathematical thought: relatively simple concepts (such as integers), initially based on very concrete operations (for example, counting), are found to be capable of assuming novel meanings and potential uses, extending far beyond the limits of the concept as originally defined. A similar extension of basic concepts, with even more powerful results, will be found with the introduction of irrationals (see below Irrational numbers). A second example of this is presented by the following: Under the primitive definition, with k equal to either zero or a fraction, ak would, at first sight, appear to be utterly devoid of meaning. Clarification is needed before writing a repeated product of either zero factors or a fractional number of factors. Yet, limiting attention to the case k = 0 here (the case of k = fraction will be considered below), a little reflection shows that a0 can, in fact, assume a perfectly precise meaning, coupled with an additional and quite extraordinary property. Since the result of dividing any (nonzero) number by itself is unity, it follows that am am = am-m = a0 = 1. Not only can the definition of ak be extended to include the case k = 0, but the ensuing result also possesses the noteworthy property that it is independent of the particular (nonzero) value of the base a. A similar argument may be given to show that ak is a meaningful expression even when k is negative, namely, a-k = 1/ak. The original concept of exponent is thus broadened to a great extent. Fundamental theory If three positive integers a, b, and c are in the relation ab = c, it is said that a and b are divisors or factors of c, or that a divides c (written a|c), and b divides c. The number c is said to be a multiple of a and a multiple of b. The number 1 is called the unit, and it is clear that 1 is a divisor of every positive integer. If c can be expressed as a product ab in which a and b are positive integers each greater than 1, then c is called composite. A positive integer neither 1 nor composite is called a prime. Thus, 2, 3, 5, 7, 11, 13, 17, 19, are prime numbers. Euclid proved that the number of prime numbers is infinite (Elements, book IX, proposition 20). The fundamental theorem of arithmetic was proved by Gauss in his Disquisitiones Arithmeticae. It states that every composite number can be expressed as a product of prime numbers and that, save for the order in which the factors are written, this representation is unique. This theorem follows rather directly from a theorem of Euclid (Elements, book VII, proposition 30) to the effect that if a prime divides a product, it divides one of its factors, and the fundamental theorem is therefore sometimes credited to Euclid. For every finite set a1, a2, , ak of positive integers, there exists a largest integer d that divides each of these numbers, called their greatest common divisor (GCD). If d = 1, the numbers are said to be relatively prime. There also exists a smallest positive integer m that is a multiple of each of the numbers. This is called their least common multiple (LCM). If p1, p2, , ph are the distinct primes that divide all of the numbers a1, a2, , ak, and if ei is the smallest exponent to which pi occurs in any of them, then (see Box 2, item 10) the product of the powers formed with typical number pi as base and ei as exponent is the GCD of a1, a2, , ak. If p1, p2, , pi are the distinct primes that divide any one or more of the numbers a1, a2, , ak, and if ni is the largest exponent to which pi occurs in any of them, then (see Box 2, item 11) the product of the powers formed with typical number pi as base and ni as exponent is the LCM of a1, a2, , ak. An example (see Box 2, item 12) is easily constructed. When only two numbers are involved, the GCD and the LCM combine to give the same product as the product of the original numbers. If a and b are two positive integers, a > b, by means of the division algorithm two integers q and r can be determined such that (see Box 2, item 13) a is the sum of q numbers of magnitude b plus a number r that is less than b. The number q is called the partial quotient (the quotient if r = 0), and r is called the remainder. The GCD of a and b is equal to the GCD of b and r. If the division algorithm is applied successively, a remainder 0 must ultimately appear. The last positive remainder is the GCD of a and b. Thus, if a = 544, b = 119, a simple calculation (see Box 2, item 14) shows that the GCD of 544 and 119 is 17. This process is known as the Euclidean algorithm. By means of it, the GCD can be obtained without first factoring the numbers a and b into prime factors.