Number Theory - Art of Problem Solving

1 Number TheoryNaoki PrefaceThis set of notes on Number Theory was originally written in 1995 for studentsat the IMO level. It covers the basic background material that an IMOstudent should be familiar with. This text is meant to be a reference, andnota replacement but rather a supplement to a Number Theory textbook;several are given at the back. Proofs are given when appropriate, or whenthey illustrate some insight or important idea. The problems are culled fromvarious sources, many from actual contests and olympiads, and in generalare very difficult. The author welcomes any corrections or DivisibilityFor integersaandb, we say thatadividesb, or thatais adivisor(orfactor) ofb, or thatbis amultipleofa, if there exists an integercsuchthatb=ca, and we denote this bya|b.

2 Otherwise,adoes not divideb, andwe denote this bya-b. A positive integerpis aprimeif the only divisors ofpare 1 andp. Ifpk|aandpk+1-awherepis a prime, the highestpower ofpdividinga, then we denote this bypk Facts Ifa,b >0, anda|b, thena b. Ifa|b1,a|b2, .. ,a|bn, then for any integersc1,c2, .. ,cn,a|n i= Division Algorithm. For any positive integeraandintegerb, there exist unique integersqandrsuch thatb=qa+rand0 r < a, withr= 0 iffa| Fundamental Theorem of Arithmetic. Every integergreater than 1 can be written uniquely in the formpe11pe22 pekk,where thepiare distinct primes and theeiare positive (Euclid) There exist an infinite Number of Suppose that there are a finite Number of primes, sayp1,p2.

3 ,pn. LetN=p1p2 pn+ 1. By the fundamental theorem of arithmetic,Nis divisible by some primep. This primepmust be among thepi, since byassumption these are all the primes, butNis seen not to be divisible by anyof thepi, Letxandybe integers. Prove that 2x+ 3yis divisibleby 17 iff 9x+ 5yis divisible by 17|(2x+ 3y) 17|[13(2x+ 3y)], or 17|(26x+ 39y) 17|(9x+ 5y), and conversely, 17|(9x+ 5y) 17|[4(9x+ 5y)], or17|(36x+ 20y) 17|(2x+ 3y).Example Find all positive integersdsuch thatddivides bothn2+1and (n+ 1)2+ 1 for some Letd|(n2+ 1) andd|[(n+ 1)2+ 1], ord|(n2+ 2n+ 2).Thend|[(n2+ 2n+ 2) (n2+ 1)], ord|(2n+ 1) d|(4n2+ 4n+ 1), sod|[4(n2+2n+2) (4n2+4n+1)], ord|(4n+7).

4 Thend|[(4n+7) 2(2n+1)],ord|5, sodcan only be 1 or 5. Takingn= 2 shows that both of thesevalues are Suppose thata1,a2, .. ,a2nare distinct integers suchthat the equation(x a1)(x a2) (x a2n) ( 1)n(n!)2= 0has an integer solutionr. Show thatr=a1+a2+ +a2n2n.(1984 IMO Short List)Solution. Clearly,r6=aifor alli, and ther aiare 2ndistinct integers,so|(r a1)(r a2) (r a2n)| |(1)(2) (n)( 1)( 2) ( n)|= (n!)2,2with equality iff{r a1, r a2, .. , r a2n}={1,2, .. , n, 1, 2, .. , n}.Therefore, this must be the case, so(r a1) + (r a2) + + (r a2n)= 2nr (a1+a2+ +a2n)= 1 + 2 + +n+ ( 1) + ( 2) + + ( n) = 0 r=a1+a2+ + Let 0< a1< a2< < amn+1bemn+ 1 integers.

5 Provethat you can select eitherm+ 1 of them no one of which divides any other,orn+ 1 of them each dividing the following one.(1966 Putnam Mathematical Competition)Solution. For eachi, 1 i mn+ 1, letnibe the length of the longestsequence starting withaiand each dividing the following one, among theintegersai,ai+1, .. ,amn+1. If someniis greater thannthen the problemis solved. Otherwise, by the pigeonhole principle, there are at leastm+ 1values ofnithat are equal. Then, the integersaicorresponding to thesenicannot divide each Facts Bertrand s Postulate. For every positive integern, there exists a primepsuch thatn p 2n. Gauss s Lemma.

6 If a polynomial with integer coefficients factors intotwo polynomials with rational coefficients, then it factors into two poly-nomials with integer Letaandbbe positive integers such thata|b2,b2|a3,a3|b4,b4|a5,.. Prove thata= Leta,b, andcdenote three distinct integers, and letPdenote a poly-nomial having all integral coefficients. Show that it is impossible thatP(a) =b,P(b) =c, andP(c) =a.(1974 USAMO)33. Show that ifaandbare positive integers, then(a+12)n+(b+12)nis an integer for only finitely many positive integersn.(A Problem Seminar, Newman)4. For a positive integern, letr(n) denote the sum of the remainders whennis divided by 1, 2.

7 ,nrespectively. Prove thatr(k) =r(k 1) forinfinitely many positive integersk.(1981 K ursch ak Competition)5. Prove that for all positive integersn,0<n k=1g(k)k 2n3<23,whereg(k) denotes the greatest odd divisor ofk.(1973 Austrian Mathematics Olympiad)6. Letdbe a positive integer, and letSbe the set of all positive integersof the formx2+dy2, wherexandyare non-negative integers.(a) Prove that ifa Sandb S, thenab S.(b) Prove that ifa Sandp S, such thatpis a prime andp|a,thena/p S.(c) Assume that the equationx2+dy2=phas a solution in non-negative integersxandy, wherepis a given prime. Show that ifd 2, then the solution is unique, and ifd= 1, then there areexactly two GCD and LCMT hegreatest common divisorof two positive integersaandbis the great-est positive integer that divides bothaandb, which we denote by gcd(a, b),and similarly, thelowest common multipleofaandbis the least positive4integer that is a multiple of bothaandb, which we denote by lcm(a, b).

8 Wesay thataandbarerelatively primeif gcd(a, b) = 1. For integersa1,a2,.. ,an, gcd(a1, a2, .. , an) is the greatest positive integer that divides all ofa1,a2, .. ,an, and lcm(a1, a2, .. , an) is defined Facts For alla,b, gcd(a, b) lcm(a, b) =ab. For alla,b, andm, gcd(ma, mb) =mgcd(a, b) and lcm(ma, mb) =mlcm(a, b). Ifd|gcd(a, b), thengcd(ad,bd)=gcd(a, b) particular, ifd= gcd(a, b), then gcd(a/d, b/d) = 1; that is,a/dandb/dare relatively prime. Ifa|bcand gcd(a, c) = 1, thena|b. For positive integersaandb, ifdis a positive integer such thatd|a,d|b, and for anyd ,d |aandd |bimplies thatd |d, thend=gcd(a, b). This is merely the assertion that any common divisor ofaandbdivides gcd(a, b).

9 Ifa1a2 anis a perfectkthpower and theaiare pairwise relativelyprime, then eachaiis a perfectkthpower. Any two consecutive integers are relatively Show that for any positive integerN, there exists amultiple ofNthat consists only of 1s and 0s. Furthermore, show that ifNis relatively prime to 10, then there exists a multiple that consists only of Consider theN+ 1 integers 1, 11, 111, .. , (N+ 1 1s).When divided byN, they leaveN+ 1 remainders. By the pigeonhole princi-ple, two of these remainders are equal, so the difference in the correspondingintegers, an integer of the form , is divisible byN. IfNis relativelyprime to 10, then we may divide out all powers of 10, to obtain an integer ofthe form that remains divisible For any positive integersaandb, there exist integersxandysuch thatax+by= gcd(a, b).

10 Furthermore, asxandyvary over allintegers,ax+byattains all multiples and only multiples of gcd(a, b).Proof. LetSbe the set of all integers of the formax+by, and letdbe theleast positive element ofS. By the division algorithm, there exist integersqandrsuch thata=qd+r, 0 r < d. Thenr=a qd=a q(ax+by) =(1 qx)a (qy)b, soris also inS. Butr < d, sor= 0 d|a, andsimilarly,d|b, sod|gcd(a, b). However, gcd(a, b) divides all elements ofS,so in particular gcd(a, b)|d d= gcd(a, b). The second part of the The positive integersaandbare relatively prime iff thereexist integersxandysuch thatax+by= For any positive integersa1,a2, .. ,an, there existintegersx1,x2.