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

This hard challenge publication by means of popular US Olympiad coaches, arithmetic academics, and researchers develops a mess of problem-solving talents had to excel in mathematical contests and in mathematical study in quantity thought. supplying proposal and highbrow pride, the issues in the course of the booklet inspire scholars to precise their principles in writing to provide an explanation for how they conceive difficulties, what conjectures they make, and what conclusions they achieve. utilizing particular innovations and methods, readers will gather a pretty good knowing of the basic suggestions and ideas of quantity thought.

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

Similar number theory books

Experimental Number Theory

This graduate textual content, in response to years of training adventure, is meant for first or moment 12 months graduate scholars in natural arithmetic. the most objective of the textual content is to teach how the pc can be utilized as a device for examine in quantity concept via numerical experimentation. The publication comprises many examples of experiments in binary quadratic types, zeta services of sorts over finite fields, basic category box concept, elliptic devices, modular varieties, besides routines and chosen suggestions.

Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography

Chinese language the rest Theorem, CRT, is likely one of the jewels of arithmetic. it's a ideal mixture of attractiveness and application or, within the phrases of Horace, omne tulit punctum qui miscuit utile dulci. recognized already for a long time, CRT maintains to provide itself in new contexts and open vistas for brand new sorts of purposes.

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

Sample text

For example, µ(2) = −1, µ(6) = 1, µ(12) = µ(22 · 3) = 0. 35. The M¨obius function µ is multiplicative. Proof: Let m, n be positive integers such that gcd(m, n) = 1. If p 2 | m for some p > 1, then p 2 | mn and so µ(m) = µ(mn) = 0 and we are done. Consider now m = p1 · · · pk , n = q1 · · · qh , where p1 , . . , pk , q1 , . . , qh are distinct primes. Then µ(m) = (−1)k , µ(n) = (−1)h , and mn = p1 · · · pk q1 · · · qh . It follows that µ(mn) = (−1)k+h = (−1)k (−1)h = µ(m)µ(n). For an arithmetic function f we deﬁne its summation function F by F(n) = f (d).

Solution: The answer is k = 4. We ﬁrst show that 20022002 is not a sum of three cubes. To restrict the number of cubes modulo n, we would like to have ϕ(n) to be a multiple of 3. Again, consider n = 7. But adding three cubes modulo 7 gives too many residue classes (since 7 is too small). We then consider n = 9 with ϕ(9) = 6. Because 2002 ≡ 4 (mod 9) and 20023 ≡ 43 ≡ 1 (mod 9), it follows that 20022002 ≡ (20023 )667 · 2004 ≡ 4 (mod 9). On the other hand, x 3 ≡ 0, ±1 (mod 9) for integers x. We see that x13 +x23 +x33 ≡ 4 (mod 9).

We will study the solutions of the linear congruence systems when we study the Chinese Remainder Theorem in the sequel to this book: 105 Diophantine Equations and Integer Function 1. Foundations of Number Theory 23 Problems. The major difference between solving an equation and solving a congruence equation is the limitation of division in the latter situation. For example, in algebra, 4x = 4y implies that x = y. In modular arithmetic, 4x ≡ 4y (mod 6) does not necessarily imply that x ≡ y (mod 6).