Advanced book on Mathematics Olympiad

Number Theory 691 738.The answer is negative. To motivate our claim, assume the contrary, and let a 0 ,a 1 ,...,a 1995 =a 0 be t ...

692 Number Theory 741.Note that ifdis a divisor ofn, then so isnd. So the sumsis given by s= ∑k−^1 i= 1 didi+ 1 =n^2 ∑k−^1 i= 1 ...

Number Theory 693 744.There are clearly more 2’s than 5’s in the prime factorization ofn!, so it suffices to solve the equation ...

694 Number Theory ∑ k≥ 1 k (⌊ n pk ⌋ − ⌊ n pk+^1 ⌋) = ∑ k≥ 1 (k−(k− 1 )) ⌊ n pk ⌋ = ∑ k≥ 1 ⌊ n pk ⌋ . By Polignac’s formula this ...

Number Theory 695 Of course, the sum terminates at themth term, wheremis defined bypm≤n<pm+^1. Writeγ=α 2 , so thatαequals ...

696 Number Theory 750.Observe that 2002= 103 + 103 + 13 + 13 , so that 20022002 = 20022001 · 2002 = ( ( 2002 )^667 ) 3 ( 103 + 1 ...

Number Theory 697 Sinces≡b(moda), there existsnsuch thats=an+b, and sosis a term of the arithmetic progression that can be writt ...

698 Number Theory Fori=1 the property is obviously true, sincep 1 =2 and the consecutive terms of the progression are odd number ...

Number Theory 699 whereσis a certain permutation of 1, 2 ,...,n. The sides are parallel to the raysσ(k)k, so the angle between ...

700 Number Theory 760.Note that n= 1 + 10 +···+ 10 p−^2 = 10 p−^1 − 1 10 − 1 . By Fermat’s little theorem the numerator is divis ...

Number Theory 701 Now assume that there are only finitely many primes of the form 4m+1,man integer, sayp 1 ,p 2 ,...,pn. The num ...

702 Number Theory nlim→∞xn=nlim→∞^3 n ( A ( 2 3 )n +B ) =∞. Letnbe sufficiently large thatxnis a prime number different from 2 a ...

Number Theory 703 for some integersm, cj,αji. Becausefis a polynomial of total degree less thann,we haveαj 1 +αj 2 + ··· +αjn< ...

704 Number Theory We conclude that ifais a perfect square but not a fourth power modulo 37, and is− 1 modulo 3, thenak≡− 1 (mod ...

Number Theory 705 Hence [( p− 1 2 ) ! ] 2 ≡− 1 (modp), as desired. To show that the equation has no solution ifp≡ 3 (mod 4), ass ...

706 Number Theory 775.We use strong induction. The property is true forn=1. Letn=pαq, wherepis a prime number andqis relatively ...

Number Theory 707 Ifn=pα 11 ···pαkk, then φ(n)=pα 11 −^1 ···pkαk−^1 (p 1 − 1 )···(pk− 1 ). If at least two of the primesp 1 ,... ...

708 Number Theory The last term in the first sum can be ignored since it is equal to zero. To evaluate the second sum, we observ ...

Number Theory 709 βto the customer. The customer computesβk(modn). By Euler’s theorem, this isα. Success! 784.As before, letpand ...

710 Number Theory 787.Letm=m 1 m 2 .Ifx ∈{ 0 , 1 ,...,m− 1 }is such thatP(x)≡ 0 (modm), then P(x)≡ 0 (modm 1 ). Leta 1 be the re ...