課件文稿物理競賽104number theory problems from the training of usa imo team

1、About the AuthorsTitu Andreescu received his Ph.D. from the West University of Timisoara, Ro-mania. The topic of his dissertation was “Research on DiophAnalysis andApplications.” Professor Andreescu currently teaches at The University of Texas at Dallas. He is past chairman of the USA Mathematical O

2、lympiad, served as di- rector of the MAA American Mathematics Competitions (19982003), coach of the USA International Mathematical Olympiad Team (IMO) for 10 years (1993 2002), director of the Mathematical Olympiad Summer Program (19952002), and leader of the USA IMO Team (19952002). In 2002 Titu wa

3、s elected member of the IMO Advisory Board, the governing body of the worlds most prestigious mathematics competition. Titu co-founded in 2006 and continues as director of the AwesomeMath Summer Program (AMSP). He received the Edyth May SliffeAward for Distinguished High School Mathematics Teaching

4、from the MAA in 1994 and a “Certicate of Appreciation” from the president of the MAA in 1995 for his outstanding service as coach of the Mathematical Olympiad Summer Pro-gram in preparing the US team for its perfect performance inat the1994 IMO. Titus contributions to numerous textbooks and problem

5、books are recognized worldwide.Dorin Andrica received his Ph.D in 1992 from “Babes¸-Bolyai” University inCluj-Napoca, Romania; his thesis treated critical points and applications to the geometry of differentiable submanifolds. Professor Andrica has been chairman of the Department of Geometry at

6、 “Babes¸-Bolyai” since 1995. He has written and contributed to numerous mathematics textbooks, problem books, articles and sci- entic papers at various levels. He is an invited lecturer at university conferences around the world: Austria, Bulgaria, Czech Republic, Egypt, France, Germany, Greece

7、, Italy, the Netherlands, Portugal, Serbia, Turkey, and the USA. Dorin is a member of the Romanian Committee for the Mathematics Olympiad and is a member on the editorial boards of several international journals. Also, he is well known for his conjecture about consecutive primes called “Andricas Con

8、jecture.” He has been a regular faculty member at the CanadaUSA Mathcamps between 20012005 and at the AwesomeMath Summer Program (AMSP) since 2006.ZuFeng received his Ph.D. from Johns Hopkins University with emphasison Algebraic Number Theory and Elliptic Curves. He teaches at Phillips ExeterAcademy

9、. Zualso served as a coach of the USA IMO team (19972006), wasthe deputy leader of the USA IMO Team (20002002), and an assistant director ofthe USA Mathematical Olympiad Summer Program (19992002). He has been a member of the USA Mathematical Olympiad Committee since 1999, and has been the leader of

10、the USA IMO team and the academic director of the USA Mathe-matical Olympiad Summer Program since 2003. Zuis also co-founder andacademic director of the AwesomeMath Summer Program (AMSP) since 2006. He received the Edyth May Sliffe Award for Distinguished High School Mathe- matics Teaching from the

11、MAA in 1996 and 2002.Titu Andreescu Dorin AndricaZuFeng104 Number Theory ProblemsFrom the Training of the USA IMO TeamBirkha¨user Boston Basel BerlinTitu AndreescuThe University of Texas at DallasDepartment of Science/Mathematics Education Richardson, TX 75083U.S.A.Dor

12、in Andrica“Babes¸-Bolyai” University Faculty of Mathematics 3400 Cluj-Napoca RomaniadorinandricaZuFengPhillips Exeter Academy Department of Mathematics Exeter, NH 03833U.S.A.Cover design by Mary Burgess.Mathematics Subject Classication (2000): 00A05, 00A07, 11-00, 11-XX, 11Axx, 1

13、1Bxx, 11D04Library of Congress Control Number: 2006935812ISBN-10: 0-8176-4527-6ISBN-13: 978-0-8176-4527-4e-ISBN-10: 0-8176-4561-6e-ISBN-13: 978-0-8176-4561-8Printed on acid-paper. c 2007 Birkha¨user Boston. This work may not be translated or copied in whole or in part without the writ-ten permi

14、ssion of the publisher (Birkha¨user Boston, c/o Springer Science+Business Media LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronicadaptatio

15、n, computer software, or by similar or dissimilar methodology now known or hereafter de- veloped is forbidden.The use in this publication of trade names, trademarks, service marks and similar terms, even if they are not identied as such, is not to be taken as an expression of opinion as to whether o

16、r not they are subject to proprietary rights.9 8 7 6 5 4 3 2 1 (EB)104 Number Theory ProblemsTitu Andreescu, Dorin Andrica, ZuFengOctober 25, 2006ContentsPreface AcknowledgmentsAbbreviations and Notationvii ixxi1Foundations of Number Theory DivisibilityDivision Algorithm PrimesThe Fundamental Theore

17、m of Arithmetic.Euclidean Algorithm Be´zouts Identity L.C.M.The Number of Divisors The Sum of Divisors Modular Arithmetics Residue ClassesFermats Little Theorem and Eulers Theorem Eulers Totient FunctionMultiplicative Function1145711121316171819242733363840465265707172Linear Dioph Numerical Sys

18、temsEquationsDivisibility Criteria in the Decimal System Floor FunctionLegendres Function Fermat Numbers Mersenne Numbers Perfect NumbersContentsvi2345Introductory Problems Advanced ProblemsSolutions to Introductory ProblemsSolutions to Advanced Problems758391131Glossary FurtherIndex189197203ingPref

19、aceThis book contains 104 of the best problems used in the training and testing of the U.S. International Mathematical Olympiad (IMO) team. It is not a collection of very difcult, and impenetrable questions. Rather, the book gradually builds s number-theoretic skills and techniques. The rst chapter

20、provides acompensive introduction to number theory and its mathematical structures. This chapter can serve as a textbook for a short course in number theory. Thiswork aims to broadens view of mathematics and better prepare them forpossible participation in various mathematical competitions. It provi

21、des in-depthenrichment in important areas of number theory by reorganizing and enhngs problem-solving tactics and strategies. The book further stimulates stu-dents interest for the future study of mathematics.In the United States of America, the selection process leading to participation in the Inte

22、rnational Mathematical Olympiad (IMO) consists of a series of national contests called the American Mathematics Contest 10 (AMC 10), the American Mathematics Contest 12 (AMC 12), the American Invitational Mathematics Ex- amination (AIME), and the United States of America Mathematical Olympiad (USAMO

23、). Participation in the AIME and the USAMO is by invitation only, based on performance in the preceding exams of the sequence. The Mathematical Olympiad Summer Program (MOSP) is a four-week intensive training programfor approximately fty very promisings who have risen to the top in theAmerican Mathe

24、matics Competitions. The sixs representing the UnitedStates of America in the IMO are selected on the basis of their USAMO scores and further testing that takes place during MOSP. Throughout MOSP, full days ofclasses and extensive problem sets gives thorough preparation in severalimportant areas of

25、mathematics. These topics include combinatorial argumentsand identities, generating functions, graph theory, recursive relations, sums and products, probability, number theory, polynomials, functional equations, complex numbers in geometry, algorithmic proofs, combinatorial and advanced geometry, fu

26、nctional equations, and classical inequalities.Olympiad-style exams consist of several challenging essay problems. Correct solutions often require deep analysis and careful argument. Olympiad questionsPrefaceviiican seem impenetrable to the novice, yet most can be solved with elementary high school

27、mathematics techniques, when cleverly applied.Here is some advice fors who attempt the problems that follow.Take your time! Very few contestants can solve all the given problems.Try to make connections between problems. An important theme of this work is that all important techniques and ideas featu

28、red in the book appear more than once!Olympiad problems dont “crack” immediately. Be patient. Try different approaches. Experiment with simple cases. In some cases, working back- ward from the desired result is helpful.Even if you can solve a problem, dothe solutions. They may con-tain some ideas th

29、at did not occur in your solutions, and they may discuss strategic and tactical approaches that can be used elsewhere. The solutionsare also ms of elegant presentation that you should emulate, but theyoften obscure the tortuous process of investigation, false starts, inspiration,and attention tothat

30、 led to them. When youthe solutions, try toreconstruct the thinking that went into them. Ask yourself, “What were the key ideas? How can I apply these ideas further?”Go back to the original problem later, and see whether you can solve it in a different way. Many of the problems have multiple solutio

31、ns, but not all are outlined here.Meaningful problem solving takes practice. Dont get discouraged if youhave trouble at rst. For additional practice, use the books on the list.ingTitu Andreescu Dorin AndricaZuFengOctober 2006AcknowledgmentsThanks to Sara Campbell, Yingyu (Dan) Gao, Sherry Gong, Koen

32、e Hon, Ryan Ko, Kevin Medzelewski, Garry Ri, and Kijun (Larry) Seo. They were the membersof Zus number theory class at Phillips Exeter Academy. They worked onthe rst draft of the book. They helped proofthe original manuscript, raisedcritical questions, and provided acute mathematical ideas. Their co

33、ntribution im- proved the avor and the structure of this book. We thank Gabriel Dospinescu (Dospi) for many remarks and corrections to the rst draft of the book. Some ma-terials aapted from 11, 12, 13, and 14. We also thank thoseswho helped Titu and Zuedit those books.Many problems are either inspir

34、ed by or adapted from mathematical contestsin different countries and from the following journals: The American Mathematical Monthly, United States of America Crux, Canada High School Mathematics, Mathematics Magazine, United States of America Revista Matematica Timis¸oara, RomaniaWe did our be

35、st to cite all the original sources of the problems in the solution section. We express our deepest appreciation to the original proposers of the problems.Abbreviations and NotationAbbreviationsAHSME AIME AMC10 AMC12 APMC ARMLBalkan Baltic HMMT IMO USAMO MOSPPutnamSt. PetersburgAmerican High School

36、Mathematics Examination American Invitational Mathematics Examination American Mathematics Contest 10American Mathematics Contest 12, which replaces AHSME AustrianPolish Mathematics CompetitionAmerican Regional Mathematics League Balkan Mathematical OlympiadBaltic Way Mathematical Team Contest Harva

37、rdMIT Math Tournament International Mathematical OlympiadUnited States of America Mathematical Olympiad Mathematical Olympiad Summer ProgramThe William Lowell Putnam Mathematical Competition St. Petersburg (Leningrad) Mathematical OlympiadNotation for Numerical Sets and FieldsZZn N N0Q Q+ Q0QnR R+ R

38、0Rn Cxn( p(x)the set of integersthe set of integers modulo nthe set of positive integersthe set of nonnegative integers the set of rational numbersthe set of positive rational numbersthe set of nonnegative rational numbers the set of n-tuples of rational numbers the set of real numbersthe set of pos

39、itive real numbersthe set of nonnegative real numbers the set of n-tuples of real numbers the set of complex numbersthe coefcient of the term xn in the polynomial p(x)Abbreviations and NotationxiiNotation for Sets, Logic, and Number Theory| A|the number of elements in the set A A is a proper subset

40、of BA is a subset of BA without B (set difference) the intersection of sets A and B the union of sets A and Bthe element a belongs to the set A n divides mthe greatest common divisor of m, nthe least common multiple of m, nA BA BA BA BA Ba An m(m, n)lcm(m, n) (n) (n) (n)the number of primes nnumber

41、of divisors of nsum of positive divisors of na and b are congruent modulo mEulers totient function order of a modulo m Mo¨bius functionbase-b representation the sum of digits of n factorial base expansion oor of xcelling of x fractional part of x Legendres function pk fully divides n Fermat num

42、ber Mersenne numbera b (mod m)ordm(a) µakak1 . a0(b)S(n)( f1, f2,., fm) x x x eppk nfn Mn1Foundations of Number TheoryDivisibilityBack in elementary school, we learned four fundamental operations on numbers(integers), namely, addition (+), subtraction (), multiplication (× or ·), and

43、di-vision (÷ or / or c ). For any two integers a and b, their sum a + b, differencesa b and b a, and product ab are all integers, while their quotients a ÷ b (oraa/b or ) and b ÷ a are not necessarily integers.bFor an integer m and a nonzero integer n, we say that m is divisible by n

44、or nmdivides m if there is an integer k such that m = kn; that is,is an integer. Wendenote this by n | m. If m is divisible by n, then m is called a multiple of n; andn is called a divisor (or factor) of m.Because 0 = 0 · n, it follows that n | 0 for all integers n. For a xed integern, the mult

45、iples of n are 0, ±n, ±, 2n,.Hence it is not difcult to see thatthere is a multiple of n among every n consecutive integers. If m is not divisible by n, then we write n m. (Note that 0 m for all nonzero integers m, since m = 0 = k · 0 for all integers k.)Proposition 1.1. Let x, y, and

46、 z be integers. We have the following basic prop- erties:(a) x | x (reexivity property);(b) If x | y and y | z, then x | z (transitivity property);(c) If x | y and y = 0, then |x | |y|;(d) If x | y and x | z, then x | y + z for any integers and ;(e) If x | y and x | y ± z, then x | z;(f) If x |

47、 y and y | x , then |x |= |y|;104 Number Theory Problems2y(g) If x | y and y = 0, then| y;x(h) for z = 0, x | y if and only if xz | yz.The proofs of the above properties are rather straightforward from the deni-tion. We present these proo writing proofs.ly to give theer some relevant examples ofProo

48、f: For (a), we note that x = 1 · x . In (b) to (h), the condition x | y is given;that is, y = kx for some integer k.For (b), we have y | z; that is, z = k1 y for some integer k1. Then z = (kk1)x ,or x | z.For (c), we note that if y = 0, then |k| 1, and so |y|= |k|· |x | |x |.For (d), we fu

49、rther assume that z = k2x . Then y + z = (k + k2)x .For (e), we obtain y ± z = k3x , or ±z = k3x y = (k3 k)x . It follows thatz = ±(k k3)x .For (f), because x | y and y | x , it follows that x = 0 and y = 0. By (c), wehave |y| |x | and |x | |y|. Hence |x |= |y|.yFor (g),= k = 0 is an

50、integer. Since y = x · k, k | y.xFor (h), since z = 0, x = 0 if and only if xz = 0. Note that y = kx if and only if yz = kxz.The property (g) is simple but rather helpful. For a nonzero integer n, thereis an even number of positive divisors of n unless n is a perfect square; that is,n = m2 for

51、some integer m. (If an integer is not divisible by any perfect square,then it is called square. If n = m3 for some integer m, then n is called amsperfect cube. In general, if n =for integers m and s with s 2, then nis called a perfect power.) This is because all the divisors of y appear in pairs,yna

52、mely, x and(observe that x =if y is not a perfect square). Here is a classicyxxbrain teaser:Example 1.1. Twenty boreds take turns walking down a hall that con-tains a row of lockers; the second 16, 18, 20; the third if a locker wason. For the i thd lockers, numbered 1 to 20. The rstopens all thes al

53、l the lockers numbered 2, 4, 6, 8, 10, 12, 14,operates on the lockers numbered 3, 6, 9, 12, 15, 18:d, he opens it, and if a locker was open, hes it; and so, he works on the lockers numbered by multiples of i : if alocker wasd, he opens it, and if a locker was open, hes it. What is thenumber of the l

54、ockers that remain open after all thes nish their walks?Solution: Note that the i th locker will be operated byj if and only ifj | i . By property (g), this can happen if and only if the locker will also bei222operated by. Thus, only the lockers numbered 1 = 1 , 4 = 2 , 9 = 3 ,j1. Foundations of Num

55、ber Theory3and 16 = 42 will be operated on an odd number of times, and these are the lockers that will be left open after all the operations. Hence the answer is 4.The set of integers, denoted by Z, can be partitioned into two subsets, the set of odd integers and the set of even integers:±1, &#

56、177;3, ±5,. and 0, ±2, ±4,. ,respectively. Although the concepts of odd and even integers appear straightfor- ward, they come handy in tackling various number-theoretic problems. Here are some basic ideas:(1) an odd number is of the form 2k + 1, for some integer k;(2) an even number i

57、s of the form 2m, for some integer m;(3) the sum of two odd numbers is an even number;(4) the sum of two even numbers is an even number;(5) the sum of an odd and even number is an odd number;(6) the product of two odd numbers is an odd number;(7) a product of integers is even if and only if at least one of its factors is even.Example 1.2. Let n be an integer greater than 1. Prove that(a) 2