HW 12, MAT 312/AMS 351: SPRING 2017 Problem 1. (1) Set H = {4a + 6b | a, b Z} Z. Show that H is a subgroup of Z. (2) Is H cyclic? Problem 2. Write down all the cyclic subgroups of the following groups G6 ,G7 , G8 , G11 , G12 . Which of these groups is cyclic? Problem 3. Let G be a group that has no subgroups. Show that G is cyclic. [Hint: consider an element g G and the subgroup hgi H]. Problem 4. Let G be an abelian group and let H G be the set of elements a G such that a2 = e. Show that H is subgroup of G. Problem 5. Let G be an abelian group and let H, K G be two subgroups. Set HK = {hk | h H, k K}. Show that HK is a subgroup of G. Problem 6. Do problems 5.1.4, 5.1.7, and 5.1.9. Problem 7. Let G and H be two groups. A map f : G H is called a group homomorphism (or more simply a homomorphism) if it \"respects the group structure\" i.e., if f (xy) = f (x)f (y) holds for any two elements x, y G. Denote by eG G and eH H the identity elements of G and H, respectively. (1) We define the kernel of f to be the subset ker(f ) = {g G | f (g) = eH }. Show that ker(f ) G is a subgroup. (2) We define the image of f to be the subset Im(f ) = {h G | h = f (g) for some g G}. Show that Im(f ) H is a subgroup. 1 Group theory and error-correcting codes llz= Since we have listed all the cyclic subgroups in 5(3) and since S(3) itself is not on the list, it follows that the group S(3) is not cyclic. Note that, in principle, we can nd all the cyclic subgroups of a given nite group by taking each element of the group in tum and computing the cyclic subgroup it generates, then deleting any duplicates. Example 2 As we saw above, the subgroup of GL(2, 1R) generated by 1 1 0 1 is an innite cyclic group. Example 3 In the additive group (2, +), the cyclic subgroup generated by the integer 1 consists of all multiples (not powers, because the group operation is addition!) of 1 and so is the whole group. The subgroup (2) is the set of even integers. The subgroup (3) consists of all integer multiples of 3. The intersection is easily computed: (2) n (3) = (6). Example 4 The group (Zn, +) is itself cyclic, as are all its subgroups The set of all its subgroups forms a partially ordered set under inclusion. The Hasse diagram of this set is shown in Fig. 5.1. The reader may be familiar with vector spaces, where the change from struc tures generated by one element to those generated by two is not very great. 5.1 Preliminaries The situation for groups is very different A group generated by two elements may well be immensely complicated. In Section 4.3 .4 we saw some of the sim- pler examples: the dihedral groups (groups of symmetries of regular n-sided polygons) can be generated by two elements. These elements are the reection R in the perpendicular bisector of any one of the sides and the rotation p, through 21r/n radians. Thus R2 = e = p" and there is also the relation p"\"R = Rp. The resulting group has 2n elements which can all be written in the form p' R7 wherefisOorlandOsi < n. We also saw in Section 4.2 that the symmetric group S(n) can be generated by its transpositions. In fact S(n) can be generated by the n 1 transpositions (1 2), (2 3), . . . , (n 1 n): for every element ofS(n) can be written as aproduct of these. (This was set as Exercise 4.2.10.) However, the relations between these generators are much more complicated than in the case of the dihedral groups. Exercises 5.1 1. Prove that for any elements a and b of a group G, ab = bu if and only if (ab)'1 = a\"b\". 2. Let a, b be elements of a group G. Find (in terms of a and b) an expression for the solution x of the equation axba\" = b. 3. Take G to be the cyclic group with 12 elements. Find an element g in G such that the equation x2 = g has no solution. 4. Use Theorem 5.1.1 to decide which of the following subsets of the given groups are subgroups: (i) the subset of the symmetries of a square consisting of the rotations; (ii) the subset of (R +) consisting of lR\\(0) under multiplication; (iii) the subset (id, (1 2), (1 3), (2 3)} of S(3); (iv) the subset of (GL6, lR),-) consisting of matrices of the form 1 a b 0 1 c . 0 0 l . Give an example of a group G and elements a, b, and c in G, such that a is different from b but ac = cb. . Let G be a cyclic group generated by 2:. Note that for any positive integer k, the set (xk) is a subgroup of G. Ifx has nite order 12, consider the possible values fork (from 0 to 11) and, in each case, show that (x') is generated by x\" where d is the greatest common divisor of k and n. Deduce that (x") has 12/41 elements. Group theory and error-correcting codes . Let G be a cyclic group generated by x with x of order greater than 1. Let Hbe a subgroup ofG with Hneither G nor (2). Let m 2 1 be minimal such that x\" is in H. Use the division algorithm to show that it" generates H and deduce that every subgroup of a cyclic group is cyclic. . Let g and x be elements of a group G. Show that for all positive integers k, <3"ng = g"x*g- Dcduce that; has order 3 ifand only if(for all g E G) g"xg has order 3. Show that the same is true for any integer n 2 1 in place of 3. . Let G be any group and dene the relation of conjugacy on G by aRb if and only if there exists g e G such that b = (big. Show that this is an equivalence relation on G. . Find a e 623, the group of invertible congruence classes modulo 23, such that every element of G23 is a power of a: that is, show that G13 is a cyclic group by nding a generator for it. Similarly show that G26 is cyclic by nding a generator for it. Is every group of the form 6,. cyclic? 5.2 Cosets and Lagrange's Theorem If H is a subgroup of a group G then G breaks up into 'translates', or careta, of Hi This notion of a coset is a key concept in group theory and we will make use of cosets in this section by proving Lagrange's Theorem. The remainder of the section is devoted to deriving consequences of this theorem, which may be regarded as the fundamental result of elementary group theory. Denition Let H be a subgroup of the group G, and let a be any element of G. Dene aH to be the set of all elements of G which may be written as uh for some element It in H: aH = (ah : h e H). This is a (left) coset ofH (in G): it is also termed the left coset of a with respect to H. Similarly dene the right coset Ha = (ha I h e H). We make the convention that the unqualied term 'coset' means 'left coset'. Notes (1) The subgroup H is a coset of itself, being equal to eH. (2) The element a is always a member of its coset aH since a = lie 5 aH (for e is in H, since H is a subgroup). Similarly, a is a member of the right coset Ha. (3) If b is in (1H then bH = uH. To see this suppose that b = ah for some h in H. A typical member of bH has the form bk for some k in H. We have: bk = (uh)k = u(hk). 5.2 Guests and Lagrange's Theorem Since H is a subgroup, hk is in H and so we have that bk is in 11H. Thus bH S aH. For the converse, note that from the equation b = ah we may derive a = bh\Examples of groups 4.3 Definition and examples of groups We are now ready to abstract the properties which several of our structures share We make the following general denition Denition A group is a set G. together with an operation *, which satises the following properties: (61) for all elements g and h of G, g a h is anelement ofG (closure); (G2) for all elements, 3, h and k of G, (gah)*k=g*(hak) (associativity); (G3) there exists an element e of G, called the identity (or unit) of G, such thatforallginGwehave eag=gse=g (existenceofidentity); (G4) for every g inG there exists an elemait 3'1 called the inverse ofg, such that gsg'1=g"*g=e (existenceofinverse). Denition The group (G, aa) is said to be commutative or Abelian (after Niels Henrik Abel (180229)) if the operation a: satises the commutative law, thatis,ifforallg andhinGwehaveg *h = h *g. Normally we will use multiplicative notation instead of 's', and so write 'gh' instead of 'g *h': for that reason some books use '1' instead of '2' for the identity element of G. Occasionally (and especially if the group is Abelian) we will use additive notation, writing 'g + h' instead of 'g at h' and g for g", in which case the symbol '0' is normally used for the identity element of G Note that the condition (GS) ensures that the set G is non-empty. Associativity means that (gh)k = g(hk), and so we may write ghk without ambiguityr It follows, by induction, that this is true for any product of group elements: different bracketing does not change the value of the resulting element. Use of the terms \"the identity' and 'rhe inverse\" presupposes that the objects named are uniquely dened We now justify this usage Theorem 4.3.1 Let G be any group. Then there is just one element e of G satisfying the conditicnfor being an identity of G. Also, for each element g in G 43 Definition and examples of groups there is just one element g1 in G satisfying the condition for being an inverse of g. Proof Suppose that both e and f satisfy the condition for being an identity element of G. Then we have f=ef=e2 the rst equality holds since e acts as an identity, the second equality holds since f acts as an identity So there is just one identity element, Given g in G, suppose that both h and k satisfy the condition for being an inverse of g, Then we have h = he = huh), since I: is an inverse for g. But, by associativity, this equals (hg)k and then, since h is an inverse for g, this in turn equals ek = k. Thus it = k, and the inverse of g is indeed unique. El Let us now consider some examples of groups, 4.3.1 Groups of numbers Example 1 The integers (Z, +) with addition as the operation, form a group The closure and associativity properties are part of the unwritten assumptions we have made about Z. The identity element for addition is 0. The inverse of n is n. This group has an innite number of elements. In contrast, the set of natural numbers N equipped with addition is not a group, since not all its elements have additive inverses (within the set N). Note also that the integers with multiplication as the operation do not form a group since, for instance, 2 does not have a multiplicative inverse within the set Z. Example 2 The integers modulo n, (Zn, +) (Let the set of congruence classes modulo n), equipped with addition modulo n (ire. addition of congruence classes) as the operation. form a group. The identity element is the congru- ence class [0],, of 0 modulo n. The inverse of [k],, is [k],,. This example was discussed in Chapter 1, and it is an example of a group with a nite number of elements Notice again that if multiplication is taken as the operation then the set of congruence classes modulo n is not a group since not all elements have inverses (for example, [0],I has no multiplicative inverse). \fThis page intentionally left blank Numbers, Groups and Codes Second Edition Numbers, Groups and Codes Second Edition J. F. HUMPHREYS Senior Fellow in Mathematics, University of Liverpool M. Y. PREST Professor of Mathematics, University of Manchester CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, So Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 2RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521540506 Cambridge University Press 2004 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 2004 ISBN-13 ISBN-10 978-0-511-19420-7 eBook (EBL) 0-511-19420-X eBook (EBL) ISBN-13 ISBN-10 978-0-521-54050-6 paperback 0-521-54050-X 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. To Sarah, Katherine and Christopher J. F. Humphreys To the memory of my parents M. Y. Prest Contents page ix x xi xiv Preface to first edition Preface to second edition Introduction Advice to the reader 1 1.1 1.2 1.3 1.4 1.5 1.6 2 2.1 2.2 2.3 2.4 3 3.1 3.2 3.3 4 4.1 4.2 4.3 Number theory The division algorithm and greatest common divisors Mathematical induction Primes and the Unique Factorisation Theorem Congruence classes Solving linear congruences Euler's Theorem and public key codes Summary of Chapter 1 Sets, functions and relations Elementary set theory Functions Relations Finite state machines Summary of Chapter 2 Logic and mathematical argument Propositional logic Quantifiers Some proof strategies Summary of Chapter 3 Examples of groups Permutations The order and sign of a permutation Definition and examples of groups vii 1 1 15 25 36 49 59 77 78 78 86 103 117 126 127 128 137 141 146 147 148 159 170 viii 4.4 5 5.1 5.2 5.3 5.4 6 6.1 6.2 6.3 6.4 6.5 Contents Algebraic structures Summary of Chapter 4 Group theory and error-correcting codes Preliminaries Cosets and Lagrange's Theorem Groups of small order Error-detecting and error-correcting codes Summary of Chapter 5 Polynomials Introduction The division algorithm for polynomials Factorisation Polynomial congruence classes Cyclic codes Summary of Chapter 6 184 199 200 200 212 219 230 253 255 255 262 273 279 284 291 Appendix on complex numbers Answers References and further reading Biography Name index Subject index 292 296 323 326 331 333 Preface to first edition This book arose out of a one-semester course taught over a number of years both at the University of Notre Dame, Indiana, and at the University of Liverpool. The aim of the course is to introduce the concepts of algebra, especially group theory, by many examples and to relate them to some applications, particularly in computer science. The books which we considered for the course seemed to fall into two categories. Some were too elementary, proceeded at too slow a pace and had far from adequate coverage of the topics we wished to include. Others were aimed at a higher level and were more comprehensive, but had correspondingly skimpy presentation of the material. Since we could find no text which presented the material at the right level and in a way we felt appropriate, we prepared our own course notes: this book is the result. We have added some topics which are not always treated in order to increase the flexibility of the book as the basis for a course. The material in the book could be covered at an unhurried pace in about 48 lectures; alternatively, a 36-hour unit could be taught, covering Chapters 1, 2 (not Section 2.4), 4 and 5. ix Preface to second edition We have prepared this second edition bearing in mind the fact that students studying mathematics at university, at least in the UK, are less well prepared than in the past. We have taken more time to explain some points and, in particular, we have not assumed that students are comfortable reading formal statements of theorems and making sense of their proofs. Especially in the first chapter, we have added many comments designed to help the reader make sense of theorems and proofs. The more 'mathematically sophisticated' reader may, of course, read quickly through these comments. We have also added a few more straightforward exercises at the ends of some sections. Two major changes in content have been made. In Chapter 3 we have removed material (some propositional logic, Boolean algebras and Karnaugh maps) around Boolean algebras. We have retained most of the material on propositional logic, added a section designed to help students deal with quantifiers and added a further section on proof strategies. The emphasis of this chapter is now on the use of logic within mathematics rather than on the Boolean structure behind propositional logic. The second major change has been the inclusion of a new chapter, Chapter 6, on the algebra of polynomials. We emphasise the similarity with the arithmetic of integers, including the usefulness of the notion of congruence class, and we show how polynomials are used in constructing cyclic codes. x Introduction 'A group is a set endowed with a specified binary operation which is associative and for which there exist an identity element and inverses.' This, in effect, is how many books on group theory begin. Yet this tells us little about groups or why we should study them. In fact, the concept of a group evolved from examples in number theory, algebra and geometry and it has applications in many contexts. Our presentation of group theory in this book reflects to some extent the historical development of the subject. Indeed, the formal definition of an abstract group does not occur until the fourth chapter. We believe that, apart from being more 'honest' than the usual presentation, this approach has definite pedagogic advantages. In particular, the student is not presented with a seemingly unmotivated abstract definition but, rather, sees the sense of the definition in terms of the previously introduced special cases. Moreover, the student will realise that these concepts, which may be so glibly presented, actually evolved slowly over a period of time. The choice of topics in the book is motivated by the wish to provide a sound, rigorous and historically based introduction to group theory. In the sense that complete proofs are given of the results, we do not depart from tradition. We have, however, tried to avoid the dryness frequently associated with a rigorous approach. We believe that by the overall organisation, the style of presentation and our frequent reference to less traditional topics we have been able to overcome this problem. In pursuit of this aim we have included many examples and have emphasised the historical development of the ideas, both to motivate and to illustrate. The choice of applications is directed more towards 'finite mathematics' and computer science than towards applications arising out of the natural sciences. Group theory is the central topic of the book but the formal definition of a group does not appear until the fourth chapter, by which time the reader will xi xii Introduction have had considerable practice in 'group theory'. Thus we are able to present the idea of a group as a concept that unifies many ideas and examples which the reader already will have met. One of the objectives of the book is to enable the reader to relate disparate branches of mathematics through 'structure' (in this case group theory) and hence to recognise patterns in mathematical objects. Another objective of the book is to provide the reader with a large number of skills to acquire, such as solving linear congruences, calculating the sign of a permutation and correcting binary codes. The mastery of straightforward clearly defined tasks provides a motivation to understand theorems and also reveals patterns. The text has many worked examples and contains straightforward exercises (as well as more interesting ones) to help the student build this confidence and acquire these skills. The first chapter of the book gives an account of elementary number theory, with emphasis on the additive and multiplicative properties of sets of congruence classes. In Chapter 2 we introduce the fundamental notions of sets, functions and relations, treating formally ideas that we have already used in an informal way. These fundamental concepts recur throughout the book. We also include a section on finite state machines. Chapter 3 is an introduction to the logic of mathematical reasoning, beginning with a detailed discussion of propositional logic. Then we discuss the use of quantifiers and we also give an overview of some proof strategies. The later chapters do not formally depend on this one. Chapter 4 is the central chapter of the book. We begin with a discussion of permutations as yet another motivation for group theory. The definition of a group is followed by many examples drawn from a variety of areas of mathematics. The elementary theory of groups is presented in Chapter 5, leading up to Lagrange's Theorem and the classification of groups of small order. At the end of Chapter 5, we describe applications to error-detecting and error-correcting codes. Chapter 6 introduces the arithmetic of polynomials, in particular the division algorithm and various results analogous to those in Chapter 1. These ideas are applied in the final section, which depends on Chapter 5, to the construction of cyclic codes. Every section contains many worked examples and closes with a set of exercises. Some of these are routine, designed to allow the reader to test his or her understanding of the basic ideas and methods; others are more challenging and point the way to further developments. The dependences between chapters are mostly in terms of examples drawn from earlier material and the development of certain ideas. The main dependences are that Chapter 5 requires Chapter 1 and the early part of Section 4.3 Introduction xiii and, also, the examples in Section 4.3 draw on some of Chapter 1 (as well as Sections 4.1 and 4.2). The material on group theory could be introduced at an early stage but this would not be in the spirit of the book, which emphasises the development of the concept. The formal material of the book could probably be presented in a book of considerably shorter length. We have adopted a more leisurely presentation in the interests of motivation and widening the potential readership. We have tried to cater for a wide range in ability and degree of preparation in students. We hope that the less well prepared student will find that our exposition is sufficiently clear and detailed. A diligent reader will acquire a sound basic knowledge of a branch of mathematics which is fundamental to many later developments in mathematics. All students should find extra interest and motivation in our relatively historical approach. The better prepared student also should derive long-term benefit from the widening of the material, will discover many challenging exercises and will perhaps be tempted to develop a number of points that we just touch upon. To assist the student who wishes to learn more about a topic, we have made some recommendations for further reading. Changes in teaching and examining mathematics in secondary schools in the UK have resulted in first-year students of mathematics having rather different skills than in the past. We believe that our approach is well suited to such students. We do not assume a great deal of background yet we do not expect the reader to be an uncritical and passive consumer of information. One last word: in our examples and exercises we touch on a variety of further developments (for example, normal subgroups and homomorphisms) that could, with a little supplementary material, be introduced explicitly. Advice to the reader Mathematics cannot be learned well in a passive way. When you read this book, have paper and pen(cil) to hand: there are bound to be places where you cannot see all the details in your head, so be prepared to stop reading and start writing. Ideally, you should proceed as follows. When you come to the statement of a theorem, pause before reading the proof: do you find the statement of the result plausible? If not, why not? (try to disprove it). If so, then why is it true? How would you set about showing that it is true? Write down a sketch proof if you can: now try to turn that into a detailed proof. Then read the proof we give. Exercises The exercises at the end of each section are not arranged in order of difficulty, but loosely follow the order of presentation of the topics. It is essential that you should attempt a good portion of these. Understanding the proofs of the results in this book is very important but so also is doing the exercises. The second-best way to check that you understand a topic is to attempt the exercises. (The best way is to try to explain it to someone else.) It may be quite easy to convince yourself that you understand the material: but attempting the relevant exercises may well expose weak points in your comprehension. You should find that wrestling with the exercises, particularly the more difficult ones, helps you to develop your understanding. You should also find that exercises and proofs illuminate each other. Proofs Although the emphasis of this text is on examples and applications, we have included proofs of almost all the results that we use. Since students often find difficulty with formal proofs, we will now discuss these at some length. Attitudes towards the need for proofs in mathematics have changed over the centuries. The first mathematics was concerned with computations using particular numbers, and so the question of proof, as opposed to correctness of a xiv Advice to the reader xv computation, never arose. Later, however, in arithmetic and geometry, people saw patterns and relationships that appeared to hold irrespective of the particular numbers or dimensions involved, so they began to make general assertions about numbers and geometrical figures. But then a problem arose: how may one be certain of the truth of a general assertion? One may make a general statement, say about numbers, and check that it is true for various particular cases, but this does not imply that it is always true. To illustrate. You may already have been told that every positive integer greater than 1 is a product of primes, for instance 12 = 2 2 3, 35 = 5 7, and so on. But since there are infinitely many positive integers it is impossible, by considering each number in turn, to check the truth of the assertion for every positive integer. So we have the assertion: 'every positive integer greater than 1 is a product of primes'. The evidence of particular examples backs up this assertion, but how can we be justifiably certain that it is true? Well, we may give a proof of the assertion. A proof is a sequence of logically justified steps which takes us from what we already know to be true to what we suspect (and, after a proof has been found, know) to be true. It is unreasonable to expect to conjure something from nothing, so we do need to make some assumptions to begin with (and we should also be clear about what we mean by a valid logical deduction). In the case of the assertion above, all we need to assume are the ordinary arithmetic properties of the integers, and the principle of induction (see Section 1.2 for the latter). It is also necessary to have defined precisely the terms that we use, so we need a clear definition of what is meant by 'prime'. We may then build on these foundations and construct a proof of the assertion. (We give one on p. 28.) It should be understood that current mathematics employs a very rigorous standard of what constitutes a valid proof. Certainly what passed for a proof in earlier centuries would often not stand up to present-day criteria. There are many good reasons for employing such strict criteria but there are some drawbacks, particularly for the student. A formal proof is something that is constructed 'after the event'. When a mathematician proves a result he or she will almost certainly have some 'picture' of what is going on. This 'picture' may have suggested the result in the first place and probably guided attempts to find a proof. In writing down a formal proof, however, it often is the case that the original insight is lost, or at least becomes embedded in an obscuring mass of detail. Therefore one should not try to read proofs in a naive way. Some proofs are merely verifications in which one 'follows one's nose', but you will probably be able to recognise such a proof when you come across one and find no great xvi Advice to the reader trouble with it - provided that you have the relevant definitions clear in your mind and have understood what is being assumed and what is to be proved. But there are other proofs where you may find that, even if you can follow the individual steps, you have no overview of the structure or direction of the proof. You may feel rather discouraged to find yourself in this situation, but the first thing to bear in mind is that you probably will understand the proof sometime, if not now, then later. You should also bear in mind that there is some insight or idea behind the proof, even if it is obscured. You should therefore try to gain an overview of the proof: first of all, be clear in your mind about what is being assumed and what is to be proved. Then try to identify the key points in the proof - there are no recipes for this, indeed even experienced mathematicians may find difficulty in sorting out proofs that are not well presented, but with practice you will find the process easier. If you still find that you cannot see what is 'going on' in the proof, you may find it helpful to go through the proof for particular cases (say replacing letters with numbers if that is appropriate). It is often useful to ignore the given proof (or even not to read it in the first place) but to think how you would try to prove the result - you may well find that your idea is essentially the same as that behind the proof given (or is even better!). In any event, do not allow yourself to become 'stuck' at a proof. If you have made a serious attempt to understand it, but to little avail, then go on: read through what comes next, try the examples, and maybe when you come back to the proof (and you should make a point of coming back to it) you will wonder why you found any difficulty. Remember that if you can do the 'routine' examples then you are getting something out of this text: understanding (the ideas behind) the proofs will deepen your understanding and allow you to tackle less routine and more interesting problems. Background assumed We have tried to minimise the prerequisites for successfully using this book. In theory it would be enough to be familiar with just the basic arithmetic and order-related properties of the integers, but a reader with no more preparation than this would, no doubt, find the going rather tough to begin with. The reader that we had in mind when writing this book has also seen a bit about sets and functions, knows a little elementary algebra and geometry, and does know how to add and multiply matrices. A few examples and exercises refer to more advanced topics such as vectors, but these may safely be omitted. 1 Number theory This chapter is concerned with the properties of the set of integers {. . . , 2, 1, 0, 1, 2, . . .} under the arithmetic operations of addition and multiplication. We shall usually denote the set of integers by Z. We shall assume that you are acquainted with the elementary arithmetical properties of the integers. By the end of this chapter you should be able to solve the following problems. 1. What are the last two digits of 31000 ? 2. Can every integer be written as an integral linear combination of 197 and 63? 3. Show that there are no integers x such that x 5 3x 2 + 2x 1 = 0. 4. Find the smallest number which when divided by 3 leaves 2, by 5 leaves 3 (Master Sun's tzi su`an jing and by 7 leaves 2. (This problem appears in Sun Arithmetical Manual ) which was written around the fourth century.) 5. How may a code be constructed which allows anyone to encode messages and send them over public channels, yet only the intended recipient is able to decode the messages? 1.1 The division algorithm and greatest common divisors We will assume that the reader is acquainted with the elementary properties of the order relation '' on the set Z. This is the relation 'less than or equal to' which allows us to compare any two integers. Recall that, for example, 100 2 and 3 3. The following property of the set P = {1, 2, . . .} of positive integers is important enough to warrant a special name. 1 2 Number theory Well-ordering principle Any non-empty set, X , of positive integers has a smallest element (meaning an element which is less than or equal to every member of the set X ). You are no doubt already aware of this principle. Indeed you may wonder why we feel it necessary to state the principle at all, since it is so 'obvious'. It is, however, as you will see, a key ingredient in many proofs in this chapter. An equivalent statement is that one cannot have an unending, strictly decreasing, sequence of positive integers. Note that the principle remains valid if we replace the set of positive integers by the set N = {0, 1, 2, . . .} of natural numbers. But the principle fails if we replace P by the set, Z, of all integers or, for a different kind of reason, if we replace P by the set of positive rational numbers (you should stop to think why). We use Q to denote the set of all rational numbers (fractions). A typical use of the well-ordering principle has the following shape. We have a set X of positive integers which, for some reason, we know is non-empty (that is, contains at least one element). The principle allows us to say 'Let k be the least element of X '. You will see the well-ordering principle in action in this section. The well-ordering principle is essentially equivalent to the method of proof by mathematical induction. That method of proof may take some time to get used to if it is unfamiliar to you, so we postpone mathematical induction until the next section. The proof of the first result, Theorem 1.1.1, in this section is a good example of an application of the well-ordering principle. Look at the statement of the result now. It may or may not be obvious to you what the theorem is 'really saying'. Mathematical statements, such as the statement of 1.1.1, are typically both general and concise. That makes for efficient communication but a statement which is concise needs thought and time to draw out its meaning and, when faced with a statement which is general, one should always make the effort (in this context, by plugging in particular values) to see what it means in particular cases. In this instance we will lead you through this process but it is something that you should learn to do for yourself (you will find many opportunities for practice as you work through the book). The first sentence, 'Let a and b be natural numbers with a > 0', invites you to choose two natural numbers, call one of them a and the other b, but make sure that the first is strictly positive. We might choose a = 175, b = 11. The second sentence says that there are natural numbers, which we will write as q and r , such that 0 r < a and b = aq + r . The first statement, 0 r < a, says that r is strictly smaller than a (the '0 r ' is redundant since any natural number has to be greater than or equal to 0, it is just there for emphasis). 1.1 The division algorithm and greatest common divisors 3 The second statement says that b is an integer multiple of a, plus r . With our choice of numbers the second statement becomes: 'There are natural numbers q, r such that 0 r < 175 and 11 = 175q + r '. In other words, we can write 11 as a non-negative multiple of 175, plus a non-negative number which is strictly smaller than 175. But that is obvious: take q = 0 and r = 11 to get 11 = 175 0 + 11. You would be correct in thinking that there is more to 1.1.1 than is indicated by this example! You might notice that 1.1.1 says more if we take b > a. So let us try with the values reversed, a = 11, b = 175. Then 1.1.1 says that there are natural numbers q, r with r < 11 such that 175 = 11q + r . How can we find such numbers q, r ? Simply divide 175 by 11 to get a quotient (q) and remainder (r ): 175 = 11 15 + 10, that is q = 15, r = 10. So the statement of 1.1.1 is simply an expression of the fact that, given a pair of positive integers, one may divide the first into the second to get a quotient and a remainder (where we insist that the remainder is as small as possible, that is, strictly less than the first number). Now you should read through the proof to see if it makes sense. As with the statement of the result we will discuss (after the proof ) how you can approach such a proof in order to understand it: in order to see 'what is going on' in the proof. Theorem 1.1.1 (Division Theorem) Let a and b be natural numbers with a > 0. Then there are natural numbers q, r with 0 r < a such that: b = aq + r (r is the remainder, q the quotient of b by a). Proof If a > b then just take q = 0 and r = b. So we may as well suppose that a b. Consider the set of non-negative differences between b and integer multiples of a: D = {b ak : b ak 0 and k is a natural number}. (If this set-theoretic notation is unfamilar to you then look at the beginning of Section 2.1.) This set, D, is non-empty since it contains b = b a 0. So, by the wellordering principle, D contains a least element r = b aq (say). If r were not strictly less than a then we would have r a 0, and therefore r a = (b aq) a = b a(q + 1). So r a would be a member of D strictly less than r , contradicting the minimality of r . 4 Number theory Hence r does satisfy 0 r < a; and so r and q are as in the statement of the theorem. ! For example, if a = 3 and b = 7 we obtain q = 2 and r = 1: we have 7 = 3 2 + 1. If a = 4 and b = 12 we have q = 3 and r = 0: that is 12 = 4 3 + 0. The symbol '!' above marks the end of a proof. Comments on the proof Let us pull the above proof apart in order to see how it works. You might recognise the content of the first sentence from the discussion before 1.1.1: it is saying that if a > b then there is nothing (much) to do - we saw an example of that when we made the choice a = 175, b = 11. The next sentence says that we can concentrate on the main case where a b. The next stage, the introduction of the set D, certainly needs explanation. Before you read a proof of any statement you should (make sure you understand the statement! and) think how you might try to prove the statement yourself. In this case it is not so obvious how to proceed: you know how to divide any one number into another in order to get a quotient and a remainder, but trying to express this formally so that you can prove that it always works could be quite messy (though it is possible). The proof above is actually a very clever one: by focussing on a well chosen set it cuts through any messy complications and gives a short, elegant path to the end. So to understand the proof we need to understand what is in the set D. Now, one way of finding q and r is to subtract integer multiples of a from b until we reach the smallest possible non-negative value. The definition of the set D is based on that idea. That definition says that the typical element of D is a number of the form b ak, that is, b minus an integer multiple of a (well, in the definition k is supposed to be non-negative but that is not essential: we are after the smallest member of D and allowing k to be negative will not affect that). In other words, D is the set of non-negative integers which may be obtained by subtracting a non-negative multiple of a from b (so, in our example, D would contain numbers including 175 and 98 = 175 7 11). What we then want to do is choose the least element of D, because that will be a number of the form b ak which is the smallest possible (without dropping to a negative number). The well-ordering principle guarantees that D, a set of natural numbers, has a smallest element, but only if we first check that D has at least one element. But that is obvious: b itself is in D. So now we have our least element in D and, in anticipation of the last line of the proof, we write it as r. Of course, being a member of D it has the form r = b aq for some q (again, in anticipation of how the remainder of the 1.1 The division algorithm and greatest common divisors 5 proof will go, we write q for this particular value of what we wrote as 'k' in the definition of D). Rearranging the equation r = b aq we certainly have b = aq + r so all that is left is to show that 0 r < a. We chose r to be in D and it is part of the definition of D that all its elements should be non-negative so we do have 0 r . All that remains is to show r < a. The last part of the proof is an example of what is called 'proof by contradiction' (we discuss this technique below). We want to prove r < a so we say, suppose not - then r a - but in that case we could subtract a at least once more from r and still have a number of the form b ak which is non-negative. Such a number would be an element of D but strictly smaller than r and that contradicts our choice of r as the smallest element of D. The conclusion is that we do, indeed, have r < a and, with that, the proof is finished. Proof by contradiction Suppose that we want to prove a statement. Either it is true or it is false. What we can do is suppose that it is false and then see where that leads us: if it leads us to something that is wrong then we must have started out by supposing something that is wrong. In other words, the supposition that the statement is false must be wrong. Therefore the original statement must be true. For instance, suppose that we want to prove that there is no largest integer. Well, either that is correct or else there is a largest integer. So let us suppose for a moment that there is a largest integer n say. But then n + 1 is an integer which is larger than n, a contradiction (to n being the largest integer). So supposing that there is a largest integer leads to a contradiction and must, therefore, be false. In other words, there is no largest integer. Definition Given two integers a and b, we say that a divides b (written 'a | b') if there is an integer k such that ak = b. For example, 7 | 42 but 7 does not divide 40, we write 7 |! 40 (it is true that 40/7 makes sense as a rational number but here we are working in the integers and insist that k in the definition should be an integer: positive, negative or 0). Thus a divides b exactly if, with notation as in Theorem 1.1.1, r = 0. Note that this definition has the consequence (take k = 0) that every integer divides 0. Another idea with which you are probably familiar is that of the greatest common divisor (also called highest common factor) of two integers a and b. Usually this is described as being 'the largest integer which divides both a and b'. In fact, it is not only 'the largest' in the sense that every other common divisor of a and b is less than it: it is even the case that every common divisor of a and b divides it. 6 Number theory This is essentially what the next theorem says. The proof should be surprising: it proves an important property of greatest common divisor that you may not have come across before, a property which we extract in Corollary 1.1.3. Theorem 1.1.2 Given positive integers a and b, there is a positive integer d such that (i) d divides a and d divides b, and (ii) if c is a positive integer which divides both a and b then c divides d (that is, any common divisor of a and b must divide d ). Proof Let D be the set of all positive integers of the form as + bt where s and t vary over the set of all integers: D = {as + bt : s and t are integers and as + bt > 0}. Since a(a = a 1 + b 0) is in D, we know that D is not empty and so, by the well-ordering principle, D has a least element d, say. Since d is in D there are integers s and t such that d = as + bt. We have to show that any common divisor c of a and b is a divisor of d. So suppose that c divides a, say a = cg, and that c divides b, say b = ch. Then c divides the right-hand side (cgs + cht) of the above equation and so c divides d. This checks condition (ii). We also have to check that d does divide both a and b, that is we have to check condition (i). We will show that d divides a since the proof that d divides b is similar (a and b are interchangable throughout the statement and proof so 'by symmetry' it is enough to check this for one of them). Applying Theorem 1.1.1 to 'divide d into a', we may write a = dq + r with 0 r < d. We must show that r = 0. We have r = a dq = a (as + bt)q = a(1 sq) + b(tq). Therefore, if r were positive it would be in D. But d was chosen to be minimal in D and r is strictly less than d. Hence r cannot be in D, and so r cannot be positive. Therefore r is zero, and hence d does, indeed, divide a. ! 1.1 The division algorithm and greatest common divisors 7 Comment Note the structure of the last part of the proof above. We chose d to be minimal in the set D and then essentially said, 'The remainder r is an integer combination of a and b so, if it is not zero, it must be in the set D. But d was supposed to be the least member of D and r < d. So the only possibility is that r = 0.' There is a definite similarity to the end of the proof of 1.1.1. Given any a and b as in 1.1.2, we claim that there is just one positive integer d which satisfies the conditions (i) and (ii) of the theorem. For, suppose that a positive integer e also satisfies these conditions. Applying condition (i) to e we have that e divides both a and b; so, by condition (ii) applied to d and with e in place of 'c' there, we deduce that e divides d. Similarly (the situation is symmetric in d and e) we may deduce that d divides e. So we have two integers, d and e, and each divides the other: that can only happen if each is the other. But both d and e are positive, so the only possibility is that e = d, as claimed. Note the strategy of the argument in the paragraph above. We want to show that there is just one thing satisfying certain conditions. What we do is to take two such things (but allowing the possibility that they are equal) and then show (using the conditions they satisfy) that they must be equal. Definition The integer d satisfying conditions (i) and (ii) of the theorem is called the greatest common divisor or gcd of a and b and is denoted (a, b) or gcd(a, b). Some prefer to call (a, b) the highest common factor or hcf of a and b. Note that, just from the definition, (a, b) = (b, a). For example, (8, 12) = 4, (3, 21) = 3, (4, 15) = 1, (250, 486) = 2. Note It follows easily from the definition that if a divides b then the gcd of a and b is a. For instance gcd(6, 30) = 6. The proof of 1.1.2 actually showed the following very important property (you should go back and check this). Corollary 1.1.3 Let a and b be positive integers. Then the greatest common divisor, d, of a and b is the smallest positive integral linear combination of a and b. (By an integral linear combination of a and b we mean an integer of the form as + bt where s and t are integers.) That is, d = as + bt for some integers s and t. For instance, the gcd of 12 and 30 is 6: we have 6 = 30 1 12 2. In Section 1.5 we give a method for calculating the gcd of any two positive integers. 8 Number theory We make some comment on what might be unfamiliar terminology. A 'Corollary' is supposed to be a statement that follows from another. So often, after a Theorem or a Proposition (a statement which, for whatever reason, is judged by the authors to be not quite as noteworthy as a Theorem) there might be one or more Corollaries. In the case above it was really a corollary of the proof, rather than the statement, of 1.1.2. The term 'Lemma', used below, indicates a result which we prove on the way to establishing something more notable (a Proposition or even a Theorem). Before stating the next main theorem we give a preliminary result. Lemma 1.1.4 Let a and b be natural numbers and suppose that a is non-zero. Suppose that b = aq + r with q and r positive integers. Then the gcd of b and a is equal to the gcd of a and r. Proof Let d be the gcd of a and b. Since d divides both a and b, d divides the (term on the) right-hand side of the equation r = b aq: hence d divides the left-hand side, that is, d divides r. So d is a common divisor of a and r. Therefore, by definition of (a, r ), d divides (a, r ). Similarly, since the gcd (a, r ) divides a and r and since b = aq + r , (a, r ) must divide b. So (a, r ) is a common divisor of a and b and hence, by definition of d = (a, b), it must be that (a, r ) divides d. It has been shown that d and (a, r ) are positive integers which divide each other. Hence they are equal, as required. ! Discussion of proof of 1.1.4 Sometimes, if the structure of a proof is not clear to you, it can help to go through it with some or all 'x's and 'y's (or in this case, a and b) replaced by particular values. We illustrate this by going through the proof above with particular values for a and b. Let us take a = 30, b = 171. In the statement of 1.1.4 we write b in the form aq + r , that is, we write 171 in the form 30q + r . Let us take q = 5 so r = 21 and the equation in the statement of the lemma is 171 = 30 5 + 21 (but we do not have to take the form with smallest remainder r, we could have taken say q = 3 and r = 81, the conclusion of the lemma will still be true with those choices). The proof begins by assigning d to be (30, 171). Then (says the proof ) d divides both 30 and 171 so it divides the right-hand side of the rearranged equation 21 = 171 30 5 hence d divides the left-hand side, that is d divides 21. So d is a common divisor of 30 and 21. Therefore, by definition of the gcd (30, 21) it must be that d divides (30, 21). 1.1 The division algorithm and greatest common divisors 9 Similarly, since (30, 21) divides both 30 and 21 and since 171 = 30 5 + 21 it must be that (30, 21) divides 171 and so is a common divisor of 30 and 171. Therefore, by definition of d = (30, 171) we must have that (30, 21) divides d. Therefore d and (30, 21) are positive integers which divide each other. The conclusion is that they must be equal: (30, 171) = (30, 21). (Of course, you can compute the actual values of the gcd to check this but the point is that you do not need to do the computation to know that they are equal. In fact, the lemma that we have just proved is the basis of the practical method for computing greatest common divisors, so to say that we do not need this lemma because we can always compute the values completely misses the point!) The next result appears in Euclid's Elements (Book VII Propositions 1 and 2) and so goes back as far as 300 bc. The proof here is essentially that given in s`uan sh`u (Nine Chapters on Euclid (it also appears in the Chinese Jiu zhang the Mathematical Art) which was written no later than the first century ad). Observe that the proof uses 1.1.1, and hence depends on the well-ordering principle (which was used in the proof of 1.1.1). Indeed it also uses the wellordering principle directly. The (very useful) 1.1.3 is not explicit in Euclid. Theorem 1.1.5 (Euclidean algorithm) Let a and b be positive integers. If a divides b then a is the greatest common divisor of a and b. Otherwise, applying 1.1.1 repeatedly, define a sequence of positive integers r1 , r2 , . . . , rn by b = aq1 + r1 a = r 1 q2 + r 2 .. . (0 < r1 < a), (0 < r2 < r1 ), rn2 = rn1 qn + rn (0 < rn < rn1 ), rn1 = rn qn+1 . Then rn is the greatest common divisor of a and b. Proof Apply Theorem 1.1.1, writing r1 , r2 , . . . , rn for the successive non-zero remainders. Since a, r1 , r2 , . . . is a decreasing sequence of positive integers, it must eventually stop, terminating with an integer rn which, because no nonzero remainder 'rn+1 ' is produced must, therefore, divide rn1 . Then, applying 1.1.4 to the second-to-last equation gives (rn2 , rn1 ) = (rn1 , rn ) which, we have just observed, is rn . Repeated application of Lemma 1.1.4, working back through the equations, shows that rn is the greatest common divisor of a and b. ! 10 Number theory Example Take a = 30, b = 171. 171 = 5 30 + 21 30 = 21 + 9 so r1 = 21 so r2 = 9 so r3 = 3 21 = 2 9 + 3 9 = 3 3. and (171, 30) = (30, 21); and (30, 21) = (21, 9); and (21, 9) = (9, 3); Hence (171, 30) = (30, 21) = (21, 9) = (9, 3) = 3. If we wish to write the gcd in the form 171s + 30t, we can use the above equations to 'solve' for the remainders as follows. 3 = 21 2 9 = 21 2(30 21) = 3 21 2 30 = 3(171 5 30) 2 30 = 3 171 17 30. The calculation may be conveniently arranged in a matrix format. To find (a, b) as a linear combination of a and b, set up the partitioned matrix " ! b 1 0 a 0 1 (this may be thought of as representing the equations: 'x = b' and 'y = a'). Set b = aq1 + r1 with 0 r1 < a. If r1 = 0 then we may stop since then a = (a, b). If r1 is non-zero, subtract q1 times the bottom row from the top row to get (noting that b aq1 = r1 ) ! " r1 1 q1 . 0 1 a Now write a = r1 q2 + r2 with 0 r2 < r1 . We may stop if r2 = 0 since r1 is then the gcd of a and r1 , and hence by 1.1.4 is the gcd of a and b. Furthermore, the row of the matrix which contains r1 allows us to read off r1 as a combination of a and b: namely 1 b + (q1 ) a = r1 . If r2 is non-zero then we continue. Thus, if at some stage one of the rows is ni m i | ri () representing the equation bn i + am i = ri , 1.1 The division algorithm and greatest common divisors 11 and if the other row reads n i+1 ( ) m i+1 | ri+1 then we set ri = ri+1 qi+2 + ri+2 with 0 ri+2 < ri+1 and we subtract qi+2 times the second of these rows from the first and replace () with the result. Observe that these operations reduce the size of the (non-negative) numbers in the right-hand column, and so eventually the process will stop. When it stops we will have the gcd: moreover if the row containing the gcd reads n m|d then we have the expression, bn + am = d, of d as an integral linear combination of a and b. Example 1 We repeat the above example in matrix form: so a = 30 and b = 171. ! 1 0 0 1 171 30 " ! ! 1 5 0 1 21 30 3 17 1 6 " ! " 21 1 5 9 1 6 " ! " 3 3 3 17 . 9 0 10 57 So (171, 30) = 3 = 3 171 17 30. Example 2 Take b to be 507 and a to be 391. " ! " ! " ! 507 116 116 1 1 1 1 1 0 391 391 43 0 1 0 1 3 4 ! " ! " 30 30 7 9 7 9 43 13 3 4 10 13 ! " ! " 25 35 4 4 25 35 10 13 91 118 13 1 (507, 391) = 1 = 91 507 + 118 391. 12 Number theory You may use whichever method you prefer for calculating gcds: the methods are essentially the same and it is only in the order of the calculations that they differ. The advantages of the matrix method are that there is less to write down and, at any stage, the calculation can be checked for correctness, since a row u v | w represents the equation bu + av = w. A disadvantage is that one has to put more reliance on mental arithmetic. Therefore it is especially important that, after finishing a calculation like those above, you should check the correctness of the final equation as a safeguard against errors in arithmetic. A good exercise (if you have the necessary background) is to write a program (in pseudocode) which, given any two positive integers, finds their gcd as an integral linear combination. If you attempt this exercise you will find that any gaps in your understanding of the method will be highlighted. The definition of greatest common divisor may be extended as follows. Definition Let a1 , . . . , an be positive integers. Then their greatest common divisor (a1 , . . . , an ), also written gcd(a1 , . . . , an ), is the positive integer m with the property that m | ai for each i and, whenever c is an integer with c | ai for each i, we have c | m. This exists, and can be calculated, by using the case n = 2 'and induction'. We discuss induction at length in the next section but here we will give a somewhat informal indication of how it is used. We claim that (a1 , . . . , an ) = ((a1 , . . . , an1 ), an ). In other words, we can compute the gcd of n numbers, a1 , . . . , an by computing the gcd of the first n 1 of them and then computing the gcd of that and the last number an . As for computing the gcd of a1 , . . . , an1 we compute that by computing the gcd of the first n 2 numbers and then computing the gcd of that with an1 . Etc. So, in the end, all we need is to be able to compute the gcd of two numbers. Here is an example. Suppose that we wish to compute (24, 60, 30, 8). We claim that this is equal to ((24, 60, 30), 8) and that this is equal to (((24, 60), 30), 8). Now we do some arithmetic and find that (24, 60) = 12, then (12, 30) = 6 and then (6, 8) = 2, so we conclude (24, 60, 30, 8) = 2. After you have read the section on induction you can try, as an exercise, to give a formal proof that, for all n and integers a1 , . . . , an , we have (a1 , . . . , an ) = ((a1 , . . . , an1 ), an ). Definition Two positive integers a and b are said to be relatively prime (or coprime) if their greatest common divisor is 1: (a, b) = 1. Example 2 above shows that 507 and 391 are relatively prime. 1.1 The division algorithm and greatest common divisors 13 We now give some properties of relatively prime integers. You are probably aware of these properties though you may not have seen them stated formally. A special case of (i) below is the deduction that since 15 and 8 are relatively prime and since 15 divides 8 30 = 240 it must be that 15 divides 30. A special case of (ii) is that since 15 and 8 are relatively prime and since 15 divides 360 and 8 divides 360 we must have that 15 8 = 120 divides 360. Perhaps by giving numerical values to a, b, and c in this way it all seems rather obvious but, beware: neither (i) nor (ii) is true without the assumption that a and b are relatively prime. If we were to replace 15 and 8 by, say 6 and 9, the statements (i) and (ii) would be false for some values of c. See Exercises 1.1.4 and 1.1.5 at the end of the section. Theorem 1.1.6 Let a, b, c be positive integers with a and b relatively prime. Then (i) if a divides bc then a divides c, (ii) if a divides c and b divides c then ab divides c. Proof (i) Since a and b are relatively prime there are, by 1.1.3, integers r and s such that 1 = ar + bs. Multiply both sides of this equation by c to get c = car + cbs. () Since a divides bc, it divides the right-hand side of the equation and hence divides c. (ii) With the above notation, consider equation (). Since a divides c, ab divides cbs and, since b divides c, ab divides car. Thus ab divides c as required. ! Comment Note how using 1.1.3 gives a beautifully simple argument - surely not the argument one would first think of trying. The results of this section may be extended in fairly obvious ways to include negative integers. For example, to apply Theorem 1.1.1 with b negative and a positive it makes best sense to demand that the remainder 'r' still satisfy the inequality 0 r < a. This means that in order to divide the negative number b by a we do not simply divide the positive number b by a and then put a minus sign in front of everything. 14 Number theory Example To divide 9 by 4: find the multiple of 4 which is just below 9 (that is 12 = 4(3)) and then write: 9 = 4(3) + 3, noting that the remainder 3 satisfies 0 3 < 4. (If we wrote 9 = 4(2) + 1, then the remainder 1 would not satisfy the inequality 0 r < 4.) So remember that the remainder should always be positive or zero. A similar remark applies to Theorem 1.1.5: we require that the greatest common divisor always be positive. Example The greatest common divisor of 24 and 102 equals the greatest common divisor of 24 and 102. To express it as a linear combination of 24 and 102, either we use the matrix method or we proceed as follows, remembering that remainders must always be non-negative: 102 = 24 5 + 18 24 = 18(2) + 12 18 = 12 1 + 6 12 = 6 2. Hence the gcd of 24 and 102 is 6 and 6 is 1(102) + 4(24). To conclude this section, we note that there is the notion of least common multiple or lcm of integers a and b. This is defined to be the positive integer m such that both a and b divide m (so m is a common multiple of a and b), and such that m divides every common multiple of a and b. It is denoted by lcm(a, b). The proof that such an integer m does exist, and is unique, is left as an exercise. More generally, given non-zero integers a1 , . . . , an , we define their least common multiple, lcm(a1 , . . . , an ), to be the (unique) positive integer m which satisfies ai |m for all i and, whenever an integer c satisfies ai | c for all i, we have m | c. For instance lcm(6, 15, 4) = lcm(lcm(6, 15), 4) = lcm(30, 4) = 60. We shall see in Section 1.3 how to interpret both the greatest common divisor and the least common multiple of integers a and b in terms of the decomposition of a and b as products of primes. All of the concepts and most of the results of this section are to be found in the Elements of Euclid (who flourished around 300 bc). Euclid's origins are unknown but he was one of the scholars called to the Museum of Alexandria. The Museum was a centre of scholarship and research established by Ptolemy, a general of Alexander the Great, who, after the latter's death in 323 bc, gained control of the Egyptian part of the empire. 1.2 Mathematical induction 15 The Elements probably was a textbook covering all the elementary mathematics of the time. It was not the first such 'elements' but its success was such that it drove its predecessors into oblivion. It is not known how much of the mathematics of the Elements originated with Euclid: perhaps he added no new results; but the organisation, the attention to rigour and, no doubt, some of the proofs, were his. It is generally thought that the algebra in Euclid originated considerably earlier. No original manuscript of the Elements survives, and modern editions have been reconstructed from various recensions (revised editions) and commentaries by other authors. Exercises 1.1 1. For each of the following pairs a, b of integers, find the greatest common divisor d of a and b and express d in the form ar + bs: (i) a = 7 and b = 11; (ii) a = 28 and b = 63; (iii) a = 91 and b = 126; (iv) a = 630 and b = 132; (v) a = 7245 and b = 4784; (vi) a = 6499 and b = 4288. 2. Find the gcd of 6, 14 and 21 and express it in the form 6r + 14s + 21t for some integers r, s and t. [Hint: compute the gcd of two numbers at a time.] 3. Let a and b be relatively prime integers and let k be any integer. Show that b and a + bk are relatively prime. 4. Give an example of integers a, b and c such that a divides bc but a divides neither b nor c. 5. Give an example of integers a, b and c such that a divides c and b divides c but ab does not divide c. 6. Show that if (a, c) = 1 = (b, c) then (ab, c) = 1 (this is Proposition 24 of Book VII in Euclid's Elements). 7. Explain how to measure 8 units of water using only two jugs, one of which holds precisely 12 units, the other holding precisely 17 units of water. 1.2 Mathematical induction We can regard the positive integers as having been constructed in the following way. Start with the number 1. Then add 1 to get 2. Then add 1 to get 3. Add 1 again to get 4. And so on. That is, we start with a certain base, 1, and then, again and again without ending, we add 1. In this way we generate the positive integers. A construction of this sort (begin with a base case then apply a process again and again) is described as an inductive construction. Here is another example. 16 Number theory Define a sequence of integers as follows. Set a1 = 2, define an+1 inductively by the formula an+1 = 2an + 1. So a2 = 2a1 + 1 = 2 2 + 1 = 5, a3 = 2a2 + 1 = 2 5 + 1 = 11, a4 = 2a3 + 1 = 2 11 + 1 = 23, and so on. You might notice that if we add 1 to any of the numbers that we have generated so far we obtain a multiple of 3. You might check a few more values and see that this still seems to be a property of the numbers generated in this sequence. But how can we prove that this holds for every number in the sequence? Obviously we cannot check each one, because the sequence never ends. What we can do is use a proof by induction. Essentially this is a proof that uses the way that the sequence is generated by a base number together with a rule (an+1 = 2an + 1) which is applied again and again. At the base case we can just compute: adding 1 to a1 gives 1 + 2 = 3 which is certainly divisible by 3. At the 'inductive step', where we go from an to an+1 , we argue as follows. Suppose that we know that an + 1 is a multiple of 3, say an + 1 = 3k. Then an+1 + 1 = (2an + 1) + 1 = 2an + 2 = 2(an + 1) = 2(3k): which is certainly a multiple of 3. It follows that for every n it is true that an + 1 is a multiple of 3. Use of the induction principle can take very complicated forms but, at base, is the fact that the positive integers are constructed by starting somewhere and then applying a 'rule' again and again. Here is a very abstract statement of the induction principle. In the statement, 'P(n)' is any mathematical assertion involving the positive integer n (think of 'n' as standing for an integer variable, as in the assertion ' 12 + 13 + + n1 is not an integer'). Induction principle Let P(n) be an assertion involving the positive integer variable n. If (a) P(1) holds and (b) whenever P(k) holds so also does P(k + 1) then P(n) holds for every positive integer n. That is, if we can prove the 'base case' at n = 1 and then, if we have an argument that proves the k + 1 case from the k case, then we have the result for all positive integers. The typical structure of a proof by induction is as follows. Base case - show P(1); Induction step - assume that P(k) holds (this assumption is the induction hypothesis) and deduce that P(k + 1) follows