Why Playing Important Part for Development in Child

At one time, play was what children did while their parents got on with the housework or needed a bit of rest in between chores. Nowadays, the saying that â€Å"play is the child's work† from child psychologists and educators has led parents to believe that play is something that has to be â€Å"worked at† for the success of their children. They seem to think that play must have a purpose, that it has to be time-tabled into their already over-crowded day, or else they did feel guilty for being a ‘bad mother' or an ‘uncaring father. That just kicking a ball around in fun is not good enough any more, they may be selling their children short if they do not give them ‘play with a purpose'. Playing with your child should be as natural as leaves to a tree. The parents are a child's first playmates. They are introduced to the joy of being with each other in an atmosphere of joyful sharing and enjoyment of each other. To a child, any activity that she enjoys i s play. It is her way of preparing herself to appreciate and learn about the world around her.Through play, a child learns about space, about color and sound, textures and smells. By playing with others, she learns to live with her fellow-people and to develop confidence in her ability to think creatively. Often we meet children who have grown up in isolation, who have not learned to play or interact with their peers. They find it difficult to become part of the human race, to enjoy the camaraderie of friendship. It is important for working mother to remember that play does not mean having to throw a ball across a field or dress dolls with your child.Play is an attitude of mind. It is an attitude of the child that says, ‘Hey, this is fun! † whether it be playing with a high-powered radio-controlled car with her father or kneading dough for cookies with her mother. It is an attitude of the parent which can say â€Å"I enjoy being with my child and doing things with herâ € . In addition, play is not necessarily the world of toys. To a child, play exits in the most unexpected places. The drawer of cutlery, the cupboard of ots and pans, the box of wastepaper, cushions on the floor or empty boxes or spools of threads which are all worlds of magic play. Children who are not given a lot of conventional toys create creatively, and will continue to create with pleasure all their lives. In conclusion, to understand the world of play is essential to the working mother who can then enter it whenever she can and be it only now and then. You really should be spending more time playing with your children. Come, play with me!

The Higher Arithmetic – an Introduction to the Theory of Numbers

This page intentionally left blank Now into its eighth edition and with additional material on primality testing, written by J. H. Davenport, The Higher Arithmetic introduces concepts and theorems in a way that does not require the reader to have an in-depth knowledge of the theory of numbers but also touches upon matters of deep mathematical signi? cance. A companion website (www. cambridge. org/davenport) provides more details of the latest advances and sample code for important algorithms. Reviews of earlier editions: ‘. . . the well-known and charming introduction to number theory . . can be recommended both for independent study and as a reference text for a general mathematical audience. ’ European Maths Society Journal ‘Although this book is not written as a textbook but rather as a work for the general reader, it could certainly be used as a textbook for an undergraduate course in number theory and, in the reviewer’s opinion, is far superior for this purpose to any other book in English. ’ Bulletin of the American Mathematical Society THE HIGHER ARITHMETIC AN INTRODUCTION TO THE THEORY OF NUMBERS Eighth edition H. Davenport M. A. , SC. D. F. R. S. late Rouse Ball Professor of Mathematics in the University of Cambridge and Fellow of Trinity College Editing and additional material by James H. Davenport CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www. cambridge. org Information on this title: www. cambridge. org/9780521722360  © The estate of H. Davenport 2008 This publication is in copyright.Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2008 ISBN-13 ISBN-13 978-0-511-45555-1 978-0-521-72236-0 eBook (EBL) paperback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. CONTENTS Introduction I Factorization and the Primes 1. 2. 3. 4. . 6. 7. 8. 9. 10. The laws of arithmetic Proof by induction Prime numbers The fundamental theorem of arithmetic Consequences of the fundamental theorem Euclid’s algorithm Another proof of the fundamental theorem A property of the H. C. F Factorizing a number The series of primes page viii 1 1 6 8 9 12 16 18 19 22 25 31 31 33 35 37 40 41 42 45 46 II Congruences 1. 2. 3. 4. 5. 6. 7. 8. 9. The congruence notation Linear congruences Fermat’s theorem Euler’s function ? (m) Wilson’s theorem Algebraic congruences Congruences to a prime modulus Congr uences in several unknowns Congruences covering all numbers v vi III Quadratic Residues 1. 2. 3. 4. . 6. Primitive roots Indices Quadratic residues Gauss’s lemma The law of reciprocity The distribution of the quadratic residues Contents 49 49 53 55 58 59 63 68 68 70 72 74 77 78 82 83 86 92 94 99 103 103 104 108 111 114 116 116 117 120 122 124 126 128 131 133 IV Continued Fractions 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Introduction The general continued fraction Euler’s rule The convergents to a continued fraction The equation ax ? by = 1 In? nite continued fractions Diophantine approximation Quadratic irrationals Purely periodic continued fractions Lagrange’s theorem Pell’s equation A geometrical interpretation of continued fractionsV Sums of Squares 1. 2. 3. 4. 5. Numbers representable by two squares Primes of the form 4k + 1 Constructions for x and y Representation by four squares Representation by three squares VI Quadratic Forms 1. 2. 3. 4. 5. 6. 7. 8. 9. Introduction Equivalent forms The discriminant The representation of a number by a form Three examples The reduction of positive de? nite forms The reduced forms The number of representations The class-number Contents VII Some Diophantine Equations 1. Introduction 2. The equation x 2 + y 2 = z 2 3. The equation ax 2 + by 2 = z 2 4. Elliptic equations and curves 5.Elliptic equations modulo primes 6. Fermat’s Last Theorem 7. The equation x 3 + y 3 = z 3 + w 3 8. Further developments vii 137 137 138 140 145 151 154 157 159 165 165 168 173 179 185 188 194 199 200 209 222 225 235 237 VIII Computers and Number Theory 1. 2. 3. 4. 5. 6. 7. 8. 9. Introduction Testing for primality ‘Random’ number generators Pollard’s factoring methods Factoring and primality via elliptic curves Factoring large numbers The Dif? e–Hellman cryptographic method The RSA cryptographic method Primality testing revisited Exercises Hints Answers Bibliography IndexINTRODUCTION T he higher arithmetic, or the theory of numbers, is concerned with the properties of the natural numbers 1, 2, 3, . . . . These numbers must have exercised human curiosity from a very early period; and in all the records of ancient civilizations there is evidence of some preoccupation with arithmetic over and above the needs of everyday life. But as a systematic and independent science, the higher arithmetic is entirely a creation of modern times, and can be said to date from the discoveries of Fermat (1601–1665).A peculiarity of the higher arithmetic is the great dif? culty which has often been experienced in proving simple general theorems which had been suggested quite naturally by numerical evidence. ‘It is just this,’ said Gauss, ‘which gives the higher arithmetic that magical charm which has made it the favourite science of the greatest mathematicians, not to mention its inexhaustible wealth, wherein it so greatly surpasses other parts of mathematics. ’ The theory of numbers is generally considered to be the ‘purest’ branch of pure mathematics.It certainly has very few direct applications to other sciences, but it has one feature in common with them, namely the inspiration which it derives from experiment, which takes the form of testing possible general theorems by numerical examples. Such experiment, though necessary in some form to progress in every part of mathematics, has played a greater part in the development of the theory of numbers than elsewhere; for in other branches of mathematics the evidence found in this way is too often fragmentary and misleading.As regards the present book, the author is well aware that it will not be read without effort by those who are not, in some sense at least, mathematicians. But the dif? culty is partly that of the subject itself. It cannot be evaded by using imperfect analogies, or by presenting the proofs in a way viii Introduction ix which may convey the main idea o f the argument, but is inaccurate in detail. The theory of numbers is by its nature the most exact of all the sciences, and demands exactness of thought and exposition from its devotees. The theorems and their proofs are often illustrated by numerical examples.These are generally of a very simple kind, and may be despised by those who enjoy numerical calculation. But the function of these examples is solely to illustrate the general theory, and the question of how arithmetical calculations can most effectively be carried out is beyond the scope of this book. The author is indebted to many friends, and most of all to Professor o Erd? s, Professor Mordell and Professor Rogers, for suggestions and corrections. He is also indebted to Captain Draim for permission to include an account of his algorithm.The material for the ? fth edition was prepared by Professor D. J. Lewis and Dr J. H. Davenport. The problems and answers are based on the suggestions of Professor R. K. Guy. Chapter VIII a nd the associated exercises were written for the sixth edition by Professor J. H. Davenport. For the seventh edition, he updated Chapter VII to mention Wiles’ proof of Fermat’s Last Theorem, and is grateful to Professor J. H. Silverman for his comments. For the eighth edition, many people contributed suggestions, notably Dr J. F. McKee and Dr G. K. Sankaran.Cambridge University Press kindly re-typeset the book for the eighth edition, which has allowed a few corrections and the preparation of an electronic complement: www. cambridge. org/davenport. References to further material in the electronic complement, when known at the time this book went to print, are marked thus:  ¦:0. I FACTORIZATION AND THE PRIMES 1. The laws of arithmetic The object of the higher arithmetic is to discover and to establish general propositions concerning the natural numbers 1, 2, 3, . . . of ordinary arithmetic. Examples of such propositions are the fundamental theorem (I. 4)? hat every nat ural number can be factorized into prime numbers in one and only one way, and Lagrange’s theorem (V. 4) that every natural number can be expressed as a sum of four or fewer perfect squares. We are not concerned with numerical calculations, except as illustrative examples, nor are we much concerned with numerical curiosities except where they are relevant to general propositions. We learn arithmetic experimentally in early childhood by playing with objects such as beads or marbles. We ? rst learn addition by combining two sets of objects into a single set, and later we learn multiplication, in the form of repeated addition.Gradually we learn how to calculate with numbers, and we become familiar with the laws of arithmetic: laws which probably carry more conviction to our minds than any other propositions in the whole range of human knowledge. The higher arithmetic is a deductive science, based on the laws of arithmetic which we all know, though we may never have seen them form ulated in general terms. They can be expressed as follows. ? References in this form are to chapters and sections of chapters of this book. 1 2 The Higher Arithmetic Addition.Any two natural numbers a and b have a sum, denoted by a + b, which is itself a natural number. The operation of addition satis? es the two laws: a+b =b+a (commutative law of addition), (associative law of addition), a + (b + c) = (a + b) + c the brackets in the last formula serving to indicate the way in which the operations are carried out. Multiplication. Any two natural numbers a and b have a product, denoted by a ? b or ab, which is itself a natural number. The operation of multiplication satis? es the two laws ab = ba a(bc) = (ab)c (commutative law of multiplication), (associative law of multiplication).There is also a law which involves operations both of addition and of multiplication: a(b + c) = ab + ac (the distributive law). Order. If a and b are any two natural numbers, then either a is equal to b o r a is less than b or b is less than a, and of these three possibilities exactly one must occur. The statement that a is less than b is expressed symbolically by a < b, and when this is the case we also say that b is greater than a, expressed by b > a. The fundamental law governing this notion of order is that if a b. We propose to investigate the common divisors of a and b.If a is divisible by b, then the common divisors of a and b consist simply of all divisors of b, and there is no more to be said. If a is not divisible by b, we can express a as a multiple of b together with a remainder less than b, that is a = qb + c, where c < b. (2) This is the process of ‘division with a remainder’, and expresses the fact that a, not being a multiple of b, must occur somewhere between two consecutive multiples of b. If a comes between qb and (q + 1)b, then a = qb + c, where 0 < c < b. It follows from the equation (2) that any common divisor of b and c is also a divisor of a.Moreo ver, any common divisor of a and b is also a divisor of c, since c = a ? qb. It follows that the common divisors of a and b, whatever they may be, are the same as the common divisors of b and c. The problem of ? nding the common divisors of a and b is reduced to the same problem for the numbers b and c, which are respectively less than a and b. The essence of the algorithm lies in the repetition of this argument. If b is divisible by c, the common divisors of b and c consist of all divisors of c. If not, we express b as b = r c + d, where d < c. (3)Again, the common divisors of b and c are the same as those of c and d. The process goes on until it terminates, and this can only happen when exact divisibility occurs, that is, when we come to a number in the sequence a, b, c, . . . , which is a divisor of the preceding number. It is plain that the process must terminate, for the decreasing sequence a, b, c, . . . of natural numbers cannot go on for ever. Factorization and the Primes 17 Let us suppose, for the sake of de? niteness, that the process terminates when we reach the number h, which is a divisor of the preceding number g.Then the last two equations of the series (2), (3), . . . are f = vg + h, g = wh. (4) (5) The common divisors of a and b are the same as those of b and c, or of c and d, and so on until we reach g and h. Since h divides g, the common divisors of g and h consist simply of all divisors of h. The number h can be identi? ed as being the last remainder in Euclid’s algorithm before exact divisibility occurs, i. e. the last non-zero remainder. We have therefore proved that the common divisors of two given natural numbers a and b consist of all divisors of a certain number h (the H. C. F. f a and b), and this number is the last non-zero remainder when Euclid’s algorithm is applied to a and b. As a numerical illustration, take the numbers 3132 and 7200 which were used in  §5. The algorithm runs as follows: 7200 = 2 ? 3132 + 936, 3 132 = 3 ? 936 + 324, 936 = 2 ? 324 + 288, 324 = 1 ? 288 + 36, 288 = 8 ? 36; and the H. C. F. is 36, the last remainder. It is often possible to shorten the working a little by using a negative remainder whenever this is numerically less than the corresponding positive remainder. In the above example, the last three steps could be replaced by 936 = 3 ? 324 ? 6, 324 = 9 ? 36. The reason why it is permissible to use negative remainders is that the argument that was applied to the equation (2) would be equally valid if that equation were a = qb ? c instead of a = qb + c. Two numbers are said to be relatively prime? if they have no common divisor except 1, or in other words if their H. C. F. is 1. This will be the case if and only if the last remainder, when Euclid’s algorithm is applied to the two numbers, is 1. ? This is, of course, the same de? nition as in  §5, but is repeated here because the present treatment is independent of that given previously. 8 7. Another proof of t he fundamental theorem The Higher Arithmetic We shall now use Euclid’s algorithm to give another proof of the fundamental theorem of arithmetic, independent of that given in  §4. We begin with a very simple remark, which may be thought to be too obvious to be worth making. Let a, b, n be any natural numbers. The highest common factor of na and nb is n times the highest common factor of a and b. However obvious this may seem, the reader will ? nd that it is not easy to give a proof of it without using either Euclid’s algorithm or the fundamental theorem of arithmetic.In fact the result follows at once from Euclid’s algorithm. We can suppose a > b. If we divide na by nb, the quotient is the same as before (namely q) and the remainder is nc instead of c. The equation (2) is replaced by na = q. nb + nc. The same applies to the later equations; they are all simply multiplied throughout by n. Finally, the last remainder, giving the H. C. F. of na and nb, is nh, wher e h is the H. C. F. of a and b. We apply this simple fact to prove the following theorem, often called Euclid’s theorem, since it occurs as Prop. 30 of Book VII.If a prime divides the product of two numbers, it must divide one of the numbers (or possibly both of them). Suppose the prime p divides the product na of two numbers, and does not divide a. The only factors of p are 1 and p, and therefore the only common factor of p and a is 1. Hence, by the theorem just proved, the H. C. F. of np and na is n. Now p divides np obviously, and divides na by hypothesis. Hence p is a common factor of np and na, and so is a factor of n, since we know that every common factor of two numbers is necessarily a factor of their H. C. F.We have therefore proved that if p divides na, and does not divide a, it must divide n; and this is Euclid’s theorem. The uniqueness of factorization into primes now follows. For suppose a number n has two factorizations, say n = pqr . . . = p q r . . . , where all the numbers p, q, r, . . . , p , q , r , . . . are primes. Since p divides the product p (q r . . . ) it must divide either p or q r . . . . If p divides p then p = p since both numbers are primes. If p divides q r . . . we repeat the argument, and ultimately reach the conclusion that p must equal one of the primes p , q , r , . . . We can cancel the common prime p from the two representations, and start again with one of those left, say q. Eventually it follows that all the primes on the left are the same as those on the right, and the two representations are the same. Factorization and the Primes 19 This is the alternative proof of the uniqueness of factorization into primes, which was referred to in  §4. It has the merit of resting on a general theory (that of Euclid’s algorithm) rather than on a special device such as that used in  §4. On the other hand, it is longer and less direct. 8. A property of the H. C.F From Euclid’s algorithm one can deduce a remarkable property of the H. C. F. , which is not at all apparent from the original construction for the H. C. F. by factorization into primes ( §5). The property is that the highest common factor h of two natural numbers a and b is representable as the difference between a multiple of a and a multiple of b, that is h = ax ? by where x and y are natural numbers. Since a and b are both multiples of h, any number of the form ax ? by is necessarily a multiple of h; and what the result asserts is that there are some values of x and y for which ax ? y is actually equal to h. Before giving the proof, it is convenient to note some properties of numbers representable as ax ? by. In the ? rst place, a number so representable can also be represented as by ? ax , where x and y are natural numbers. For the two expressions will be equal if a(x + x ) = b(y + y ); and this can be ensured by taking any number m and de? ning x and y by x + x = mb, y + y = ma. These numbers x and y will be natura l numbers provided m is suf? ciently large, so that mb > x and ma > y. If x and y are de? ned in this way, then ax ? by = by ? x . We say that a number is linearly dependent on a and b if it is representable as ax ? by. The result just proved shows that linear dependence on a and b is not affected by interchanging a and b. There are two further simple facts about linear dependence. If a number is linearly dependent on a and b, then so is any multiple of that number, for k(ax ? by) = a. kx ? b. ky. Also the sum of two numbers that are each linearly dependent on a and b is itself linearly dependent on a and b, since (ax1 ? by1 ) + (ax2 ? by2 ) = a(x1 + x2 ) ? b(y1 + y2 ). 20 The Higher ArithmeticThe same applies to the difference of two numbers: to see this, write the second number as by2 ? ax2 , in accordance with the earlier remark, before subtracting it. Then we get (ax1 ? by1 ) ? (by2 ? ax2 ) = a(x1 + x2 ) ? b(y1 + y2 ). So the property of linear dependence on a and b is preserved by addition and subtraction, and by multiplication by any number. We now examine the steps in Euclid’s algorithm, in the light of this concept. The numbers a and b themselves are certainly linearly dependent on a and b, since a = a(b + 1) ? b(a), b = a(b) ? b(a ? 1). The ? rst equation of the algorithm was a = qb + c.Since b is linearly dependent on a and b, so is qb, and since a is also linearly dependent on a and b, so is a ? qb, that is c. Now the next equation of the algorithm allows us to deduce in the same way that d is linearly dependent on a and b, and so on until we come to the last remainder, which is h. This proves that h is linearly dependent on a and b, as asserted. As an illustration, take the same example as was used in  §6, namely a = 7200 and b = 3132. We work through the equations one at a time, using them to express each remainder in terms of a and b. The ? rst equation was 7200 = 2 ? 3132 + 936, which tells s that 936 = a ? 2b. The second equation was 3 132 = 3 ? 936 + 324, which gives 324 = b ? 3(a ? 2b) = 7b ? 3a. The third equation was 936 = 2 ? 324 + 288, which gives 288 = (a ? 2b) ? 2(7b ? 3a) = 7a ? 16b. The fourth equation was 324 = 1 ? 288 + 36, Factorization and the Primes which gives 36 = (7b ? 3a) ? (7a ? 16b) = 23b ? 10a. 21 This expresses the highest common factor, 36, as the difference of two multiples of the numbers a and b. If one prefers an expression in which the multiple of a comes ? rst, this can be obtained by arguing that 23b ? 10a = (M ? 10)a ? (N ? 23)b, provided that Ma = N b.Since a and b have the common factor 36, this factor can be removed from both of them, and the condition on M and N becomes 200M = 87N . The simplest choice for M and N is M = 87, N = 200, which on substitution gives 36 = 77a ? 177b. Returning to the general theory, we can express the result in another form. Suppose a, b, n are given natural numbers, and it is desired to ? nd natural numbers x and y such that ax ? by = n. (6) Such an e quation is called an indeterminate equation since it does not determine x and y completely, or a Diophantine equation after Diophantus of Alexandria (third century A . D . , who wrote a famous treatise on arithmetic. The equation (6) cannot be soluble unless n is a multiple of the highest common factor h of a and b; for this highest common factor divides ax ? by, whatever values x and y may have. Now suppose that n is a multiple of h, say, n = mh. Then we can solve the equation; for all we have to do is ? rst solve the equation ax1 ? by1 = h, as we have seen how to do above, and then multiply throughout by m, getting the solution x = mx1 , y = my1 for the equation (6). Hence the linear indeterminate equation (6) is soluble in natural numbers x, y if and only if n is a multiple of h.In particular, if a and b are relatively prime, so that h = 1, the equation is soluble whatever value n may have. As regards the linear indeterminate equation ax + by = n, we have found the condition for it to be soluble, not in natural numbers, but in integers of opposite signs: one positive and one negative. The question of when this equation is soluble in natural numbers is a more dif? cult one, and one that cannot well be completely answered in any simple way. Certainly 22 The Higher Arithmetic n must be a multiple of h, but also n must not be too small in relation to a and b.It can be proved quite easily that the equation is soluble in natural numbers if n is a multiple of h and n > ab. 9. Factorizing a number The obvious way of factorizing a number is to test whether it is divisible by 2 or by 3 or by 5, and so on, using the series of primes. If a number N v is not divisible by any prime up to N , it must be itself a prime; for any composite number has at least two prime factors, and they cannot both be v greater than N . The process is a very laborious one if the number is at all large, and for this reason factor tables have been computed.The most extensive one which is gener ally accessible is that of D. N. Lehmer (Carnegie Institute, Washington, Pub. No. 105. 1909; reprinted by Hafner Press, New York, 1956), which gives the least prime factor of each number up to 10,000,000. When the least prime factor of a particular number is known, this can be divided out, and repetition of the process gives eventually the complete factorization of the number into primes. Several mathematicians, among them Fermat and Gauss, have invented methods for reducing the amount of trial that is necessary to factorize a large number.Most of these involve more knowledge of number-theory than we can postulate at this stage; but there is one method of Fermat which is in principle extremely simple and can be explained in a few words. Let N be the given number, and let m be the least number for which m 2 > N . Form the numbers m 2 ? N , (m + 1)2 ? N , (m + 2)2 ? N , . . . . (7) When one of these is reached which is a perfect square, we get x 2 ? N = y 2 , and consequently N = x 2 ? y 2 = (x ? y)(x + y). The calculation of the numbers (7) is facilitated by noting that their successive differences increase at a constant rate. The identi? ation of one of them as a perfect square is most easily made by using Barlow’s Table of Squares. The method is particularly successful if the number N has a factorization in which the two factors are of about the same magnitude, since then y is small. If N is itself a prime, the process goes on until we reach the solution provided by x + y = N , x ? y = 1. As an illustration, take N = 9271. This comes between 962 and 972 , so that m = 97. The ? rst number in the series (7) is 972 ? 9271 = 138. The Factorization and the Primes 23 subsequent ones are obtained by adding successively 2m + 1, then 2m + 3, and so on, that is, 195, 197, and so on.This gives the series 138, 333, 530, 729, 930, . . . . The fourth of these is a perfect square, namely 272 , and we get 9271 = 1002 ? 272 = 127 ? 73. An interesting algorithm for fact orization has been discovered recently by Captain N. A. Draim, U . S . N. In this, the result of each trial division is used to modify the number in preparation for the next division. There are several forms of the algorithm, but perhaps the simplest is that in which the successive divisors are the odd numbers 3, 5, 7, 9, . . . , whether prime or not. To explain the rules, we work a numerical example, say N = 4511. The ? st step is to divide by 3, the quotient being 1503 and the remainder 2: 4511 = 3 ? 1503 + 2. The next step is to subtract twice the quotient from the given number, and then add the remainder: 4511 ? 2 ? 1503 = 1505, 1505 + 2 = 1507. The last number is the one which is to be divided by the next odd number, 5: 1507 = 5 ? 301 + 2. The next step is to subtract twice the quotient from the ? rst derived number on the previous line (1505 in this case), and then add the remainder from the last line: 1505 ? 2 ? 301 = 903, 903 + 2 = 905. This is the number which is to be divi ded by the next odd number, 7. Now we an continue in exactly the same way, and no further explanation will be needed: 905 = 7 ? 129 + 2, 903 ? 2 ? 129 = 645, 645 ? 2 ? 71 = 503, 503 ? 2 ? 46 = 411, 645 + 2 = 647, 503 + 8 = 511, 411 + 5 = 416, 647 = 9 ? 71 + 8, 511 = 11 ? 46 + 5, 416 = 13 ? 32 + 0. 24 The Higher Arithmetic We have reached a zero remainder, and the algorithm tells us that 13 is a factor of the given number 4511. The complementary factor is found by carrying out the ? rst half of the next step: 411 ? 2 ? 32 = 347. In fact 4511 = 13? 347, and as 347 is a prime the factorization is complete. To justify the algorithm generally is a matter of elementary algebra.Let N1 be the given number; the ? rst step was to express N1 as N1 = 3q1 + r1 . The next step was to form the numbers M2 = N1 ? 2q1 , The number N2 was divided by 5: N2 = 5q2 + r2 , and the next step was to form the numbers M3 = M2 ? 2q2 , N 3 = M3 + r 2 , N 2 = M2 + r 1 . and so the process was continued. It can be deduced from these equations that N2 = 2N1 ? 5q1 , N3 = 3N1 ? 7q1 ? 7q2 , N4 = 4N1 ? 9q1 ? 9q2 ? 9q3 , and so on. Hence N2 is divisible by 5 if and only if 2N1 is divisible by 5, or N1 divisible by 5. Again, N3 is divisible by 7 if and only if 3N1 is divisible by 7, or N1 divisible by 7, and so on.When we reach as divisor the least prime factor of N1 , exact divisibility occurs and there is a zero remainder. The general equation analogous to those given above is Nn = n N1 ? (2n + 1)(q1 + q2 +  ·  ·  · + qn? 1 ). The general equation for Mn is found to be Mn = N1 ? 2(q1 + q2 +  ·  ·  · + qn? 1 ). (9) If 2n + 1 is a factor of the given number N1 , then Nn is exactly divisible by 2n + 1, and Nn = (2n + 1)qn , whence n N1 = (2n + 1)(q1 + q2 +  ·  ·  · + qn ), (8) Factorization and the Primes by (8). Under these circumstances, we have, by (9), Mn+1 = N1 ? 2(q1 + q2 +  ·  ·  · + qn ) = N1 ? 2 n 2n + 1 N1 = N1 . n + 1 25 Thus the complementary factor to the factor 2n + 1 is Mn+1 , as stated in the example. In the numerical example worked out above, the numbers N1 , N2 , . . . decrease steadily. This is always the case at the beginning of the algorithm, but may not be so later. However, it appears that the later numbers are always considerably less than the original number. 10. The series of primes Although the notion of a prime is a very natural and obvious one, questions concerning the primes are often very dif? cult, and many such questions are quite unanswerable in the present state of mathematical knowledge.We conclude this chapter by mentioning brie? y some results and conjectures about the primes. In  §3 we gave Euclid’s proof that there are in? nitely many primes. The same argument will also serve to prove that there are in? nitely many primes of certain speci? ed forms. Since every prime after 2 is odd, each of them falls into one of the two progressions (a) 1, 5, 9, 13, 17, 21, 25, . . . , (b) 3, 7, 11, 15, 19, 23, 27, . . . ; the progression (a) consisting of all numbers of the form 4x + 1, and the progression (b) of all numbers of the form 4x ? 1 (or 4x + 3, which comes to the same thing).We ? rst prove that there are in? nitely many primes in the progression (b). Let the primes in (b) be enumerated as q1 , q2 , . . . , beginning with q1 = 3. Consider the number N de? ned by N = 4(q1 q2 . . . qn ) ? 1. This is itself a number of the form 4x ? 1. Not every prime factor of N can be of the form 4x + 1, because any product of numbers which are all of the form 4x + 1 is itself of that form, e. g. (4x + 1)(4y + 1) = 4(4x y + x + y) + 1. Hence the number N has some prime factor of the form 4x ? 1. This cannot be any of the primes q1 , q2 , . . . , qn , since N leaves the remainder ? when 26 The Higher Arithmetic divided by any of them. Thus there exists a prime in the series (b) which is different from any of q1 , q2 , . . . , qn ; and this proves the proposition. The same argument cannot be used to prove t hat there are in? nitely many primes in the series (a), because if we construct a number of the form 4x +1 it does not follow that this number will necessarily have a prime factor of that form. However, another argument can be used. Let the primes in the series (a) be enumerated as r1 , r2 , . . . , and consider the number M de? ned by M = (r1 r2 . . rn )2 + 1. We shall see later (III. 3) that any number of the form a 2 + 1 has a prime factor of the form 4x + 1, and is indeed entirely composed of such primes, together possibly with the prime 2. Since M is obviously not divisible by any of the primes r1 , r2 , . . . , rn , it follows as before that there are in? nitely many primes in the progression (a). A similar situation arises with the two progressions 6x + 1 and 6x ? 1. These progressions exhaust all numbers that are not divisible by 2 or 3, and therefore every prime after 3 falls in one of these two progressions.One can prove by methods similar to those used above that there ar e in? nitely many primes in each of them. But such methods cannot cope with the general arithmetical progression. Such a progression consists of all numbers ax +b, where a and b are ? xed and x = 0, 1, 2, . . . , that is, the numbers b, b + a, b + 2a, . . . . If a and b have a common factor, every number of the progression has this factor, and so is not a prime (apart from possibly the ? rst number b). We must therefore suppose that a and b are relatively prime. It then seems plausible that the progression will contain in? itely many primes, i. e. that if a and b are relatively prime, there are in? nitely many primes of the form ax + b. Legendre seems to have been the ? rst to realize the importance of this proposition. At one time he thought he had a proof, but this turned out to be fallacious. The ? rst proof was given by Dirichlet in an important memoir which appeared in 1837. This proof used analytical methods (functions of a continuous variable, limits, and in? nite series), an d was the ? rst really important application of such methods to the theory of numbers.It opened up completely new lines of development; the ideas underlying Dirichlet’s argument are of a very general character and have been fundamental for much subsequent work applying analytical methods to the theory of numbers. Factorization and the Primes 27 Not much is known about other forms which represent in? nitely many primes. It is conjectured, for instance, that there are in? nitely many primes of the form x 2 + 1, the ? rst few being 2, 5, 17, 37, 101, 197, 257, . . . . But not the slightest progress has been made towards proving this, and the question seems hopelessly dif? cult.Dirichlet did succeed, however, in proving that any quadratic form in two variables, that is, any form ax 2 + bx y + cy 2 , in which a, b, c are relatively prime, represents in? nitely many primes. A question which has been deeply investigated in modern times is that of the frequency of occurrence of the p rimes, in other words the question of how many primes there are among the numbers 1, 2, . . . , X when X is large. This number, which depends of course on X , is usually denoted by ? (X ). The ? rst conjecture about the magnitude of ? (X ) as a function of X seems to have been made independently by Legendre and Gauss about X 1800.It was that ? (X ) is approximately log X . Here log X denotes the natural (so-called Napierian) logarithm of X , that is, the logarithm of X to the base e. The conjecture seems to have been based on numerical evidence. For example, when X is 1,000,000 it is found that ? (1,000,000) = 78,498, whereas the value of X/ log X (to the nearest integer) is 72,382, the ratio being 1. 084 . . . . Numerical evidence of this kind may, of course, be quite misleading. But here the result suggested is true, in the sense that the ratio of ? (X ) to X/ log X tends to the limit 1 as X tends to in? ity. This is the famous Prime Number Theorem, ? rst proved by Hadamard and de la Vall? e e Poussin independently in 1896, by the use of new and powerful analytical methods. It is impossible to give an account here of the many other results which have been proved concerning the distribution of the primes. Those proved in the nineteenth century were mostly in the nature of imperfect approaches towards the Prime Number Theorem; those of the twentieth century included various re? nements of that theorem. There is one recent event to which, however, reference should be made.We have already said that the proof of Dirichlet’s Theorem on primes in arithmetical progressions and the proof of the Prime Number Theorem were analytical, and made use of methods which cannot be said to belong properly to the theory of numbers. The propositions themselves relate entirely to the natural numbers, and it seems reasonable that they should be provable without the intervention of such foreign ideas. The search for ‘elementary’ proofs of these two theorems was u nsuccessful until fairly recently. In 1948 A. Selberg found the ? rst elementary proof of Dirichlet’s Theorem, and with 28 The Higher Arithmetic he help of P. Erd? s he found the ? rst elementary proof of the Prime Numo ber Theorem. An ‘elementary’ proof, in this connection, means a proof which operates only with natural numbers. Such a proof is not necessarily simple, and indeed both the proofs in question are distinctly dif? cult. Finally, we may mention the famous problem concerning primes which was propounded by Goldbach in a letter to Euler in 1742. Goldbach suggested (in a slightly different wording) that every even number from 6 onwards is representable as the sum of two primes other than 2, e. g. 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 + 5, 12 = 5 + 7, . . . Any problem like this which relates to additive properties of primes is necessarily dif? cult, since the de? nition of a prime and the natural properties of primes are all expressed in terms of multiplic ation. An important contribution to the subject was made by Hardy and Littlewood in 1923, but it was not until 1930 that anything was rigorously proved that could be considered as even a remote approach towards a solution of Goldbach’s problem. In that year the Russian mathematician Schnirelmann proved that there is some number N such that every number from some point onwards is representable as the sum of at most N primes.A much nearer approach was made by Vinogradov in 1937. He proved, by analytical methods of extreme subtlety, that every odd number from some point onwards is representable as the sum of three primes. This was the starting point of much new work on the additive theory of primes, in the course of which many problems have been solved which would have been quite beyond the scope of any pre-Vinogradov methods. A recent result in connection with Goldbach’s problem is that every suf? ciently large even number is representable as the sum of two numbers, one of which is a prime and the other of which has at most two prime factors.Notes Where material is changing more rapidly than print cycles permit, we have chosen to place some of the material on the book’s website: www. cambridge. org/davenport. Symbols such as  ¦I:0 are used to indicate where there is such additional material.  §1. The main dif? culty in giving any account of the laws of arithmetic, such as that given here, lies in deciding which of the various concepts should come ? rst. There are several possible arrangements, and it seems to be a matter of taste which one prefers. It is no part of our purpose to analyse further the concepts and laws of ? rithmetic. We take the commonsense (or na? ve) view that we all ‘know’ Factorization and the Primes 29 the natural numbers, and are satis? ed of the validity of the laws of arithmetic and of the principle of induction. The reader who is interested in the foundations of mathematics may consult Bertrand Russe ll, Introduction to Mathematical Philosophy (Allen and Unwin, London), or M. Black, The Nature of Mathematics (Harcourt, Brace, New York). Russell de? nes the natural numbers by selecting them from numbers of a more general kind. These more general numbers are the (? ite or in? nite) cardinal numbers, which are de? ned by means of the more general notions of ‘class’ and ‘one-to-one correspondence’. The selection is made by de? ning the natural numbers as those which possess all the inductive properties. (Russell, loc. cit. , p. 27). But whether it is reasonable to base the theory of the natural numbers on such a vague and unsatisfactory concept as that of a class is a matter of opinion. ‘Dolus latet in universalibus’ as Dr Johnson remarked.  §2. The objection to using the principle of induction as a de? ition of the natural numbers is that it involves references to ‘any proposition about a natural number n’. It seems plain the th at ‘propositions’ envisaged here must be statements which are signi? cant when made about natural numbers. It is not clear how this signi? cance can be tested or appreciated except by one who already knows the natural numbers.  §4. I am not aware of having seen this proof of the uniqueness of prime factorization elsewhere, but it is unlikely that it is new. For other direct proofs, see Mathews, p. 2, or Hardy and Wright, p. 21.?  §5. It has been shown by (intelligent! computer searches that there is no odd perfect number less than 10300 . If an odd perfect number exists, it has at least eight distinct prime factors, of which the largest exceeds 108 . For references and other information on perfect or ‘nearly perfect’ numbers, see Guy, sections A. 3, B. 1 and B. 2.  ¦I:1  §6. A critical reader may notice that in two places in this section I have used principles that were not explicitly stated in  §Ã‚ §1 and 2. In each place, a proof by induction co uld have been given, but to have done so would have distracted the reader’s attention from the main issues.The question of the length of Euclid’s algorithm is discussed in Uspensky and Heaslet, ch. 3, and D. E. Knuth’s The Art of Computer Programming vol. II: Seminumerical Algorithms (Addison Wesley, Reading, Mass. , 3rd. ed. , 1998) section 4. 5. 3.  §9. For an account of early methods of factoring, see Dickson’s History Vol. I, ch. 14. For a discussion of the subject as it appeared in ? Particulars of books referred to by their authors’ names will be found in the Bibliography. 30 The Higher Arithmetic the 1970s see the article by Richard K. Guy, ‘How to factor a number’, Congressus Numerantium XVI Proc. th Manitoba Conf. Numer. Math. , Winnipeg, 1975, 49–89, and at the turn of the millennium see Richard P. Brent, ‘Recent progress and prospects for integer factorisation algorithms’, Springer Lecture Notes in Comp uter Science 1858 Proc. Computing and Combinatorics, 2000, 3–22. The subject is discussed further in Chapter VIII. It is doubtful whether D. N. Lehmer’s tables will ever be extended, since with them and a pocket calculator one can easily check whether a 12-digit number is a prime. Primality testing is discussed in VIII. 2 and VIII. 9. For Draim’s algorithm, see Mathematics Magazine, 25 (1952) 191–4. 10. An excellent account of the distribution of primes is given by A. E. Ingham, The Distribution of Prime Numbers (Cambridge Tracts, no. 30, 1932; reprinted by Hafner Press, New York, 1971). For a more recent and extensive account see H. Davenport, Multiplicative Number Theory, 3rd. ed. (Springer, 2000). H. Iwaniec (Inventiones Math. 47 (1978) 171–88) has shown that for in? nitely many n the number n 2 + 1 is either prime or the product of at most two primes, and indeed the same is true for any irreducible an 2 + bn + c with c odd. Dirichlet’s p roof of his theorem (with a modi? ation due to Mertens) is given as an appendix to Dickson’s Modern Elementary Theory of Numbers. An elementary proof of the Prime Number Theorem is given in ch. 22 of Hardy and Wright. An elementary proof of the asymptotic formula for the number of primes in an arithmetic progression is given in Gelfond and Linnik, ch. 3. For a survey of early work on Goldbach’s problem, see James, Bull. American Math. Soc. , 55 (1949) 246–60. It has been veri? ed that every even number from 6 to 4 ? 1014 is the sum of two primes, see Richstein, Math. Comp. , 70 (2001) 1745–9. For a proof of Chen’s theorem that every suf? iently large even integer can be represented as p + P2 , where p is a prime, and P2 is either a prime or the product of two primes, see ch. 11 of Sieve Methods by H. Halberstam and H. E. Richert (Academic Press, London, 1974). For a proof of Vinogradov’s result, see T. Estermann, Introduction to Modern Prime Number Theory (Cambridge Tracts, no. 41, 1952) or H. Davenport, Multiplicative Number Theory, 3rd. ed. (Springer, 2000). ‘Suf? ciently large’ in Vinogradov’s result has now been quanti? ed as ‘greater than 2 ? 101346 ’, see M. -C. Liu and T. Wang, Acta Arith. , 105 (2002) 133–175.Conversely, we know that it is true up to 1. 13256 ? 1022 (Ramar? and Saouter in J. Number Theory 98 (2003) 10–33). e II CONGRUENCES 1. The congruence notation It often happens that for the purposes of a particular calculation, two numbers which differ by a multiple of some ? xed number are equivalent, in the sense that they produce the same result. For example, the value of (? 1)n depends only on whether n is odd or even, so that two values of n which differ by a multiple of 2 give the same result. Or again, if we are concerned only with the last digit of a number, then for that purpose two umbers which differ by a multiple of 10 are effectively the same. The congruence notation, introduced by Gauss, serves to express in a convenient form the fact that two integers a and b differ by a multiple of a ? xed natural number m. We say that a is congruent to b with respect to the modulus m, or, in symbols, a ? b (mod m). The meaning of this, then, is simply that a ? b is divisible by m. The notation facilitates calculations in which numbers differing by a multiple of m are effectively the same, by stressing the analogy between congruence and equality.Congruence, in fact, means ‘equality except for the addition of some multiple of m’. A few examples of valid congruences are: 63 ? 0 (mod 3), 7 ? ?1 (mod 8), 52 ? ?1 (mod 13). A congruence to the modulus 1 is always valid, whatever the two numbers may be, since every number is a multiple of 1. Two numbers are congruent with respect to the modulus 2 if they are of the same parity, that is, both even or both odd. 31 32 The Higher Arithmetic Two congruences can be added, subtracted, or m ultiplied together, in just the same way as two equations, provided all the congruences have the same modulus.If a ? ? (mod m) and b ? ? (mod m) then a + b ? ? + ? (mod m), a ? b ? ? ? ? (mod m), ab ? (mod m). The ? rst two of these statements are immediate; for example (a + b) ? (? + ? ) is a multiple of m because a ? ? and b ? ? are both multiples of m. The third is not quite so immediate and is best proved in two steps. First ab ? ?b because ab ? ?b = (a ? ?)b, and a ? ? is a multiple of m. Next, ? b ? , for a similar reason. Hence ab ? (mod m). A congruence can always be multiplied throughout by any integer: if a ? ? (mod m) then ka ? k? (mod m).Indeed this is a special case of the third result above, where b and ? are both k. But it is not always legitimate to cancel a factor from a congruence. For example 42 ? 12 (mod 10), but it is not permissible to cancel the factor 6 from the numbers 42 and 12, since this would give the false result 7 ? 2 (mod 10). The reason is obvious : the ? rst congruence states that 42 ? 12 is a multiple of 10, but this does not imply that 1 (42 ? 12) is a multiple of 10. The cancellation of 6 a factor from a congruence is legitimate if the factor is relatively prime to the modulus.For let the given congruence be ax ? ay (mod m), where a is the factor to be cancelled, and we suppose that a is relatively prime to m. The congruence states that a(x ? y) is divisible by m, and it follows from the last proposition in I. 5 that x ? y is divisible by m. An illustration of the use of congruences is provided by the well-known rules for the divisibility of a number by 3 or 9 or 11. The usual representation of a number n by digits in the scale of 10 is really a representation of n in the form n = a + 10b + 100c +  ·  ·  · , where a, b, c, . . . re the digits of the number, read from right to left, so that a is the number of units, b the number of tens, and so on. Since 10 ? 1 (mod 9), we have also 102 ? 1 (mod 9), 103 ? 1 (mod 9), and so on. Hence it follows from the above representation of n that n ? a + b + c +  ·  ·  · (mod 9). Congruences 33 In other words, any number n differs from the sum of its digits by a multiple of 9, and in particular n is divisible by 9 if and only if the sum of its digits is divisible by 9. The same applies with 3 in place of 9 throughout. The rule for 11 is based on the fact that 10 ? ?1 (mod 11), so that 102 ? +1 (mod 11), 103 ? 1 (mod 11), and so on. Hence n ? a ? b + c ?  ·  ·  · (mod 11). It follows that n is divisible by 11 if and only if a ? b+c?  ·  ·  · is divisible by 11. For example, to test the divisibility of 9581 by 11 we form 1? 8+5? 9, or ? 11. Since this is divisible by 11, so is 9581. 2. Linear congruences It is obvious that every integer is congruent (mod m) to exactly one of the numbers 0, 1, 2, . . . , m ? 1. (1) r < m, For we can express the integer in the form qm + r , where 0 and then it is congruent to r (mod m). Obviously there are othe r sets of numbers, besides the set (1), which have the same property, e. . any integer is congruent (mod 5) to exactly one of the numbers 0, 1, ? 1, 2, ? 2. Any such set of numbers is said to constitute a complete set of residues to the modulus m. Another way of expressing the de? nition is to say that a complete set of residues (mod m) is any set of m numbers, no two of which are congruent to one another. A linear congruence, by analogy with a linear equation in elementary algebra, means a congruence of the form ax ? b (mod m). (2) It is an important fact that any such congruence is soluble for x, provided that a is relatively prime to m.The simplest way of proving this is to observe that if x runs through the numbers of a complete set of residues, then the corresponding values of ax also constitute a complete set of residues. For there are m of these numbers, and no two of them are congruent, since ax 1 ? ax2 (mod m) would involve x1 ? x2 (mod m), by the cancellation of the factor a (permissible since a is relatively prime to m). Since the numbers ax form a complete set of residues, there will be exactly one of them congruent to the given number b. As an example, consider the congruence 3x ? 5 (mod 11). 34 The Higher ArithmeticIf we give x the values 0, 1, 2, . . . , 10 (a complete set of residues to the modulus 11), 3x takes the values 0, 3, 6, . . . , 30. These form another complete set of residues (mod 11), and in fact they are congruent respectively to 0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8. The value 5 occurs when x = 9, and so x = 9 is a solution of the congruence. Naturally any number congruent to 9 (mod 11) will also satisfy the congruence; but nevertheless we say that the congruence has one solution, meaning that there is one solution in any complete set of residues. In other words, all solutions are mutually congruent.The same applies to the general congruence (2); such a congruence (provided a is relatively prime to m) is precisely equivalent to the con gruence x ? x0 (mod m), where x0 is one particular solution. There is another way of looking at the linear congruence (2). It is equivalent to the equation ax = b + my, or ax ? my = b. We proved in I. 8 that such a linear Diophantine equation is soluble for x and y if a and m are relatively prime, and that fact provides another proof of the solubility of the linear congruence. But the proof given above is simpler, and illustrates the advantages gained by using the congruence notation.The fact that the congruence (2) has a unique solution, in the sense explained above, suggests that one may use this solution as an interpretation b for the fraction a to the modulus m. When we do this, we obtain an arithmetic (mod m) in which addition, subtraction and multiplication are always possible, and division is also possible provided that the divisor is relatively prime to m. In this arithmetic there are only a ? nite number of essentially distinct numbers, namely m of them, since two numbers w hich are mutually congruent (mod m) are treated as the same.If we take the modulus m to be 11, as an illustration, a few examples of ‘arithmetic mod 11’ are: 5 ? 9 ? ?2. 3 Any relation connecting integers or fractions in the ordinary sense remains true when interpreted in this arithmetic. For example, the relation 5 + 7 ? 1, 5 ? 6 ? 8, 1 2 7 + = 2 3 6 becomes (mod 11) 6 + 8 ? 3, because the solution of 2x ? 1 is x ? 6, that of 3x ? 2 is x ? 8, and that of 6x ? 7 is x ? 3. Naturally the interpretation given to a fraction depends on the modulus, for instance 2 ? 8 (mod 11), but 2 ? 3 (mod 7). The 3 3 Congruences 35 nly limitation on such calculations is that just mentioned, namely that the denominator of any fraction must be relatively prime to the modulus. If the modulus is a prime (as in the above examples with 11), the limitation takes the very simple form that the denominator must not be congruent to 0 (mod m), and this is exactly analogous to the limitation in ordina ry arithmetic that the denominator must not be equal to 0. We shall return to this point later ( §7). 3. Fermat’s theorem The fact that there are only a ? nite number of essentially different numbers in arithmetic to a modulus m means that there are algebraic relations which are satis? d by every number in that arithmetic. There is nothing analogous to these relations in ordinary arithmetic. Suppose we take any number x and consider its powers x, x 2 , x 3 , . . . . Since there are only a ? nite number of possibilities for these to the modulus m, we must eventually come to one which we have met before, say x h ? x k (mod m), where k < h. If x is relatively prime to m, the factor x k can be cancelled, and it follows that x l ? 1 (mod m), where l ? h ? k. Hence every number x which is relatively prime to m satis? es some congruence of this form. The least exponent l for which x l ? (mod m) will be called the order of x to the modulus m. If x is 1, its order is obviously 1. To illustrate the de? nition, let us calculate the orders of a few numbers to the modulus 11. The powers of 2, taken to the modulus 11, are 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, . . . . Each one is twice the preceding one, with 11 or a multiple of 11 subtracted where necessary to make the result less than 11. The ? rst power of 2 which is ? 1 is 210 , and so the order of 2 (mod 11) is 10. As another example, take the powers of 3: 3, 9, 5, 4, 1, 3, 9, . . . . The ? rst power of 3 which is ? 1 is 35 , so the order of 3 (mod 11) is 5.It will be found that the order of 4 is again 5, and so also is that of 5. It will be seen that the successive powers of x are periodic; when we have reached the ? rst number l for which x l ? 1, then x l+1 ? x and the previous cycle is repeated. It is plain that x n ? 1 (mod m) if and only if n is a multiple of the order of x. In the last example, 3n ? 1 (mod 11) if and only if n is a multiple of 5. This remains valid if n is 0 (since 30 = 1), and it remains valid also for negative exponents, provided 3? n , or 1/3n , is interpreted as a fraction (mod 11) in the way explained in  §2. 36 The Higher ArithmeticIn fact, the negative powers of 3 (mod 11) are obtained by prolonging the series backwards, and the table of powers of 3 to the modulus 11 is n =†¦ ?3 ? 2 ? 1 0 1 2 3 4 5 6 . . . 9 5 4 1 3 9 5 4 1 3 †¦ . 3n ? . . . Fermat discovered that if the modulus is a prime, say p, then every integer x not congruent to 0 satis? es x p? 1 ? 1 (mod p). (3) In view of what we have seen above, this is equivalent to saying that the order of any number is a divisor of p ? 1. The result (3) was mentioned by Fermat in a letter to Fr? nicle de Bessy of 18 October 1640, in which he e also stated that he had a proof.But as with most of Fermat’s discoveries, the proof was not published or preserved. The ? rst known proof seems to have been given by Leibniz (1646–1716). He proved that x p ? x (mod p), which is equivalent to (3), b y writing x as a sum 1 + 1 +  ·  ·  · + 1 of x units (assuming x positive), and then expanding (1 + 1 +  ·  ·  · + 1) p by the multinomial theorem. The terms 1 p + 1 p +  ·  ·  · + 1 p give x, and the coef? cients of all the other terms are easily proved to be divisible by p. Quite a different proof was given by Ivory in 1806. If x ? 0 (mod p), the integers x, 2x, 3x, . . . , ( p ? )x are congruent (in some order) to the numbers 1, 2, 3, . . . , p ? 1. In fact, each of these sets constitutes a complete set of residues except that 0 has been omitted from each. Since the two sets are congruent, their products are congruent, and so (x)(2x)(3x) . . . (( p ? 1)x) ? (1)(2)(3) . . . ( p ? 1)(mod p). Cancelling the factors 2, 3, . . . , p ? 1, as is permissible, we obtain (3). One merit of this proof is that it can be extended so as to apply to the more general case when the modulus is no longer a prime. The generalization of the result (3) to any modulus was ? rst given b y Euler in 1760.To formulate it, we must begin by considering how many numbers in the set 0, 1, 2, . . . , m ? 1 are relatively prime to m. Denote this number by ? (m). When m is a prime, all the numbers in the set except 0 are relatively prime to m, so that ? ( p) = p ? 1 for any prime p. Euler’s generalization of Fermat’s theorem is that for any modulus m, x ? (m) ? 1 (mod m), provided only that x is relatively prime to m. (4) Congruences 37 To prove this, it is only necessary to modify Ivory’s method by omitting from the numbers 0, 1, . . . , m ? 1 not only the number 0, but all numbers which are not relatively prime to m.There remain ? (m) numbers, say a 1 , a2 , . . . , a? , Then the numbers a1 x, a2 x, . . . , a? x are congruent, in some order, to the previous numbers, and on multiplying and cancelling a1 , a2 , . . . , a? (as is permissible) we obtain x ? ? 1 (mod m), which is (4). To illustrate this proof, take m = 20. The numbers less than 20 and relati vely prime to 20 are 1, 3, 7, 9, 11, 13, 17, 19, so that ? (20) = 8. If we multiply these by any number x which is relatively prime to 20, the new numbers are congruent to the original numbers in some other order.For example, if x is 3, the new numbers are congruent respectively to 3, 9, 1, 7, 13, 19, 11, 17 (mod 20); and the argument proves that 38 ? 1 (mod 20). In fact, 38 = 6561. where ? = ? (m). 4. Euler’s function ? (m) As we have just seen, this is the number of numbers up to m that are relatively prime to m. It is natural to ask what relation ? (m) bears to m. We saw that ? ( p) = p ? 1 for any prime p. It is also easy to evaluate ? ( p a ) for any prime power pa . The only numbers in the set 0, 1, 2, . . . , pa ? 1 which are not relatively prime to p are those that are divisible by p. These are the numbers pt, where t = 0, 1, . . , pa? 1 ? 1. The number of them is pa? 1 , and when we subtract this from the total number pa , we obtain ? ( pa ) = pa ? pa? 1 = pa? 1 ( p ? 1). (5) The determination of ? (m) for general values of m is effected by proving that this function is multiplicative. By this is meant that if a and b are any two relatively prime numbers, then ? (ab) = ? (a)? (b). (6) 38 The Higher Arithmetic To prove this, we begin by observing a general principle: if a and b are relatively prime, then two simultaneous congruences of the form x ? ? (mod a), x ? ? (mod b) (7) are precisely equivalent to one congruence to the modulus ab.For the ? rst congruence means that x = ? + at where t is an integer. This satis? es the second congruence if and only if ? + at ? ? (mod b), or at ? ? ? ? (mod b). This, being a linear congruence for t, is soluble. Hence the two congruences (7) are simultaneously soluble. If x and x are two solutions, we have x ? x (mod a) and x ? x (mod b), and therefore x ? x (mod ab). Thus there is exactly one solution to the modulus ab. This principle, which extends at once to several congruences, provided that the moduli ar e relatively prime in pairs, is sometimes called ‘the Chinese remainder theorem’.It assures us of the existence of numbers which leave prescribed remainders on division by the moduli in question. Let us represent the solution of the two congruences (7) by x ? [? , ? ] (mod ab), so that [? , ? ] is a certain number depending on ? and ? (and also on a and b of course) which is uniquely determined to the modulus ab. Different pairs of values of ? and ? give rise to different values for [? , ? ]. If we give ? the values 0, 1, . . . , a ? 1 (forming a complete set of residues to the modulus a) and similarly give ? the values 0, 1, . . . , b ? 1, the resulting values of [? , ? constitute a complete set of residues to the modulus ab. It is obvious that if ? has a factor in common with a, then x in (7) will also have that factor in common with a, in other words, [? , ? ] will have that factor in common with a. Thus [? , ? ] will only be relatively prime to ab if ? is relatively prime to a and ? is relatively prime to b, and conversely these conditions will ensure that [? , ? ] is relatively prime to ab. It follows that if we give ? the ? (a) possible values that are less than a and prime to a, and give ? the ? (b) values that are less than b and prime to b, there result ? (a)? (b) values of [? ? ], and these comprise all the numbers that are less than ab and relatively prime to ab. Hence ? (ab) = ? (a)? (b), as asserted in (6). To illustrate the situation arising in the above proof, we tabulate below the values of [? , ? ] when a = 5 and b = 8. The possible values for ? are 0, 1, 2, 3, 4, and the possible values for ? are 0, 1, 2, 3, 4, 5, 6, 7. Of these there are four values of ? which are relatively prime to a, corresponding to the fact that ? (5) = 4, and four values of ? that are relatively prime to b, Congruences 39 corresponding to the fact that ? (8) = 4, in accordance with the formula (5).These values are italicized, as also are the corresponding values of [? , ? ]. The latter constitute the sixteen numbers that are relatively prime to 40 and less than 40, thus verifying that ? (40) = ? (5)? (8) = 4 ? 4 = 16. ? ? 0 1 2 3 4 0 0 16 32 8 24 1 25 1 17 33 9 2 10 26 2 18 34 3 35 11 27 3 19 4 20 36 12 28 4 5 5 21 37 13 29 6 30 6 22 38 14 7 15 31 7 23 39 We now return to the original question, that of evaluating ? (m) for any number m. Suppose the factorization of m into prime powers is m = pa q b . . . . Then it follows from (5) and (6) that ? (m) = ( pa ? pa? 1 )(q b ? q b? 1 ) . . . or, more elegantly, ? (m) = m 1 ? For example, ? (40) = 40 1 ? and ? (60) = 60 1 ? 1 2 1 2 1 p 1? 1 q †¦. (8) 1? 1 3 1 5 = 16, 1 5 1? 1? = 16. The function ? (m) has a remarkable property, ? rst given by Gauss in his Disquisitiones. It is that the sum of the numbers ? (d), extended over all the divisors d of a number m, is equal to m itself. For example, if m = 12, the divisors are 1, 2, 3, 4, 6, 12, and we have ? (1) + ? (2) + ? (3) + ? (4) + ? (6) + ? (12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. A general proof can be based either on (8), or directly on the de? nition of the function. 40 The Higher ArithmeticWe have already referred (I. 5) to a table of the values of ? (m) for m 10, 000. The same volume contains a table giving those numbers m for which ? (m) assumes a given value up to 2,500. This table shows that, up to that point at least, every value assumed by ? (m) is assumed at least twice. It seems reasonable to conjecture that this is true generally, in other words that for any number m there is another number m such that ? (m ) = ? (m). This has never been proved, and any attempt at a general proof seems to meet with formidable dif? culties. For some special types of numbers the result is easy, e. g. f m is odd, then ? (m) = ? (2m); or again if m is not divisible by 2 or 3 we have ? (3m) = ? (4m) = ? (6m). 5. Wilson’s theorem This theorem was ? rst publis

From Boy to a Man: Soucouyant

Living in the past is a challenge, especially when your past is racing in front of your future. The narrator from Souycouyant written by world famous author, David Chariandy, seems to have taken the role from child to caretaker when his mother, Adele, had been diagnosed with dementia. Upon facing reality, the narrator chased and followed his dreams in the begginging of the novel, but in the end, learned that you can never escape where you came from. The narrator had foreseen the future when he had left Adele along with his brother and father, but then returned feeling regret and guilt. By doing so, the narrator turned from a boy to a man when taking on the responsibilities a child should never have to bear. At the age of seven, the narrator found it hard to cope with, let alone, understand what dementia even was. â€Å"I don’t know what scientists called it; it was hard to understand, some sort of memory loss syndrome† (Chariandy 18). During the beginning of the novel, the young boy had been going through many struggles and was seen as a target for racism and discrimination. â€Å"Get off the bus; you don’t deserve to be here† (Chariandy 12). (EXPLAINATION, WHO SAID THIS, AND WHAT SITUATION? Coming to Canada was meant for a brighter future, FOR WHO? as the family had planned out there lives. But, in the hindsight of these terrible events, reality had taken over their dreams. The narrator did not have the chance of going to TO WHERE? because his father and brother both left the family in their own ways. â€Å" Father had died not long af ter being laid off at work, and my brother left quietly because it was who he was† (Chariandy 16). Adele and her son were both alone and it was up to the boy to take care of her. It seemed as if the opposite of everything that was planned for the family had turned up. Instead of the mother taking care of the son, the son was taking care of the mother. In addition, it was hard for a seven year old to do this when her mother did not even know her own name. â€Å"Adida, Adida is me† (Chariandy 31). Moving to Canada was done in hopes of more prosperous chances, but instead, the narrator and Adele are facing the exact opposite and seeing their dreams come to an end. As the years passed by, the narrator had grown old and tired of Adele. He wanted to move on in search of becoming an engineer and repairing vehicles. â€Å"Mother, I can’t stay with you for long. I am going to become and engineer you know† (Chariandy 89). The narrator had left, leaving Adele all alone. It was as if this related to the title of the story. A Soucouyant is a vampire who sucks the blood out of humans. Comparing this to the novel, Adele has had all of her loved ones â€Å"sucked† away from her, including her own memory. From being trapped in a house with nowhere to go, the young boy had escaped the shadow placed around him by his mother and instead, left her, showing how the protagonist was persistent in his journey to moving forward. After leaving, he lived in a city called Scarborough in a small apartment. Becoming an engineer was impossible, as he had no education or money to get started. He worked at the local restaurant cleaning dishes and unloading the delivery truck CHANGE TO DELIVERY TRUCK(S). â€Å"Inside I was dead, and on the outside, I was hurt from all the work I’ve bin doing just to pay for rent† (Chariandy 129). The narrator felt regret by leaving his mother. Knowing that she cannot take care of herself, the narrator, now a teen, made a plan to work until he got enough money to return back to Adele and get her the aid she really needs. Leaving Adele perceived the narrator to be moving on forward, but returning back to her shows the real growth from a boy to man. Now a fully grown man, the narrator had retuned back to Adele but felt weary and out of place. â€Å"I don’t know if mother has been hurt by my absence, or if she’s even noticed it. I don’t know what meaning there can be between us now† (Chariandy, 144). By coming back home to his mother, the narrator had taken a huge step forward into his growth because he had left his mother because he felt that he was not growing, but returned back because he is now grown. With the money he had received from the countless hours of work he had done, the narrator hired a nurse to look after Adele. â€Å" Mother, I have found a nurse named Meera who will be taking care of you when I’m off at work† (Chariandy 156). Taking on the responsibilities of a Father, the protagonist is now able to help Adele while moving on with his own life. â€Å"With the scrapes of money left over, I will be able to go to school and get a degree in engineering† (Chariandy 171). Furthermore, it seems that the tragic events that happened to the narrator all made up at the end of the novel. He enrolled in an engineering class while Meera was doing her job of taking care of Adele. The opposite had happened from dreams verse reality to reality facing their dreams. Without a father, the narrator took on the role of one and took care of his mother and had taken the steps towards getting the job he had dreamt of. In the beginning, the protagonist was immature and knew little, but as he got older and learned more, he grew as a man by taking on the huge obstacles that were in his way. The growth of the narrator is evident throughout the novel. From coping with his mother’s dementia, leaving, and then coming back to help her, the protagonist dealt with responsibilities that he should never have to face. Not only did the narrator grow to help his mother, throughout his journey he had learned that the tragic events of his fathers and brothers passing were not meant to be disappointments, rather to be an alarm to start growing. As David Brinkley once said, â€Å"A successful man is one who can lay a firm foundation with the bricks others have thrown at him†.

IT POLICY Essay Example | Topics and Well Written Essays - 750 words

IT POLICY - Essay Example The three main ethical questions that the use of social networks as a mean of communication are: (1) do social networks protect individual privacy of the users? (2) Do social networks ensure safety for their users? (3) Do the advantages of using social networks outweigh the disadvantages? The question of whether or not social networks protect individual privacy of the users is a pertinent ethical question because a critical look at many social networks shows that the use of social networks comprise individual privacy of the user. This is because many users of social networks, especially the youth share important private information about themselves with their friends on social networks, without realizing that people with bad motives can use the private information to harm them in one way or another. The question of whether or not social networks ensure safety for their users is also a critical ethical question. This question is particularly important considering cybercrimes like cyber bullying and cyber stalking. The third question also is very important because, although there are many advantages of using social networks as a mean of communication, there are also many disadvantages of using social networks as a mean of communication. On utilitarian grounds, therefore, it is important to determine whether or not the advantages of using social networks outweigh the disadvantages. To begin with, social networks compromise individual privacy, especially among the teenagers who disclose a large amount of their personal information online. As Christofides has rightly argued, although Facebook has played a significant role in telecommunication, it has presented a problem in privacy protection among high school students, thus doing more harm than good (2010). Many teenagers disclose on social networks like Facebook sensitive personal information like relationship status, email address, the list of their friends’ birthdays, as well as  other

American History Dissertation Example | Topics and Well Written Essays - 250 words

American History - Dissertation Example Ultimately, the discovery of tobacco allowed Virginia to prosper. The documents of incorporation for Virginia show that it was always intended as a business venture, chartered by the queen for profit, and not a fully fledged colony. This would help lead to the Revolutionary War, as the British felt that their colonists were generally British citizens who just happened to be making money for them and not fully-fledged colonists. Puritans in Massachusetts, meanwhile, wanted to create a utopian community, one free from evil and un-Christianity, a shining light on the hill for the world. The Mayflower Compact illustrates a desire to have some kind of localized democracy, but it's important to note that in many ways Massachussetts would be called undemocratic now, because of its radical religious interpretations and punishments for defiance. The distinction between them played out in establishing much of the course of American history. In the North like Massachusetts, civil society and in tegration due to closely connected cities would create a different culture from the South where farmers spent a lot of their time apart and civil society was far less powerful. The North did not have slaves, but it did participate in the slave trade; the Southerners bought slaves.

Discuss the limitations of Becken and Simmons' (2008) approach to Essay

Discuss the limitations of Becken and Simmons' (2008) approach to yield analysis AND discuss ways in which their model might be developed further - Essay Example In tourism, yield can mean the profit or revenue incurred from hosting the different visitor types. In order to achieve sustainable yield, three dimensions; social, economic and ecological yields need to be combined to a single yield measure (Becken and Simmons, 2008). This has been shown to be impossible as there is no suitable methodology to merge these yields. Becken and Simmons (2008) further explained that the research focused on the financial aspect in terms of yield to measure the private sector tourism yield. To calculate the financial yield, the researchers used individual sectors like hotels that the tourists visited and did not consider the financial impacts of tourism on the societies, nations or the environment. Tourism has both the public and private components and as such it is difficult to assess tourism sustainability. This represents a limitation as it this mix is complex and difficult to cumulatively assess (Becken and Simmons, 2008). The research used the transport and accommodation details of the visitors to identify the tourist types. The types that were identified as a result were; backpackers, campers, home visitors, free independent travelers and coachers. Out of these, the researchers were unable to determine the tourist types of 16% of the sample and as a result, they excluded this number from the database (Becken and Simmons, 2008). This percentage represents a significant number of tourists and is therefore a significant loss for the research. According to Becken and Simmons (2008), the research also focused on the emission of carbon dioxide gas or greenhouse gas emission as the ecological only impact of tourism. This is a limitation, as they needed to assess other environmental impacts of tourism like the impact of tourism on ecological resources like water and soil conservation. Tourism has economic, environmental and

Mass transportation in los angeles Essay Example | Topics and Well Written Essays - 500 words

Mass transportation in los angeles - Essay Example The express buses do not stop often and normally drive on the freeways where it is possible to cover the shortest distance, which means that it skips various stops and areas. The rapid buses normally travel and pick passengers on local streets, although they do not make as many stops as the local buses and, therefore, can be considered as better when it comes to beating the traffic. However, one is advised to review the schedules prior to travelling since these buses change routes and, during the late hours, their frequency is reduced. Fares for a weekly pass are $20, for a day pass one has to pay $5 and $1.50 for a single ride (Shanks, 2001). Metro buses in Los Angeles also use the orange and silver rapid transit lines to operate metro liners, which are present on the metro rail map due to the fact that, along majority of their routes, they operate transit-ways (Shanks, 2001). The Department of Transportation In Los Angeles also operates white buses on top of the Metro on local lines so as to supplement their bus service Downtown and in other areas with high population densities. In addition, cities that neighbour LA also operate bus systems that extend their routes into LA and charge different fares. These buses overlap with the Metro bus networks. Some of these bus systems also run rapid line routes, which are parallel to local routes but have fewer stops. Some of these include the Big Blue Bus that is operated by Santa Monica City and serves Santa Monica, Venice Beach, Brentwood and other West LA districts, LAX, and downtown LA. The Culver City Bus serves Culver City, LAX, Century City, Mar Vista, Rancho Park, Marina Del Rey, Palms, West LA Transit Centre, UCLA, Venice, Westwood, and Westchester (Bottles, 2011). The Burbank Transit operates around North Hollywood and Burbank, while Torrance Transit operates around Torrance to Long and Redondo Beach, downtown LA, and LAX. The Foothills Transit also operates

The effects of Globalisation Essay Example | Topics and Well Written Essays - 3000 words

The effects of Globalisation - Essay Example The effects of globalization on the European Union are diverse. But the future growth and sustainability of the EU is dependent on globalization. The reforms influenced by globalization in the European countries not only make the Union more transparent and effective but also help the European Union to establish itself as a strong global actor. The challenges faced in the global including the European Union like economic integration, economic migration, humanitarian crises, failing states, energy security, climate change, terrorism etc. are interdependent. The European Union identifies the importance of globalization and the impacts of the phenomenon on the various aspects of the economy. Therefore, it should focus on effective management of the globalization process in order to meet the arising challenges and prevent any backlash from the phenomenon. The effective management of globalization and its rules would help the European Union to act as global actor in the true sense. The int ernal policies and the association with the international organizations can help the Union in managing the process of globalization in the region and control its effects and impacts to a large extent.

Risk Assessment Continuity Plan Essay Example | Topics and Well Written Essays - 1250 words

Risk Assessment Continuity Plan - Essay Example Simply put, a continuity plan comes into play when internal or external factors influence the company to resort to emergency actions in order to continue providing services to their clients. In our case, the company’s continuity plan comes into action if the database integrity is damaged or information security is compromised. As suggested by Britt (2005) a modular stepwise plan is most effective and that is how our continuity plan would function if the risk assessment recommendations are already established. Since our security is working on several layers, the continuity plan would also work in layers which will be connected to how bad a breach is made into our systems. For instance, if a hacker attack has been detected and we know that the hacker did not manage to go thorough any layers of our security, it would be useless to require a physical change of location for our database storage servers since it would simply mean that we are reacting too much. On the other hand, if there is a fire in the building which damages the property to such an extent that business becomes impossible to continue in the same location, a secondary location must be activated where we can continue to provide services to our clients and maintain our operations at more or less the same levels. Similarly, a virus which brings down our network or corrupts the database stored on one location might require the activation of a secondary location where the most recent backup of the database could be used for continuity of business (Britt, 2005). As it has been ascertained by nearly every writer working on the topic of continuity plans, backups are essential for a smooth recovery from disaster (Gouldson, 2002). An accidental disaster does mean a flood or hurricane since in those cases a company may have a few days of warning to ensure that everything is in place to counter that. An accidental disaster can be natural, i.e. earthquake or lightning strike but

Stages in the Model of Planned Organizational Change Essay

Stages in the Model of Planned Organizational Change - Essay Example Before going to discuss stages in the model of planned organizational change, let us get a better understanding of what organizational change actually is. Organizational change refers to those changes that occur in the organization due to the influence of various external and internal forces. Rasing (2010) states, â€Å"The key to organizational change and development lies in the understanding of people's requirements and work towards it†. External and internal forces of change not only affect organizational policies but also but also affect organizational structure. Organizational change is a very important process related to roles and cultural management of a company. It refers to the changes in overall behaviors and roles of the employees of a company for bringing improvement in the overall productivity of the company. There are four main activities involved in the model of planned organizational change, which include entering, diagnosing, planning and implementing change, and evaluating and institutionalizing change. Let us discuss all of these activities in order to know what role they play in bringing change in any specific organization. Stage 1: Entering and Contracting Entering and contracting is the first set of activities involved in the planned organizational change. In this stage, managers decide whether they need to enter into the activity of organizational change or not.

Brighter Cleaning Essay Example | Topics and Well Written Essays - 1000 words

Brighter Cleaning - Essay Example y dynamic, comprising of factors that keep changing, for instance, customers’ tastes and preferences are never static, they keep changing in the face of technological advancements. In the same way, it is important that marketing strategies also keep changing in order to remain relevant and effective in the changing business environment. The name of my company is a Brighter Cleaning Company, which is located in Fort Wayne, Indiana. The company has 100 employees and over 10 years experience. The number of employees and experience puts the Brighter Cleaning Company in a position to handle any size of customers. Brighter Cleaning Company main focus is supplying cleaning products to the businesses around. The company offers products to some parts of Ohio: Defiance, Bryan, Plymouth, Peru, Lima, Napoleon, Celina and Coldwater. Other areas that the company’s products have gained popularity are: Auburn, Anderson, Angola Bluffton and Fort Wayne just to name a few. The Brighter Cleaning Company offers janitorial equipment and cleaning solutions products for furniture and floors. The cleaning products and janitorial equipment help in keeping the work places clean and free from germs. The products can be categorized into three major areas: equipment, paper products and cleaning chemicals. The specific products include brooms, brushes, dustpans, chemicals, dust mops, dusters and cleaning pads. Additional products are floor and furniture care, janitorial carts, paper products, rags and wipes. The Brighter Cleaning Company also offers receptacles, personal care, trash bags, liners, recycling equipments and replacement parts. The company’s mission statement is stated as; to become the leading provider of reliable and efficient cleaning services that leaves the workplace and other environment sparkling clean, free from germs and disease causing micro-organisms, as well as other health hazards. In achieving this mission, the company has so far identified janitorial

Happiness in marriage Essay Example for Free

Happiness in marriage Essay Happiness in marriage is entirely a matter of chance. With reference to marriages in Pride and Prejudice, to what extent is this statement true? Marriage is the key issue in Pride and Prejudice, and Austen uses class structure, manners and proper behaviour in society to embellish the topic. It is the overall picture given by these subjects that tell us about the happiness a woman could expect from entering the state of marriage, whether marrying for love and felicity, or, as seems the wise choice in the case of many of the characters, for money and financial security. Pride and Prejudice explores the situations that many young ladies found themselves put in, and whether or not it was possible to achieve fulfilment and happiness if you were to marry for the latter. In the Bennet household, particularly, marriage is a very poignant subject. For Mrs Bennet, she feels it is essential for her girls (and for herself) that they should marry well, as otherwise they stand to lose everything without a son to take over the estate. Her feelings are made clear at the beginning, once she has heard that a wealthy Mr Bingley has recently moved to the neighbourhood. Without any knowledge or regard for his character, she immediately jumps to the conclusion that it is a fine thing for our girls. This statement is made purely on the awareness of his handsome fortune, and of the happiness and fortune that it could bring her. She uses the word girls, and this shows that she doesnt care for individual happiness, but she does want one of them married to him, never mind which. Her own marriage is described as lacking in respect, esteem and confidence, and through Elizabeths eyes it is improper and unsuitable. Although their marriage was based chiefly on an attraction on Mr Bennets part, Jane Austen states that it had been an imprudent move, and that he had married a woman whose weak understanding and illiberal mind had very early in their marriage put an end to all real affection. The only happiness he seems to have from the marriage is his constant mocking of his wife for his own amusement, and marvelling at her ignorance. The marriage which exists is based on a fancy rather than the three qualities that Jane Austen, through Elizabeth, attributes to true marital happiness for both partners: respect, esteem and confidence, which is exactly what Mr and Mrs Bennet dont have for each other. Mrs Bennet, for her own daughters marriages, sees the purpose as a way of supporting themselves, and gaining some kind of financial security, and the bigger the fortune, the better the match. When Elizabeth turns down the heir to Longbourn, Mr Collins, she says to her daughter If you go on refusing every offer of marriage, you will never get a husband, and I am sure I do not know who is to maintain you when your father is dead. This view is one shared by Charlotte, although she does not air her opinions so openly. Charlotte Lucas is a realist. Her role in the book is to represent the thoughts and intentions of many ladies in eighteenth century society. What numerous young women were doing, whether they were influenced by their mothers or not, was to make a cautious and prudent marriage. As a girl of twenty-seven, plain, and in danger of dying an old maid, she has taken on the view that happiness in marriage is entirely a matter of chance is a reference to the fact that women did pre-dominantly marry for money, not indeed love. She even goes as far as to advise Elizabeth on a match with Mr Darcy, although Elizabeths feelings are prejudiced towards him. She tells Elizabeth not to be a simpleton, and allow her fancy for Wickham make her appear unpleasant in the eyes of [Darcy] a man ten times his consequence. This shows her prudence, that although Elizabeth has admitted she has feelings for Wickham, she should keep herself open to anyone who pays her a compliment, and is wealthier. It is this theory that influences her own marriage with Mr Collins, for although there is no real affection on her side, he can offer her protection and a comfortable life. The practical nature of her marriage causes her to justify herself to her best friend, and she openly admits to her I am not a romantic, I never was. Immediately, this tells us that this marriage is not the result of a passionate affair, it is the conclusion that her chance of happiness with him is as fair as most people can boast on entering the marriage state. This statement is quite shocking, because it means the wedding takes place with no real affection on either side: it is done merely for self-gain. This view is also made clear when she comments on Jane and Bingleys relationship: When [Jane] is secure of him (i.e. a wedding or engagement has taken place), there will be leisure for falling in love as much as she chuses. Although Mr Collins seems to be happy, when he tells Elizabeth that We (he and Charlotte) seem to have been designed for each other, we have to go back to the fact that Charlotte was his third choice. He had favoured Jane, before Mrs Bennet enlightened him with the information that she believed that she would soon be engaged to Bingley, and it was only afterwards, when Elizabeth had turned his offer of marriage down, that he showed any regard for Charlotte. He proposed twice in three days, and so it is clear that no real feelings of admiration on either part could have developed strongly. This marriage is established on the ground that Mr Collins wants to set an example to his parishioners, and, more importantly in his eyes, to please his wealthy patroness, Lady Catherine. Mr. Collins also remarks on Elizabeths situation, as his wife had done previously when he says that her portion is unhappily so small that it will in all likelihood undo the effects of [her] loveliness and amiable qualifications. The Lucases are by no means wealthy, but Mr Collins is not looking for wealth, he is looking to add to his happiness by obtaining a companion. He came with the intention of returning home with a Bennet bride, but failing that he has an intelligent, practical woman, who has gone into a marriage with no pre-wedding romance, but to be content with her quite prosperous situation. As Elizabeth observes, Charlotte was disgracing herself and sunk in her esteem, was added the distressing conviction that it was impossible for that friend to be tolerably happy in the lot she had chosen. In direct contrast to Charlottes carefully thought about match, Lydia rushes into a passionate and imprudent marriage. Society almost expected women to marry above their own wealth and station, to make a sensible union, but it was a disgrace to have an affair it was essential that a woman should keep her virtue. Lydia, however, did the latter but not the first. Inside these parameters, Lydia is a slur on her already tarnished family name. Herr quite insincere love caused her to follow her heart, and go against the foresight that was instilled in so many young women, essentially from birth. Her love can be described more as a fancy, because it holds none of the virtues so important to Elizabeth, and therefore Jane Austens eyes: respect, esteem and gratitude. However, the match between herself and Wickham gives them both happiness, and, although her family does not share their feelings, her decision, however misguided, does give her happiness. Prior to the marriage, she writes for there is but one man in the world I love, and he is an angel. This view is in opposition to Charlottes, that one must marry into good fortune, and then see what happiness may come of it, if any at all. Lydias perception of Wickham is unchanged when she writes again, once Elizabeth and Darcy are married. She says that If you love Mr Darcy half so well as I do my dear Wickham, you must be very happy. Although on initially embarking on her elopement, the marriage looked as though it was a flirtatious whim, especially on the part of Wickham, by the end, there is no real relationship development, except that they still love each other. From the circumstances surrounding both of their families, it is safe to say that Wickham is not marrying for wealth, it is for his apparent love for Lydia. Previously, he had been engaged to Mary King, a wealthy heiress of ten thousand pounds, and Elizabeth had said of the match a wise and desirable measure for both; handsome young men must have something to live on, as well as the plain. As Colonel Fitzwilliam said of men Our habits of expense make us too dependent, and there are not many in my rank of life who can afford to marry without some attention to money. However, these same motives are not seen in his match with Lydia, although it is true to say that unless Darcy had intervened, they may not have married. Elizabeth also observes that his affections for Lydia were not equal to Lydias for him.that their elopement had been brought on by the strength of her love. She also wonders why he chose to elope with her at all, before coming to the conclusion that some financial gain must have been the reason, and if that were the case, he was not the young man to resist an opportunity of having a companion. However, these reasons have not impaired Lydias enjoyment of married life, nor Wickhams, as she is constantly praising him he is always her dear, and he did everything the best in the world. Whether these observations are made due to Lydias ignorance, or her blindness in her fancy, she does not seem to have tired of him, as Mr Bennet had of Mrs Bennet soon after their wedding. Someone who has married for both money and affection is Jane. There is a mutual attraction between her and Mr Bingley, and this leads onto, we presume, matrimonial bliss. Their relationship is fixed firmly on a rational basis, and they both share an optimistic view of the world. Elizabeth, early on in the book, comments on the likelihood that Janes marriage would be for money, not love, but by the end, Jane and Bingleys equally happy manners and charming countenances mean that there is equality in their affections unlike Wickham and Lydia, where there is more fondness on her side. Their shared admiration for one another gives the foundation for equilibrium, that there will be a good balance of respect, esteem and confidence on both sides. Mr Bingley says that he could not conceive an angel more attractive, while Jane says of Bingley, albeit in private, that she never saw such happy manners. With these observations, this is a match will lead to domestic felicity that luck and chance will have no role in the marriage; it has been carefully thought out, and although it is practical, it is also a match which will bring happiness on both sides. Elizabeth describes him as violently in love, and goes on to say, at the request of her aunt, that he was wholly engrossed in her and his inattention to anyone else, meant that this was the very essence of love. Mr Bennet, immediately after the engagement had been announced tells his daughter that you will be a very happy womanI have no doubt of your doing very well together. These views are ones shared by all, because it is obvious from their first physical attraction, and also their same manner, that they were well suited, and that their pleasure is secured by such high regard. However, when Elizabeth announces her engagement, her father is not as convinced that she will be as happy as Jane is. Her knowledge of Darcys gallantry has grown, whereas her fathers has been stifled, and so he doubts her true happiness when he says: I know your true disposition, Lizzy. I know that you could be neither happy nor respectable unless you truly esteemed your husband. However, his understanding of her true feelings could not be further from the truth. Throughout the entire book, it seems Darcy and Elizabeths relationship is the only one that has grown in understanding and estimation of one another. Respect on both sides has grown, because as they have gained more knowledge, they have also gained more esteem. This is the one relationship where there is a true shift from almost hate to true love. The re-assessment of characters allows us to see the real feelings behind the relationship, and even with Jane and Bingleys, although they respect one another, their connection is based centrally around admiration, whereas Darcy and Elizabeth have had to conquer their own pride and prejudice to have a full understanding of each other. Throughout the novel, Austen dropped hints about Darcys interest into Elizabeths intriguing character, but Elizabeth showed no interest in Darcy, except to air her feelings of intolerance at his proud nature. Mrs Gardiner, whose marriage is a very good example of what a successful relationship should aim to achieve, is very motherly towards Elizabeth and gives her competent advice, rather than nonsensical schemes for marriage. She advises her on her fancy for Mr Wickham: affection for Wickham would be so very imprudent because of his want of fortune. The relationships in the book are mainly seen through the eyes of Elizabeth, and it is she who determines whether they are happy or not. She was full of scorn for Charlottes match with her fathers cousin, and when she advised Elizabeth that Jane should secure him and than fall in love, she made a witty and ironic comment, which tells us that she would only marry for a love that had been determined before a ceremony: Where nothing is in question but the desire of being well married; and if I were determined to get a rich husband, or any husband, I dare say I should adopt it. In short, Lizzy represents Austens own view on marriage, that one should truly know, admire and respect a person before entering the state. Her mother complained to Mrs Gardiner, that had it not been for Lizzys perverseness she could have married Mr Collins. With views such as this, it is little wonder that the intelligent Elizabeth has such guarded opinion of marriage: she had always been aware of the impropriety of her own parents union, that this could put her off entering into marriage with someone she did not hold esteem for. It is this reasoning that allows her to fall in love with Darcy, and visa versa. Her unconventional views on what should be established prior to an engagement contrast with many of the motives for the marriages in the book. Lydia and Wickham, as well as Mr Bennet had all been headlong in their reasons, and these marriages, although they could bring happiness for at least some amount of time would not have been as morally successful as Elizabeth and Darcy, whose marriage is based on mutual esteem. Whereas Charlotte had thought about the espousal, and then agreed, much to the disdain of her friend, her happiness is impaired, because the marriage is not based on love, as Elizabeths is, it is principled on common gain, as were many matches in the society. Not only do Darcy and Elizabeth respect and gratify each other, they also share common interests, such as reading, as well as having the same elegant tastes. These qualities ensure happiness, unlike Mr and Mrs Bennet, where stimulation of the mind is essential to one, and stimulation of the tongue necessary for the other. Pride and Prejudice is a very good example of what different types of marriages can achieve: a good home and security, passion and fun or intelligent companionship. Marriage opens up different ways to different types of happiness, but true happiness can only be achieved on the grounds of honour and deference. Lydia, and to some extent Wickham, are happy, despite the different morals in their marriage, when compared to Charlotte and Mr Collins marriage. Darcy and Elizabeth are happy because they knew, appreciated and respected each other before entering matrimony, whereas Wickham and Lydia entered marriage with little but their fancy for each other to base their lives together on. In my opinion, Darcy and Elizabeths match is better, because their happiness is determined before marriage, not decided afterwards. Happiness in marriage is entirely a matter of chance is true to some marriages, but in a carefully calculated marriage, based on respect, esteem and confidence, the question of chance is indifferent.