Advanced book on Mathematics Olympiad

5.2 Arithmetic 267 Solution.We show that any subset ofShavingnelements that are pairwise coprime can be extended to a set withn+ ...

268 5 Number Theory Euler’s theorem is widely used in cryptography. The encryption scheme used nowa- days, called the RSA algori ...

5.2 Arithmetic 269 Proof.For anyj,1≤j≤k, the numberm/mjis coprime tomjand hence invertible with respect tomj. Letbjbe the invers ...

270 5 Number Theory 786.Prove that for everyn, there existnconsecutive integers each of which is divisible by two different prim ...

5.3 Diophantine Equations 271 Proof.For the equation to have solutions it is clearly necessary thatcbe divisible by gcd(a, b). D ...

272 5 Number Theory has determinant 1. The matrices with this property form thespecial linear groupSL( 2 ,Z). This group is gene ...

5.3 Diophantine Equations 273 795.Leta, b, c, dbe integers with the property that for any two integersmandnthere exist integersx ...

274 5 Number Theory And now the problems. 797.Given a piece of paper, we can cut it into 8 or 12 pieces. Any of these pieces can ...

5.3 Diophantine Equations 275 There is a more profound way to look at this equation. Dividing through byz^2 ,we obtain the equiv ...

276 5 Number Theory Example.The numbers 2FnFn+ 1 ,Fn− 1 Fn+ 2 andF 2 n+ 1 form a Pythagorean triple. Solution.In our parametriza ...

5.3 Diophantine Equations 277 x^2 −Dy^2 = 1 has infinitely many solutions in positive integers and the general solution(xn,yn)n≥ ...

278 5 Number Theory the numberR=ln(x 1 +y 1 √ D), called the regulator, with a certain accuracy. At the time of the writing this ...

5.3 Diophantine Equations 279 Prove that the equation x^3 +y^3 +z^3 +t^3 = 1999 has infinitely many integer solutions. 812.Pro ...

6 6 Combinatorics and Probability.................................... We conclude the book with combinatorics. First, we train c ...

282 6 Combinatorics and Probability hypothesis,Ai 1 ∩···∩Aik− 1 ∈S, and alsoAik∈S,so(Ai 1 ∩···∩Aik− 1 )∩Aikis inS. This complete ...

6.1 Combinatorial Arguments in Set Theory and Geometry 283 824.LetMbe a subset of{ 1 , 2 , 3 ,..., 15 }such that the product of ...

284 6 Combinatorics and Probability Example.Consider the permutations σ 1 = ( 1234 ···19 20 a 1 a 2 a 3 a 4 ···a 19 a 20 ) , σ 2 ...

6.1 Combinatorial Arguments in Set Theory and Geometry 285 an angle of^2 nπaround its center. Such a rotation can be written as ...

286 6 Combinatorics and Probability 835.Determine the number of permutationsa 1 ,a 2 ,...,a 2004 of the numbers 1, 2,..., 2004 f ...

6.1 Combinatorial Arguments in Set Theory and Geometry 287 The two-dimensional analogue of this property states that from finite ...