Advanced book on Mathematics Olympiad

5.1 Integer-Valued Sequences and Functions 247 ( 5 k+ 2 )^2 + 12 =( 4 k+ 1 )^2 +( 3 k+ 2 )^2 , ( 5 k+ 3 )^2 + 12 =( 4 k+ 3 )^2 + ...

248 5 Number Theory 703.Prove that there exists no bijectionf:N→Nsuch that f (mn)=f (m)+f (n)+ 3 f (m)f (n), for allm, n≥1. 704. ...

5.1 Integer-Valued Sequences and Functions 249 Prove thatSmust equal the set of all integers. Solution.This problem was submitte ...

250 5 Number Theory Prove that for no integern>1 doesndivide 2n−1. 712.Find all pairs of positive integers(a, b)with the pr ...

5.1 Integer-Valued Sequences and Functions 251 Our second example is a general identity discovered by the second author and D. A ...

252 5 Number Theory 715.For a positive integernand a real numberx, compute the sum ∑ 0 ≤i<j≤n ⌊ x+i j ⌋ . 716.Prove that for ...

5.2 Arithmetic 253 5.2 Arithmetic.................................................... 5.2.1 Factorization and Divisibility There ...

254 5 Number Theory 726.The sequencea 1 ,a 2 ,a 3 ,...of positive integers satisfies gcd(ai,aj)=gcd(i, j ) fori =j. Prove tha ...

5.2 Arithmetic 255 an example, in this topology both the set of odd integers and the set of even integers are open. Because the ...

256 5 Number Theory We proceed with a problem from the 35th International Mathematical Olympiad, 1994, followed by several other ...

5.2 Arithmetic 257 741.The positive divisors of an integern>1 are 1=d 1 <d 2 <···<dk=n. Let s=d 1 d 2 +d 2 d 3 + ··· ...

258 5 Number Theory 747.Prove that the expression gcd(m, n) n ( n m ) is an integer for all pairs of integersn≥m≥1. 748.Letkandn ...

5.2 Arithmetic 259 Example.Letp>3 be a prime number, and let r ps = 1 + 1 2 + 1 3 +···+ 1 p , the sum of the firstpterms of t ...

260 5 Number Theory We left the better problems as exercises. 749.Prove that among any three distinct integers we can find two, ...

5.2 Arithmetic 261 Fermat’s little theorem.Letpbe a prime number, andna positive integer. Then np−n≡ 0 (modp). Proof.We give a g ...

262 5 Number Theory Example.Show that for every primepthere is an integernsuch that 2n+ 3 n+ 6 n− 1 is divisible byp. Solution.T ...

5.2 Arithmetic 263 A different solution is possible using reduction modulo 13. Fermat’s little theorem impliesa^12 ≡ 1 (mod 13)w ...

264 5 Number Theory 767.Letf(x 1 ,x 2 ,...,xn)be a polynomial with integer coefficients of total degree less thann. Show that th ...

5.2 Arithmetic 265 Here are more examples. 769.For each positive integern, find the greatest common divisor ofn!+1 and(n+ 1 )!. ...

266 5 Number Theory Again, we see that the numbers divisible bypi,pj, andplhave been subtracted and then added back, so we need ...