Problems in Elementary Number Theory

1 Problems in Elementary Number TheoryCompiled by Hojoo LeeVersion , Last revised on May, 2003 Typeset by LATEXThis book is available at nonprofit use onlyCopyrightc 2003 Hojoo LeeContents1. Introduction12. Divisibility Theory2 Problems2 Sources53. Congruences6 Problems6 Sources74. Primes and Composite Numbers7 Problems7 Sources85. Diophantine Equations8 Problems8 Sources116. Functions in Number Theory12 Problems12 Sources147. Rational and Irrational Numbers14 Problems14 Sources158. Additive Number Theory16 Problems16 Sources179. Sequences of Integers18 Problems18 Sources2010. Combinatorial Number Theory21 Problems21 Sources2311. Miscellaneous Problems23 Problems23 Sources25 Problems IN Elementary Number THEORYV ersion : May heart of Mathematics is its of This BookThe purpose of this book is to present a collection of interesting questions inElementary Number Theory .

2 This resource book was written for the beginners inNumber Theory . It is also intended to help students preparing to paricipate in theMathematical competitions such as IMO or the ProblemsIt contains 230 Problems . Many of the Problems in this book are Mathemati-cal competition Problems all over the the world including IMO, APMO, APMC,Putnam, etc. I consulted also many Math journals with Problems and Solutionssection. I have given sources of the Problems at the end of the each the StudentsAlthough you can undestand most of the Problems in this book, you will find thatsome of Problems are very hard. In fact, there are well-known theorems or deepresults. So, if you want to attack many Problems in this book, then you should befamilar with results inElementary Number Theory .

3 My favorite books are follow-ing : Elementary Number Theory : David M. Burton, Mc-Graw-Hill The Theory of Numbers (A Text and Source Book of Problems )by Andrew Adler and John E. Cloury, Jones and Bartlett An Introduction to the Theory of Numbers by H. S. Zuckerman,H. L. Montgomery, I. Niven, John Wiley and Sons An Introduction to the Theory of Numbers by E. M. Wright andG. H. Hardy, Oxford University PressIf you are interested in open Problems in Number Theory , then the followingbooks will be useful : Unsolved Problems in Number Theory (Problem Books in Math-ematics) by Richard K. Guy, New York : Springer-Verlag Solved and Unsolved Problems in Number Theory by Daniel Shanks,AMS Chelsea Publishing12 Problems IN Elementary Number THEORYFor more books in Number Theory , you should visit the web site krm/ You Can HelpThis book is an unfinished manuscript.

4 The current version of this book Iwould like to hear about other interesting Problems inElementary Number would be very nice if you send me your favorite Problems , fascinating facts orrecent Problems from your regional Mathematical Competitions. You can send allcomments to the author at ENJOY THE BOOK ! a positive integer such that2 + 2 28n2+ 1is an integer. Show that2 + 2 28n2+ 1is the square of an positive integers such thatab+ 1dividesa2+b2. Show thata2+b2ab+ 1is the square of an positive integers such thatxydividesx2+y2+ 1. Show thatx2+y2+ 1xy= all pairs(a, b)of integers for whicha2+b2+ 3is divisible all pairs(x, y)of positive integers withy|x2+ 1andx|y3+ all pairs(a, b)of positive integers such thatab2+b+ 7dividesa2b+a+ a positive integer withn 3.

5 Show thatnnnn nnnis divisible an integer withn 2. Show thatndoes not divide2n if there exists a positive integernsuch thatnhas exactly2000primedivisors and2n+ 1is divisible all integersn >1such that2n+ 1n2is an an integern, where100 n 1997, such that2n+ 2nis also an all triples(a, b, c)such that2c 1divides2a+ 2b+ IN Elementary Number all pairs(n, p)of nonnegative integers such that pis a prime, nnot exceeded2p, and (p 1)n+ 1is divisible bynp natural numbers such thatA=(m+ 3)n+ an integer. Prove thatAis (x) =x3+ 17. Prove that for each natural numbern 2, there is anatural numberxfor whichf(x)is divisible by3nbut not3n+ all positive integersnsuch that3n 1is divisible all positive integersnsuch that9n 1is divisible all positive integersnfor which there exists an integermso that2n 1dividesm2+ n be a positive integer.

6 Show that the product ofnconsecutive integers isdivisible byn! that the numbern k=0(2n+ 12k+ 1)23kis not divisible by5for any integern a prime Number greater than3andk= [2p3]. Prove that the sum(p1)+(p2)+ +(pk)of binomial coefficients is divisible that(2nn)|LCM[1,2, ,2n]for all positive arbitrary non-negative integers. Prove that(2m)!(2n)!m!n!(m+n)!is an integer.(0! = 1). that the coefficients of a binomial expansion(a+b)nwherenis a positiveinteger, are odd, if and only ifnis of the form2k 1for some positive that the expressiongcd(m, n)n(nm)is an integer for all pairs of positive integersn m which positive integersk, is it true that there are infinitely many pairs ofpositive integers(m, n)such that(m+n k)!

7 M!n!is an integer ?4 Problems IN Elementary Number that ifn 6is composite, thenndivides(n 1)!. that there exist infinitely many positive integersnsuch thatn2+1dividesn!. natural numbers such thatpq= 1 12+13 14+ 11318+ thatpis divisible positive integers. Whena2+b2is divided bya+b,the quotientisqand the remainder all pairs(a, b)such thatq2+r= all positive integersnthat have exactly16positive integral divisorsd1, d2 , d16such that1 =d1< d2< < d16=n,d6= 18, andd9 d8= thatnis a positive integer and letd1< d2< d3< d4be the four smallest positive integer divisors ofn. Find all integersnsuch thatn=d12+d22+d32+ a positive integer. Prove that the following two statements are equiv-alent. nis not divisible by4 There exista, b Zsuch thata2+b2+ 1is divisible the largest positive integernsuch thatnis divisible by all the positiveintegers less thann1 the greatest common divisor of the elements of the set{n13 n|n Z}.

8 Alln Nsuch that3n nis divisible that there are infinitely many compositensuch that3n 1 2n 1isdivisible that2n+ 1is an odd prime for some positive integern. Show thatnmust be a power thatpis a prime Number and is greater than3. Prove that7p 6p 1is divisible by that4n+ 2n+ 1is prime for some positive integern. Show thatnmust be a power ,m,nbe positive integersb >1andmandnare different. Suppose thatbm 1andbn 1have the same prime divisors. Show thatb+ 1must be a thata, bare natural numbers such thatp=4b 2a b2a+bis a prime Number . What is the maximum possible value ofp? >1,aandnbe positive integers such thatbn 1dividesa. Show that inbaseb, the numberahas at leastnnon-zero IN Elementary Number E otv os-K ursch ak Mathematics 1988 Mathematics Competition 1998 Problem for the Balkan Mathematical 2000 1997 1990 1999 Math Circle Monthly Contest Short List 1974 1972 Math.

9 Monthly, Problem E2623, Proposed by Ivan 1979 1977 19996 Problems IN Elementary Number Berkeley Preliminary Exam Short List Short List all positive integersnsuch thatxy+ 1 0(mod n)implies thatx+y 0(mod n). a prime Number . Determine the maximal degree of a polynomialT(x)whose coefficients belong to{0,1, , p 1}whose degree is less thanp, and whichsatisfiesT(n) =T(m)(mod p) = n=m(mod p)for all integersn, a positive integer. Prove thatnis prime if and only if(n 1k) ( 1)k(mod n)for allk {0,1, , n 1}.4.(Morley) Show that( 1)p 12(p 1p 12) 4p 1(mod p3)for all prime numberspwithp that there exists a composite numbernsuch thatan a(mod n)for alla a prime Number of the form4k+1. Suppose that2p+1is prime.

10 Showthat there is nok Nwithk <2pand2k 1 (mod2p+ 1) a positive integer. Show that there are infinitely many primespsuchthat the smallest positive primitive root ofpis greater thann, positive integersaandbare such that the numbers15a+ 16band16a 15bare both squares of positive integers. What is the least possible value that can betaken on by the smaller of these two squares? Problems IN Elementary Number a break,nchildren at school sit in a circle around their teacher to playa game. The teacher walks clockwise close to the children and hands out candies tosome of them according to the following rule. He selects one child and gives him acandy, then he skips the next child and gives a candy to the next one, then he skips2 and gives a candy to the next one, then he skips 3, and so on.