# 104 number theory problems : from the training of the USA by Titu Andreescu

By Titu Andreescu

This hard challenge e-book by means of popular US Olympiad coaches, arithmetic lecturers, and researchers develops a mess of problem-solving talents had to excel in mathematical contests and in mathematical examine in quantity idea. providing concept and highbrow pride, the issues in the course of the publication motivate scholars to specific their rules in writing to provide an explanation for how they conceive difficulties, what conjectures they make, and what conclusions they achieve. utilising particular ideas and methods, readers will collect a pretty good realizing of the basic recommendations and ideas of quantity theory.

Read Online or Download 104 number theory problems : from the training of the USA IMO team PDF

Best number theory books

Ramanujan's Notebooks

This ebook constitutes the 5th and ultimate quantity to set up the implications claimed by way of the nice Indian mathematician Srinivasa Ramanujan in his "Notebooks" first released in 1957. even supposing all of the 5 volumes includes many deep effects, possibly the common intensity during this quantity is bigger than within the first 4.

Problem-Solving and Selected Topics in Number Theory: In the Spirit of the Mathematical Olympiads

This e-book is designed to introduce one of the most very important theorems and effects from quantity thought whereas trying out the reader’s knowing via rigorously chosen Olympiad-caliber difficulties. those difficulties and their recommendations give you the reader with a chance to sharpen their talents and to use the speculation.

Primality testing for beginners

How will you inform no matter if a bunch is key? What if the quantity has countless numbers or millions of digits? this question could seem summary or beside the point, yet in truth, primality exams are played whenever we make a safe on-line transaction. In 2002, Agrawal, Kayal, and Saxena replied a long-standing open query during this context through featuring a deterministic try out (the AKS set of rules) with polynomial working time that assessments even if a host is key or no longer.

Additional info for 104 number theory problems : from the training of the USA IMO team

Example text

The set T = aS + b = {as + b | s ∈ S} is also a complete set of residue classes modulo n. 26 104 Number Theory Problems Now we are better equipped to discuss linear congruence equations a bit further. 25. Let m be a positive integer. Let a be an integer relatively prime to m, and let b be an integer. There exist integers x such that ax ≡ b (mod m), and all these integers form exactly one residue class modulo m. Proof: Let {c1 , c2 , . . , cm } be a complete set of residue classes modulo m. 24, {ac1 − b, ac2 − b, .

18. (a) a ≡ a (mod m) (reﬂexivity). (b) If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m) (transitivity). (c) If a ≡ b (mod m), then b ≡ a (mod m). 20 104 Number Theory Problems (d) If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m) and a − c ≡ b − d (mod m). (e) If a ≡ b (mod m), then for any integer k, ka ≡ kb (mod m). (f) If a ≡ b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m). In general, if ai ≡ bi (mod m), i = 1, . . , k, then a1 · · · ak ≡ b1 · · · bk (mod m). In particular, if a ≡ b (mod m), then for any positive integer k, a k ≡ bk (mod m).

Proof: Let d = gcd(a1 , . . , an ). If b is not divisible by d, then (∗) is not solvable, since for any integers x1 , . . , xn the left-hand side of (∗) is divisible by d and the right-hand side is not. If d | b, then we obtain the equivalent equation a1 x 1 + · · · + an x n = b , 1. Foundations of Number Theory 39 where ai = ai /d for i = 1, . . , n and b = b/d. Clearly, we have gcd(a1 , . . , an ) = 1. We use induction on the number n of the variables. In the case n = 1 the equation has the form x1 = b or −x1 = b, and thus the unique solution does not depend on any parameter.